algorithm - 最小エッジを追加して二部グラフ SCC を作成する

Question

e ∈ E、v1 ∈ V1、v2 ∈ V2 に対して e = (v1, v2) となる 2 部グラフ B(E, V1, V2) があります。B のエッジには方向があります。

グラフ G(E ∪ E', V2 ∪ V2) を作成して、グラフ G が強連結成分であり、最小の sizeof(E') であるようにしたいと思います。(sizeof(A) はセット A の要素の数です) E' は V1 -> V2 である必要はありません。

たとえば、V1 = {1, 2, 3} および V2 = {a, b} の場合、E = {(1, a), (2, a) の 2 部グラフ B(E, V1, V2) があります。 、（２、ｂ）、（３、ｂ）｝。次に、E' = {(a, 3), (a, 1), (b, 2)} は、G(E ∪ E', V2 ∪ V2) のすべての頂点を強結合にします (頂点ペア v1 を選択するたびに、 v2、v1 から v2 へのパスが存在する)

誰かが私にアイデアを教えてもらえますか？または、これに関するよく知られたアルゴリズムはありますか?

Answer 1

EswaranとTarjanの定理によると、r個のソース（つまり、入力エッジのない頂点）とs個のシンク（つまり、出力エッジのない頂点）を持つ非巡回有向グラフは、max（r、s）エッジを追加することで強く接続できます（例を参照）。ここ）。したがって、max（sizeof（A）、sizeof（B））エッジを追加する必要があります。この本は、解決策（頂点を一致させる簡単なシステム）を見つける方法も説明しています。