Joitter(ジョイッター) - joi2011-day1 解説

筆者: qnighy

2点間の経路の辺数が与えられた条件を満たすように、辺数最小かつその条件下で重み最小の部分グラフを見つける問題である。

(1)の条件を持つ人がいるとき

(1)の条件を持つ人がいるとき、そのような人は他の全ての人と直接繋がらなければならない。(必要条件)

さて、このとき、全ての人はそのような人を経由して辺数2で繋がるので、(2)あるいは(3)の条件を持つ人も条件を満たす。(十分条件)

よって、(1)の条件を持つ人がどちらか片方にでもいるような辺のみを選べばよい。

なんでもいいので、誰かを中心にして星(つまり高さ1の木)を作ることにしよう。すると、どの二人も辺数2以内で繋がるので、(2)および(3)の条件を満たす。(星は常に十分性を満たす。)よってこの解は有効な解である。(最小辺数の上界)

ところで、グラフが連結であるためには、n-1本以上の辺が必要であり、全ての人が(2)か(3)の条件を持つ以上、グラフは連結でないといけないため、答えとなる部分グラフは全域木であることがわかる。(最小辺数の下界)

全域木であるため、そのような部分グラフは閉路を持たない。また、2点間の経路は一意に定まる。

星は十分性を満たすので、以下では星以外に絞って考える。すなわち答えは星でないと仮定する。

N=2のとき、その2人が接続しあうグラフしか考ええない。これは星の一種であるので矛盾。

N=3のとき、やはり同様に直線状のグラフしかない。これもまた星の一種である。

Nが4以上のときを考える。

まず、このうち2つは(2)の条件を満たすはずなので、そのような2つをA,Bとおく。

AとBの経路の長さは1か2であるから、まず2の場合を考える。

この時、あるxがあって、A-x-Bと接続するはずである。

これは必ずxを根とする星になる。もし他に頂点yがあったとすると、これはAと距離2以内で繋がるはずであるが、もしxを経由せず繋がるならば、Bとの距離が2より大きくなり矛盾する。よって、yはxと接続していることになる。よって、これは星になる。

しかし星でないことを仮定しているので矛盾。

このような仮定から、星でない部分グラフならば、(2)の条件を満たす頂点は全て直接繋がっていることがわかる。

ということは、もし星でない部分グラフがありながら、(2)の条件を満たす頂点が3つ以上あるなら、閉路が生成され、矛盾するので、(2)の条件を満たす頂点はちょうど2つ(A,B)しかないとわかる。またこのとき、それ以外の頂点は全てAまたはBに直接接続していることがわかる。(必要性)

さて、(2)の条件を満たす頂点がちょうど2つ(A,B)しかなく、それ以外の頂点が全てAまたはBに接続しているならば、明らかにこれは条件を満たす。(十分性。)

よって、全体としては、「星」または「(2)の条件を満たす頂点がちょうど2つしかなく、他の頂点がいずれもそれらのうちの片方に直接接続しているようなグラフ」であることがわかる。

前者(星)は全ての頂点をそれぞれ根にして試してみればよく、後者はまずA,Bを確定させてから、それぞれの頂点はA,Bのうちコストの安いほうに接続すればよい。

この方法で、(1)の条件を持つ頂点が1つもなく、(2)の条件を持つ頂点があるときの答えが出せる。

このときは、(3)の条件は単なる連結性なので、最小全域木を求めるだけでよい。

この方法でO(N^2logN)で処理できる。

2番目のケースで、必ず星になると勘違いしていた人がよく見られたようである。注意すること。