1. 概要

このチュートリアルでは、アーティキュレーションポイントとそれらをグラフで見つける方法について説明します。

2. 意味

頂点と関連するエッジを削除するとグラフが切断される場合、頂点はグラフの関節点であると言われます。 したがって、アーティキュレーションポイントを削除すると、グラフ内の連結成分の数が増加します。

アーティキュレーションポイントは、カット頂点と呼ばれることもあります。

ここでの主な目的は、グラフ内のすべてのアーティキュレーションポイントを見つけることです。

3. 例

無向グラフを取り、定義に従うだけでアーティキュレーションポイントを見つけてみましょう。

ここに、頂点セットとエッジセットを含むグラフがあります。 頂点から始めて、頂点とそれに関連するエッジを削除するとグラフが切断されるかどうかを確認しましょう。

この場合、頂点と関連するエッジを削除しても、グラフは切断されません。 したがって、これは明確なポイントではありません。

しかし、頂点とそれに関連するエッジ、、、を試してみましょう。 これにより、グラフが2つの連結成分に分割されます。

  • 頂点セットとエッジセットを持つ最初のコンポーネント
  • 頂点セットとエッジセットを持つ2番目のコンポーネント

したがって、削除は関節点の定義を満たします。 したがって、vertexはのアーティキュレーションポイントです。

4. すべてのアーティキュレーションポイントを見つけるアルゴリズム

このセクションでは、特定のグラフ内のすべてのアーティキュレーションポイントを見つけることができるアルゴリズムを紹介します。

これは、深さ優先探索（DFS）ベースのアルゴリズムであり、グラフ内のすべてのアーティキュレーションポイントを検索します。 グラフが与えられると、アルゴリズムは最初にDFSツリーを構築します。

最初に、アルゴリズムは任意のランダムな頂点を選択してアルゴリズムを開始し、そのステータスを訪問済みとしてマークします。 次のステップは、選択した頂点の深さを計算することです。各頂点の深さは、それらが訪問される順序です。

次に、最小の検出数を計算する必要があります。これは、DFSツリーの1つのバックエッジを考慮して、任意の頂点から到達可能な頂点の深さに等しくなります。 がエッジの祖先であるがDFSツリーの一部ではない場合、エッジはバックエッジです。 ただし、エッジは元のグラフの一部です。

最初に選択された頂点の深度と最小検出数を計算した後、 アルゴリズムは、隣接する頂点を検索します。隣接する頂点がすでにアクセスされているかどうかをチェックします。 そうでない場合、アルゴリズムはそれを現在の頂点としてマークし、その深さと最小の検出数を計算します。

すべての頂点の深さと最小検出数を計算した後、アルゴリズムは頂点のペアを取得し、そのアーティキュレーションポイントかどうかをチェックします。2つの頂点とを取得しましょう。 さらに、は親であり、子の頂点であると考えています。 の最小検出数がの深さ以上の場合、はアーティキュレーションポイントです。

ルートがアーティキュレーションポイントである場合の特殊なケースが1つあります。ツリーに複数の子がある場合に限り、ルートはアーティキュレーションポイントです。 そのため、アルゴリズムにチェック条件を設定して、ツリーのルートを識別します。

5. グラフでのアルゴリズムの実行

このセクションでは、グラフを取得し、グラフ上でアルゴリズムを実行して、アーティキュレーションポイントを見つけます。

次に、グラフをDFSツリーに変換します。 頂点から開始して、頂点にアクセスしながらツリーを構築します。

この場合、頂点から始めて、頂点にアクセスしました。 頂点の後で戻って、に隣接する頂点があるかどうかを確認しますが、ない場合は確認します。

同様に、をチェックします。 頂点には隣接する頂点がありますが、これはツリーに含まれていません。 したがって、頂点を含めます。 この時点で、DFSツリーの構築は完了です。

頂点からとへの2つの点線のエッジがあることに注意してください。 これらはバックエッジであり、DFSツリーの一部ではありません。

次に、すべての頂点の深度と最小検出数を計算します。

各頂点の深さ数は、DFSツリーでアクセスされるときに計算されます。 たとえば、頂点には深さ番号があり、アルゴリズムがDFSツリーで最初に頂点にアクセスすることを示します。 同様に、頂点の深度番号はです。 これは、頂点がアルゴリズムがDFSツリーにアクセスした2番目の頂点であることを示しています。

アルゴリズムが各頂点の最小検出数を計算する方法について話しましょう。 ルールは単純です。後端で到達可能な頂点を検索し、この後端がどの頂点に到達するかを確認します。 現在の頂点の最小検出数は、後端が着地する頂点の深さに等しくなります。

頂点の最小検出数を計算するとします。 隣接する頂点はですが、バックエッジはありません。 したがって、検索は続行され、頂点に到達します。 頂点にはバックエッジがあり、頂点に接続します。 の最小検出数は、の深さに等しくなります。 したがって、の最小検出数はです。

同様の方法で、DFSツリー内の他のすべての頂点の最小検出数を計算できます。

ここで、アーティキュレーションポイントを見つけるために、DFSツリーに従っての親である頂点のペアを取得する必要があります。 がの親である頂点のランダムなペアから始めましょう。

  • 状態の確認：

したがって、ここには明確なポイントはありません。 次に、の親である別のペアを見てみましょう。

  • 状態の確認：
  • 状態確認2：

したがって、頂点はグラフのアーティキュレーションポイントであると結論付けることができます。

このようにして、任意のグラフ内のすべてのアーティキュレーションポイントを見つけることができます。

6. 時間計算量分析

アルゴリズムは主に、いくつかの追加手順を伴うDFS検索を使用します。 したがって、基本的に、このアルゴリズムの時間計算量は、DFSアルゴリズムの時間計算量と同じです。

与えられたグラフが隣接リストを使用する場合、DFSアルゴリズムの時間計算量はになります。 したがって、このアルゴリズムの全体的な時間計算量はです。

7. アプリケーション

アーティキュレーションポイントの概念は、ネットワークでは非常に重要です。 接続されたネットワークにアーティキュレーションポイントが存在することは、リスクと脆弱性が高いことを示しています。 接続されたネットワークにアーティキュレーションポイントがある場合、単一ポイント障害はネットワーク全体を切断します。

コンピュータサイエンスでは、一般的な問題の1つは、ソース頂点からシンク頂点に流れるフローの最大量を見つけることです。 この問題は、最大フロー最小カット定理として知られています。 ここでは、アーティキュレーションポイントの概念を使用して解決策を見つけます。

8. 結論

このチュートリアルでは、グラフ内のすべてのアーティキュレーションポイントを見つけるためのDFSベースのアルゴリズムを紹介しました。

また、アルゴリズムを検証するための例を示し、アーティキュレーションポイントのいくつかのアプリケーションについて説明しました。