[解決済み] グラフが半連結であるか否かを判定する

質問

有向グラフG＝（V，E）は、Vにおけるすべての頂点u，vの組に対して、u-> vまたはv-> uのパスを持つ場合、半連結であるという。 Gが半連結であるか否かを判定する効率的なアルゴリズムを述べよ。

どのように解決するのですか？

トリビアル O(V^3) を使用することで、解決できます。 フロイド・ウォーシャル をすべて最短パスにする必要がありますが、これは（時間の複雑さの点から）やりすぎです。

で行うことができます。 O(V+E) .

クレーム

DAGはトポロジカルソートで半連結であり、各々について i が存在し、エッジ (vi,vi+1)

証明する。

トポロジカルソートを持つDAGが与えられたとき v1,v2,...,vn :

エッジがない場合 (vi,v(i+1)) いくつかの i というパスも存在しない。 (v(i+1),vi) (DAGのトポロジー的なものなので)、グラフは半連結ではありません。

もし、すべての i というエッジがあります。 (vi,vi+1) であれば、各 i,j (i < j)のパスが存在します。 vi->vi+1->...->vj-1->vj となり、グラフは半連結となる。

これより、アルゴリズムを求めることができる。

1. グラフ内の最大SCCを探す。
2. 次のようなSCCグラフG'=(U,E')を構築する。 U はSCCの集合である。 E'= { (V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E } .
3. G'のトポロジカルソートを行う。
4. すべてのiについて、エッジVi,V(i+1)があるかどうかをチェックする。

正しさの証明。

グラフが半連結である場合、あるペアに対して (v1,v2) が存在する場合、そのようなパスは v1->...->v2 - そのSCCをV1, V2とする。V1 と V2 のすべてのノードが強く結ばれているので、V1 から V2、ひいては v1 から v2 への経路が存在する。

このアルゴリズムが真を得た場合、任意の2つのノードv1, v2について、それらがSCC V1, V2内にあることがわかる。V1からV2へのパスがあり（一般性を損なわず）、したがってv1からv2へのパスもある。

余談ですが、すべての半連結グラフにもルート（頂点 r すべての頂点につながる)。

証明する。
ルートが存在しないと仮定する。定義 #(v) = |{u | there is a path from v to u}| (からのパスを持つノードの数）。 v を含む)。
選ぶ a そのような #(a) = max{#(v) | for all v} .
a はルートではないので、何らかのノード u からのパスを持たない a になります。グラフは半連結なので、このグラフから u->...->a . しかし、それはつまり #(u) >= #(a) + 1 (から到達可能なすべてのノード）。 a で、さらに u ).
の最大性とは矛盾する。 #(a) したがって、ルートが存在する。