この有向グラフの 5 つのノード。
エッジ:
1 -> 2
2 -> 3
2 -> 4
4 -> 5
(グラフィックイメージ: http://i.imgur.com/hafBv.jpg )
関節点はノード 2 と 4 であると考えてよろしいですか? (ノード 2 またはノード 4 を削除すると、グラフが切断されます)
しかし、私がどこでも見た定義は、次のようなことを言っています:
ノード u は、u のすべての子 v について、v から DFS ツリー内で u より上位のノードへのバック エッジがない場合、アーティキュレーション ポイントです。
これは有向グラフに対してどのように機能しますか? たとえば、ノード 3 には、DFS ツリーで 2 より上位のノードへのバック エッジがありません。これは、ノード 3 をアーティキュレーション ポイントとして分類しますか? しかし、それを削除しても、グラフが 2 つ以上の部分に分割されることはありません (これがアーティキュレーション ノードの私の素人の定義です)。
免責事項: 私の記憶は曖昧です。
有向グラフには 3 種類の接続性があります。
すべての頂点から他のすべての頂点へのパスがある場合は「強く接続されている」、任意の 2 つのノード間にパスが存在する場合は「接続済み」ですが、両方向ではありません。アークが無向アークに置き換えられた場合にのみグラフが接続される場合は、「弱接続」。
例: 1->2 , 2->3 , 3->1 強く接続されているため、すべてのノードから他のすべてのノードに移動できます
1->2 , 2->3 3から1にはならないけど1から3にはできるから繋がってる
1->2 , 3->2 1 から 3 または 3 から 1 を取得する方法がないため、弱く接続されているだけです。
どのノードが関節点になるかは、検討している接続の種類によって異なります。
3 から 4 または 4 から 3 に到達する方法がないため、グラフは弱くしか接続されていません。これは、アーティキュレーション ポイントについて話すのが理にかなっている唯一の方法は、アークを無向として扱う場合であることを意味します。その場合、あなたが言ったように、2 と 4 がアーティキュレーション ポイントになります。
しかし、無向グラフを解くために使用した方法に従うと、ノードの尊重された (num,low) 値は node-1(1,1) 2 (2,2) 、ノード 3 (3,3)、ノード4(4,4). ノード 5(5,5). したがって、関節点の定義に従い、2 つの子を持つノードを見つけ、ルール (low(child)>=num(node)) を満たすと、ノード 2 のみが取得されるため、それが関節点です。しかし、それはまだ接続されたグラフであるため、つまりすべてのノードに到達できるため、理論を適用できますが、見つけたときにツリーとバックエッジに注意する必要があり、残りは無向グラフと同じです。
Node 3 does not have a back edge to a node higher in the DFS tree than 2
ノード 3 には子がないため、(def から) アーティキュレーション ポイントにすることはできません。この定義を有向木の文脈に置くと、関節点は根と葉ノードを除くすべての点になります。
関節点には常に子と親が必要です。これはあなたの定義に欠けているものであり、ノード 1 と 3 の関節点を作成しますが、そうではありません。
また、ノード 3 の理由付けでは、ノード自体をその子ではないと見なすことに注意してください。定義を注意深く適用すると、代わりに子を考慮する必要があることがわかります。あなたの場合-空のセットであり、私が拡張した定義では、3はもはやアーティキュレーションポイントではありません。
