logo

木と森

1. 木と森とは何ですか?

  • グラフ理論では、 です 無向、接続、非循環グラフ 。つまり、サイクルを 1 つも含まない接続されたグラフをツリーと呼びます。
  • ツリーは階層構造をグラフィカルな形で表します。
  • ツリーの要素はノードと呼ばれ、ツリーのエッジは枝と呼ばれます。
  • n 個の頂点を持つツリーには (n-1) 個のエッジがあります。
  • ツリーは、家系図のような単純なものから、コンピュータ サイエンスのデータ構造におけるツリーのような複雑なものまで、多くの便利なアプリケーションを提供します。
  • ツリー内の頂点は次数 1 であるか、子のない頂点はリーフと呼ばれます。

木と森

上の例では、すべての頂点が 6 個未満のツリーです。

グラフ理論では、 無向、接続されていない、非循環グラフ 。言い換えれば、ばらばらの木の集まりは森として知られています。森の各構成要素は木です。

木と森

上のグラフは 2 つの部分グラフのように見えますが、切り離された 1 つのグラフです。上のグラフにはサイクルがありません。だから森なのです。


2. 木の性質

  1. 少なくとも 2 つの頂点を持つすべての木には、少なくとも 2 つの葉が必要です。
  2. 木には多くの特徴があります。
    T を n 個の頂点を持つグラフとすると、次のステートメントは等価です。
    • Tは木です。
    • T にはサイクルが含まれず、n-1 個のエッジがあります。
    • T は接続されており、(n -1) 個のエッジがあります。
    • T は接続されたグラフであり、すべてのエッジがカットエッジです。
    • グラフ T の任意の 2 つの頂点は、正確に 1 つのパスによって接続されます。
    • T にはサイクルが含まれておらず、新しいエッジ e について、グラフ T+ e にはちょうど 1 つのサイクルがあります。
  3. 木のあらゆる端は切り取られています。
  4. ツリーに 1 つのエッジを追加すると、正確に 1 つのサイクルが定義されます。
  5. 接続されたすべてのグラフにはスパニング ツリーが含まれています。
  6. すべてのツリーには次数 2 の頂点が少なくとも 2 つあります。

3. スパニングツリー

スパニングツリー 接続されたグラフでは、G は G のすべての頂点を含む G のサブグラフ H であり、ツリーでもあります。

次のグラフ G について考えてみましょう。

木と森

上のグラフ G から、次の 3 つのスパニング ツリー H を実装できます。

木と森

スパニングツリーを見つける方法

次の 2 つの方法のいずれかを使用して、体系的にスパニング ツリーを見つけることができます。

  1. 伐採方法
  2. ビルドアップ方式

1. 伐採方法

  • グラフ G の任意のサイクルの選択を開始します。
  • サイクルのエッジの 1 つを削除します。
  • サイクルがなくなるまでこのプロセスを繰り返します。

  • グラフ G を考えてみましょう。
木と森
  • 上のグラフのサイクル a-d-c-a を破壊するエッジ ac を削除すると、次のグラフが得られます。
木と森
  • 上のグラフからサイクル a-d-c-b-a を破壊するエッジ cb を削除すると、次のグラフが得られます。
木と森
  • 上のグラフからサイクル d-e-c-d を破壊するエッジ ec を削除すると、次のスパニング ツリーが得られます。
木と森

2. ビルドアップ方法

  • グラフ G のエッジを一度に 1 つずつ選択します。このようにしてサイクルは作成されません。
  • すべての頂点が含まれるまでこのプロセスを繰り返します。

次のグラフ G を考えてみましょう。

木と森
  • エッジを選択してください 腹筋
木と森
  • エッジを選択してください
木と森
  • その後、エッジを選択します EC
木と森
  • 次にエッジを選択します CB そうすると、最終的に次のスパニング ツリーが得られます。
木と森

回路ランク

スパニング ツリーを取得するために G から削除する必要があるエッジの数。

スパニングツリー G = m-(n-1) 、と呼ばれます サーキットランク Gの

 Where, m = No. of edges. n = No. of vertices. 

木と森

上のグラフでは、エッジ m = 7、頂点 n = 5

するとサーキットランクは、

 G = m - (n - 1) = 7 - (5 - 1) = 3