弱いコンポーネント

グラフ理論 では、有向グラフの弱成分はグラフの頂点を到達可能性によって完全に順序付けられたサブセットに分割します。これらは、このように完全に順序付けられた頂点の集合の最も細かい分割を形成します。

弱成分は、ロナルド・グラハム、ドナルド・クヌース、そして（死後に）セオドア・モツキンによって1972年の論文で、有向グラフの強連結成分に倣って定義されました。強連結成分は、グラフの頂点を到達可能性によって部分的に順序付けられたサブセットに可能な限り細かく分割するものです。代わりに、彼らは弱成分を、頂点を到達可能性によって完全に順序付けられたサブセットに可能な限り細かく分割するものと定義しました。^{[1] [2]}

より詳細には、Knuth (2022) は、任意の有向グラフの頂点上の 4 つの対称関係(ここでは 、、、と表記)の組み合わせを通じて弱成分を定義します。${\displaystyle \Leftrightarrow}$ ${\displaystyle \parallel}$ ${\displaystyle \approx}$ ${\displaystyle \asymp}$

• グラフの任意の2 つの頂点とについて、各頂点が他方から到達可能である場合に限り、グラフにはから へのパスと から へのパスが存在します。関係は同値関係であり、その同値類はグラフの強く連結されたコンポーネントを定義するために使用されます。${\displaystyle u}$${\displaystyle v}$${\displaystyle u\Leftrightarrow v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$ ${\displaystyle u}$${\displaystyle \Leftrightarrow}$
• グラフの任意の 2 つの頂点とについて、どちらの頂点も他方から到達できない場合に限り、グラフにはと の間のいずれの方向にもパスは存在しません。${\displaystyle u}$${\displaystyle v}$${\displaystyle u\parallel v}$${\displaystyle u}$ ${\displaystyle v}$
• グラフの任意の2 つの頂点およびについて、 またはである場合に限ります。つまり、これらの頂点間には双方向の接続がある場合もあれば、相互に到達できない場合もありますが、一方向の接続は存在しない可能性があります。${\displaystyle u}$${\displaystyle v}$${\displaystyle u\approx v}$${\displaystyle u\Leftrightarrow v}$ ${\displaystyle u\parallel v}$
• 関係はの推移閉包として定義されます。つまり、 で始まり で終わる頂点のシーケンスがあり、シーケンス内の連続する各ペアが によって関連付けられている場合です。${\displaystyle \asymp}$ ${\displaystyle \approx}$${\displaystyle u\asymp v}$${\displaystyle u\approx \cdots \approx v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \approx}$

は同値関係です。つまり、すべての頂点はによって自分自身と関連しています（長さ 0 のパスで両方向に自分自身に到達できるため）、 によって関連付けられている任意の 2 つの頂点は、この関係を変更することなく互いに交換できます（対称関係とから構築されているため）、は推移的な関係です（推移的な閉包であるため）。他の同値関係と同様に、 はグラフの頂点を同値クラスに分割するために使用できます。同値クラスは、2 つの頂点が同じ同値クラスに属する場合にのみ によって関連付けられる頂点のサブセットです。これらの同値クラスは、指定されたグラフの弱いコンポーネントです。^[2]${\displaystyle \asymp}$${\displaystyle \asymp}$${\displaystyle \asymp}$${\displaystyle \asymp}$${\displaystyle \Leftrightarrow}$ ${\displaystyle \parallel}$${\displaystyle \asymp}$${\displaystyle \asymp}$

グラハム、クヌース、モツキンによる元の定義は同等ですが、定式化が多少異なります。有向グラフ が与えられた場合、彼ら${\displaystyle G}$はまず の推移閉包の補グラフとして別のグラフを構築します。Tarjan ( 1974 )が述べているように、 の辺は非パス、つまり内のパスによって接続されていない頂点のペアを表します。^[3]次に、2 つの頂点が同じ弱成分に属するのは、それらがまたはの同じ強連結成分に属している場合です。^{[1] [3]}グラハム、クヌース、モツキンが示すように、この条件は同値関係^[1]を定義します。これは上で として定義したものと同じです。^[4]${\displaystyle {\hat {G}}}$ ${\displaystyle G}$${\displaystyle {\hat {G}}}$${\displaystyle G}$${\displaystyle G}$${\displaystyle {\hat {G}}}$${\displaystyle \asymp}$

これらの定義に対応して、有向グラフが弱連結であるとは、弱コンポーネントを 1 つだけ持つ場合である。これは、その頂点を 2 つのサブセットに分割できず、最初のサブセットのすべての頂点が 2 番目のサブセットのすべての頂点に到達できるが、2 番目のサブセットのどの頂点も最初のサブセットのどの頂点にも到達できないことを意味する。これは、基礎となる無向グラフの連結性やコンポーネントなど、文献に出てくる他の弱連結性の概念とは異なる。無向グラフに対して、Knuth は無向コンポーネントという別の用語を提案している。^[2]

と が有向グラフの2つの弱成分である場合、 のすべての頂点がグラフのパスによって のすべての頂点に到達できるか、 のすべての頂点が のすべての頂点に到達できるかのどちらかです。しかし、これら2つの成分の間には、両方向の到達可能性関係は存在できません。したがって、のすべての頂点がのすべての頂点に到達できる場合、 となる弱成分の順序付けを定義できます。定義により、となります。これは非対称関係（2つの要素は一方向にのみ関連付けられ、他の方向には関連付けられていない）であり、到達可能性の推移性から推移関係であるという特性を継承しています。したがって、これは弱成分の全順序付けを定義します。これは、到達可能性と一致する、頂点を完全に順序付けされたセットに頂点を可能な限り細かく分割したものです。^[1]${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X<Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\nless X}$

弱い成分上のこの順序は、頂点自体の弱い順序として解釈することもできます。弱い順序では、から へのパスは必ず存在しますが、からへのパスは存在しないという性質があります。しかし、これはこの弱い順序の完全な特徴付けではありません。なぜなら、2つの頂点 とは、互いに同じ弱い成分に属しながら、この同じ到達可能性順序を持つことができるからです。^[2]${\displaystyle u<v}$${\displaystyle u}$ ${\displaystyle v}$${\displaystyle v}$ ${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$

すべての弱い成分は、強く連結された成分の和集合である。^[2]任意のグラフの強く連結された成分を単一の頂点に縮約して有向非巡回グラフ（与えられたグラフの凝縮）を生成し、この凝縮を位相的にソートすると、各弱い成分は必然的に強い成分の位相的順序の連続した部分列として現れる。^[3]

与えられた有向グラフの弱成分を線形時間で計算するアルゴリズムはPacault (1974) によって記述され、その後 Tarjan (1974) とKnuth (2022) によって簡略化されました。^{[2] [3] [5]} Tarjan が指摘しているように、深さ優先探索に基づくTarjan の強連結成分アルゴリズムは、強連結成分を位相的にソートされた順序 (の逆) で出力します。弱成分のアルゴリズムは、この順序で強連結成分を生成し、これまでに生成された成分を誘導サブグラフの弱成分に分割します。すべての成分が生成された後、この分割はグラフ全体の弱成分を記述します。^{[2] [3]}

現在の弱いコンポーネントへの分割をスタックに保持すると便利です。各弱いコンポーネントは、さらにそのソースのリストも保持します。ソースとは、同じ弱いコンポーネント内の他の強く接続されたコンポーネントからの入力エッジを持たない強く接続されたコンポーネントで、最も最近生成されたソースが最初になります。新しく生成された各強く接続されたコンポーネントは、それ自体で新しい弱いコンポーネントを形成する場合もあれば、スタックの上部近くにある以前に構築された弱いコンポーネントの一部とマージされる場合もあります。これらのコンポーネントは、すべてのソースに到達できないものです。^{[2] [3]}

したがって、アルゴリズムは次のステップを実行します。^{[2] [3]}

• 弱いコンポーネントの空のスタックを初期化します。各コンポーネントはソース コンポーネントのリストに関連付けられています。
• Tarjan の強く連結されたコンポーネント アルゴリズムを使用して、指定されたグラフの強く連結されたコンポーネントをトポロジカル順序の逆順に生成します。各強く連結されたコンポーネントが生成されたら、それに対して次の手順を実行します。 ${\displaystyle S}$
  • スタックが空でなく、スタックの最上位の弱いコンポーネントへのエッジがない場合、そのコンポーネントをスタックからポップします。${\displaystyle S}$
  • スタックがまだ空でなく、その最上位の弱いコンポーネントのソースの一部がからのエッジにヒットしない場合は、${\displaystyle S}$そのコンポーネントを再度スタックからポップします。
  • ソース と、ポップされた最上位コンポーネントからのヒットしていないすべてのソースを含む新しい弱いコンポーネントを構築し、${\displaystyle W}$スタックにプッシュします。${\displaystyle S}$${\displaystyle W}$

から最も最近生成された以前の強く接続されたコンポーネントへのエッジが見つかると、そのエッジのターゲット コンポーネントをスタック上の上から 2 番目のコンポーネントの最初のソースと比較することによって、からのエッジが弱いコンポーネントにヒットするかどうかの各テストを一定時間で実行できます。 ${\displaystyle S}$${\displaystyle S}$