1. 概要

このチュートリアルでは、無向グラフで連結成分の概念について説明します。

基本的な理解を得るためにいくつかの簡単な例を見てから、接続されたコンポーネントのプロパティをリストします。

2. 連結成分の定義

接続されたコンポーネントまたは無向グラフの単純なコンポーネントは、サブグラフであり、ノードの各ペアはパスを介して相互に接続されます。

ただし、さらに単純化してみましょう。 ノードのセットのいずれかのノードがエッジをトラバースすることによって他のノードに到達できる場合、ノードのセットは無向グラフで連結成分を形成します。 ここでの要点は到達可能性です。

接続されたコンポーネントでは、すべてのノードが常に相互に到達可能です。

3. いくつかの例

このセクションでは、いくつかの簡単な例について説明します。 例を上記の定義と関連付けてみます。

3.1. 1つの連結成分

この例では、指定された無向グラフには1つの連結成分があります。

このグラフに名前を付けましょう。 ここで、は頂点セットを示し、はのエッジセットを示します。 グラフには1つの連結成分があり、名前を付けましょう。これには、のすべての頂点が含まれています。 次に、セットが定義に準拠しているかどうかを確認しましょう。

定義によれば、セット内の頂点はパスを介して互いに到達する必要があります。 2つのランダムな頂点を選択しています：

  • 経由で到達可能です：
  • 経由で到達可能です：

頂点と定義を満たし、他の頂点ペアでも同じことができます。

3.2. 複数の連結成分

この例では、無向グラフには3つの連結成分があります。

このグラフに、、、、およびという名前を付けましょう。 グラフには、、、およびの3つの連結成分があります。

ここで、連結成分、、が定義を満たしているかどうかを見てみましょう。 、、およびセットのそれぞれからランダムにペアを選択します。

セットから、頂点とを選びましょう。

  • 経由で到達可能です：
  • 経由で到達可能です：

次に、頂点とセットから選択してみましょう。

  • に到達可能です：
  • に到達可能です：

最後に、頂点とセットから選択しましょう。

  • に到達可能です：
  • に到達可能です：

したがって、これらの簡単なデモンストレーションから、、、およびが連結成分の定義に従うことは明らかです。

4. プロパティ

すでに定義について説明し、連結成分のいくつかの例を示したので、連結成分が常に保持する重要なプロパティのいくつかをリストアップする良い機会です。

まず第一に、連結成分セットは常に空ではありません。

さらに、特定のグラフに複数の連結成分がある場合、連結成分の和集合は、特定のグラフのすべての頂点のセットを提供します。

例えば ：

   

.

最後に、連結成分セットはペアごとに互いに素です。つまり、2つの異なる連結成分セット間の交差をとると、交差は空のセットまたはnullセットに等しくなります。

グラフの連結成分をもう一度考えてみましょう。 で、このプロパティを確認しましょう。

   

5. 接続されたコンポーネントの検索

無向グラフを考えると、グラフの構造を分析するために連結成分の数を見つけることが重要です。グラフには多くの実際のアプリケーションがあります。 このタスクには、DFSまたはBFSのいずれかを使用できます。

このセクションでは、特定の無向グラフの連結成分の数を提供するDFSベースのアルゴリズムについて説明します。

*** QuickLaTeX cannot compile formula:
\begin{tikzpicture)

\begin{algorithm}[H]



\setcounter{algocf}{0}

\SetAlgoLined

\KwData{Given an undirected graph G(V, E)}

\KwResult{Number of Connected Components}

Component\_Count\ = 0;

\For {each vertex k \in V} {

Visited[k] = False;

}

\For {each vertex k \in V} {

\If{Visited[k] == False}{

DFS(V,k);

Component\_Count\ = Component\_Count\ + 1;

}

}

Print Component\_Count\;

\textbf{Procedure} DFS(V,k) {

Visited[k] = True;

\For {each vertex p \in V. Adj[k]} {

\If{Visited[p] == False}{

DFS(V,p);

}

}

\caption{Finding Connected Components using DFS}

\end{algorithm}

\end{tikzpicture}

*** Error message:
File ended while scanning use of \begin .
Missing $ inserted.
Emergency stop.

変数Component_Countは、指定されたグラフの連結成分の数を返します。

まず、すべての頂点を訪問されていないフラグに初期化します。 次に、ランダムな頂点を選択して開始し、頂点にアクセスしたかどうかを確認します。 そうでない場合は、DFS関数を呼び出します。

すべての頂点が訪問済みとしてマークされると、アルゴリズムは終了し、接続されたコンポーネントの数を出力します。

DFS関数では、渡す引数は、指定されたグラフのすべての頂点を含む頂点セットと、頂点セットに属している必要がある特定の頂点です。

まず、特定の入力頂点を訪問済みとしてマークします。 次に、指定された特定の入力頂点の隣接する頂点を計算します。 隣接する頂点ごとに、それらを訪問したかどうかを確認します。 そうでない場合は、隣接するすべての頂点を訪問済みとしてマークするまで、DFS関数を再帰的に呼び出します。

アルゴリズムで注意すべき重要な点は、接続されたコンポーネントの数が独立したDFS関数呼び出しの数に等しいことです。 Component_Count変数は呼び出しの数をカウントします。 もちろん、これには DFS（）関数で再帰的に行われる呼び出しは含まれません。

6. テスト走行

サンプルグラフでアルゴリズムを実行してみましょう。

無向グラフが与えられた場合、ここで、、および。

アルゴリズムの最初のステップは、すべての頂点を初期化し、それらを未訪問としてマークすることです。

赤い頂点は、訪問されていないことを示します。 緑の頂点は、アルゴリズムがアクセスしていることを示します。

頂点リストから任意の頂点を選択して、アルゴリズムを開始できます。 選びましょう。

アルゴリズムは、アクセスされているかどうかをチェックします。 この場合、は訪問されません。 したがって、と呼ばれます。

DFS（）内で、最初に、頂点に訪問済みのラベルを付け、の隣接する頂点を検索します。 隣接するすべての頂点も訪問済みとしてマークされます。 DFS がの隣接するすべての頂点へのアクセスを終了すると、 Component_Count は1になり、頂点のステータスが更新されます。

この場合も、アルゴリズムはランダムな頂点を選択します。 今回は選びましょう。

すでに訪問されているかどうかをチェックします。 訪問されないため、アルゴリズムはを呼び出します。 この場合も、アルゴリズムは頂点マークを訪問済みとしてマークし、 DFS は隣接する頂点を検索して、それらを訪問済みとしてマークします。 これで、 Component_Count が2になり、頂点リストのステータスが再び更新されます。

アルゴリズムは続行して、を選択し、ステータスをチェックして、を呼び出します。頂点とその隣接する頂点には、訪問済みのラベルが付けられ、Component_Countは3に増加します。 アルゴリズムは頂点リストのステータスを更新します。

最後に、アルゴリズムは、を選択して呼び出し、訪問したとおりに作成します。 頂点には隣接する頂点がないため、 DFS が返され、Component_Countが4に増加します。 最後に、アルゴリズムは頂点リストのステータスを更新します。

アルゴリズムがグラフのすべての頂点のトラバースを終了すると、アルゴリズムは終了し、 Component_Count の値を返します。これは、の連結成分の数に等しくなります。 この場合、アルゴリズムは次の4つの連結成分を検出します。

、、、、の連結成分を示すために、4つの異なる色を使用しました。

7. 時間計算量分析

特定の無向グラフで連結成分を見つけるために今見たアルゴリズムは、 DFS検索を使用し、DFS関数への呼び出しの数をカウントします。 グラフが隣接リストで表されている場合、無向グラフの場合、DFS検索はすべての頂点を1回、各エッジを2回訪問します。 頂点の状態の確認には時間がかかります。 したがって、合計すると、アルゴリズムには時間がかかります。

グラフが隣接行列で表されている場合、隣接する頂点を評価するために行全体をトラバースする必要があるため、DFS検索には時間がかかります。 頂点の状態を再度確認するには時間がかかります。 したがって、合計時間になります。

8. 結論

この記事では、連結成分の簡単な定義と、それに続くいくつかの簡単で理解しやすい例について説明しました。 また、連結成分のいくつかの一般的だが重要な特性をリストアップしました。

次に、 DFS検索ベースのアルゴリズムについて説明し、特定のグラフで連結成分の数を見つけました。 サンプルグラフを使用してアルゴリズムをデモンストレーションしました。 最後に、アルゴリズムの時間計算量を分析しました。