1. 概要

グラフ理論では、ツリーはグラフの特殊なケースです。 このチュートリアルでは、特定のグラフがツリーを形成するかどうかを確認する方法を説明します。

木の概念と、グラフが木を形成することの意味について説明します。

また、有向グラフと無向グラフの両方について説明します。 最後に、両方の場合のステップ間の簡単な比較を示します。

2. ツリーの定義

次の条件が満たされる場合、グラフはツリーを形成すると言います。

  1. ツリーには、ツリーのルートと呼ばれる単一のノードが含まれています。 したがって、選択したルートからツリーをトラバースし始めた後に到達した場合、ノードはノードの親であると言います。 同様に、それはの子であると言います。 ツリーのルートとして複数のノードを選択できることは注目に値します。
  2. ルートを除く各ノードには、単一の親が必要です。 つまり、ルートから開始してツリーをトラバースする場合、各ノードにはその親からのみ到達する必要があります。
  3. ルートから始めて、ツリーのすべてのノードにアクセスできる必要があります。 したがって、ツリーは常に接続されている必要があります。

ただし、これらの条件をチェックするプロセスは、有向グラフと無向グラフの場合で異なります。 したがって、各グラフタイプのアルゴリズムについて個別に説明します。

3. 有向グラフ

3.1. 手順の確認

有向グラフの場合、一連の手順を実行する必要があります。

  1. ツリーのルートを見つけます。これは、入力エッジのない頂点です。 ノードが存在しない場合は、を返します。 複数のノードが存在する場合、グラフは接続されていないため、同様に戻る必要があります。
  2. DFSを実行して、各ノードに親が1つだけあることを確認します。 そうでない場合は、を返します。
  3. すべてのノードが訪問されていることを確認してください。 DFSチェックがすべてのノードにアクセスしなかった場合は、を返します。
  4. それ以外の場合、グラフはツリーです。

3.2. チェックアルゴリズム

有向グラフがツリーであるかどうかを確認するためのアルゴリズムを見てみましょう。

まず、すべてのエッジを反復処理し、各エッジ（）の終了ノードの入力エッジの数を1つ増やします。 次に、入力エッジがないルートノードを見つけます（ステップ1）。

その後、DFSチェック（ステップ2）を実行して、各ノードに1つの親があることを確認します（関数については、以下のセクションを参照してください）。 開始するルートノードと、値で満たされた配列を渡します。 関数がを返す場合、アルゴリズムも返す必要があります。

最後に、関数からすべてのノードが訪問済みとしてマークされていることを確認します（ステップ3）。 DFSチェックがいくつかのノードを訪問済みとしてマークせずに残した場合、を返します。 それ以外の場合は、を返します。

説明したアルゴリズムの複雑さはです。ここで、は頂点の数であり、はグラフ内のエッジの数です。

3.3. DFSチェック

各ノードに親が1つだけあることを確認するために、DFSチェックを実行します。 アルゴリズムを見てみましょう。

まず、以前に現在のノードにアクセスしたことがあるかどうかを確認します。 もしそうなら、私たちは戻ります。 それ以外の場合は、このノードを訪問済みとしてマークします。

次に、現在のノードのすべての子を反復処理し、子ごとに関数を再帰的に呼び出します。 子が関数にを返すようにした場合、すぐにを返します。 それ以外の場合、関数はを返します。

このアルゴリズムの複雑さはです。ここで、は頂点の数であり、はグラフ内のエッジの数です。

4. 無向グラフ

4.1. 手順の確認

無向グラフの場合、次の3つのステップを実行します。

  1. 任意のノードからDFSチェックを実行して、各ノードに親が1つだけあることを確認します。 そうでない場合は、を返します。
  2. すべてのノードが訪問されていることを確認します。 DFSチェックですべてのノードにアクセスできなかった場合は、を返します。
  3. それ以外の場合、グラフはツリーです。

4.2. チェックアルゴリズム

無向グラフがツリーであるかどうかを確認するアルゴリズムを検討してください。

まず、関数を呼び出し（ステップ1）、ルートノードをインデックス1のノードとして渡します。 また、親ノードを-1として渡します。これは、ルートに親ノードがないことを示します。 値で満たされた配列も渡します。 この関数のアルゴリズムについては、次のセクションで説明します。

関数がを返す場合、アルゴリズムはを返す必要があります。 それ以外の場合は、すべてのノードがアクセスされていることを確認します（ステップ2）。 DFSチェックが一部のノードにアクセスしなかった場合は、を返します。

最後に、上記のすべての条件が満たされた場合、を返します。

記述されたアルゴリズムの複雑さはです。ここで、は頂点の数であり、はグラフ内のエッジの数です。

4.3. DFSチェック

無向グラフのDFSチェックアルゴリズムを見てみましょう。

アルゴリズムは、有向グラフについて上で説明したものとかなり似ています。 まず、現在のノードが以前にアクセスされたことがあるかどうかを確認します。 もしそうなら、私たちはすぐに戻ります。 それ以外の場合は、現在のノードを訪問済みとしてマークします。

次に、現在のノードの子を繰り返し処理し、子ごとに関数を再帰的に呼び出します。 ただし、無向グラフの場合、親からのエッジは双方向のエッジです。

したがって、親をの子ノードとして取得します。 この場合、親ノードを無視し、再訪しないでください。 これは、親が2回訪問されたが、訪問されていないことをアルゴリズムが認識できるようにするためです。

説明したアルゴリズムの複雑さも同様です。ここで、は頂点の数であり、はグラフ内のエッジの数です。

5. 比較

有向グラフと無向グラフの両方のステップを簡単に比較してみましょう。

6. 結論

このチュートリアルでは、グラフがツリーを形成するかどうかを確認する方法について説明しました。 まず、グラフがツリーを形成するための一般的な条件を示しました。 次に、有向グラフと無向グラフの両方と、それらがツリーを形成しているかどうかを確認する方法について説明しました。

最後に、2つのケースの簡単な比較を行いました。