1. 木と森とは何ですか?
木
- グラフ理論では、 木 です 無向、接続、非循環グラフ 。つまり、サイクルを 1 つも含まない接続されたグラフをツリーと呼びます。
- ツリーは階層構造をグラフィカルな形で表します。
- ツリーの要素はノードと呼ばれ、ツリーのエッジは枝と呼ばれます。
- n 個の頂点を持つツリーには (n-1) 個のエッジがあります。
- ツリーは、家系図のような単純なものから、コンピュータ サイエンスのデータ構造におけるツリーのような複雑なものまで、多くの便利なアプリケーションを提供します。
- あ 葉 ツリー内の頂点は次数 1 であるか、子のない頂点はリーフと呼ばれます。
例
上の例では、すべての頂点が 6 個未満のツリーです。
森
グラフ理論では、 森 は 無向、接続されていない、非循環グラフ 。言い換えれば、ばらばらの木の集まりは森として知られています。森の各構成要素は木です。
例
上のグラフは 2 つの部分グラフのように見えますが、切り離された 1 つのグラフです。上のグラフにはサイクルがありません。だから森なのです。
2. 木の性質
- 少なくとも 2 つの頂点を持つすべての木には、少なくとも 2 つの葉が必要です。
- 木には多くの特徴があります。
T を n 個の頂点を持つグラフとすると、次のステートメントは等価です。- Tは木です。
- T にはサイクルが含まれず、n-1 個のエッジがあります。
- T は接続されており、(n -1) 個のエッジがあります。
- T は接続されたグラフであり、すべてのエッジがカットエッジです。
- グラフ T の任意の 2 つの頂点は、正確に 1 つのパスによって接続されます。
- T にはサイクルが含まれておらず、新しいエッジ e について、グラフ T+ e にはちょうど 1 つのサイクルがあります。
- 木のあらゆる端は切り取られています。
- ツリーに 1 つのエッジを追加すると、正確に 1 つのサイクルが定義されます。
- 接続されたすべてのグラフにはスパニング ツリーが含まれています。
- すべてのツリーには次数 2 の頂点が少なくとも 2 つあります。
3. スパニングツリー
あ スパニングツリー 接続されたグラフでは、G は G のすべての頂点を含む G のサブグラフ H であり、ツリーでもあります。
例
次のグラフ G について考えてみましょう。
上のグラフ G から、次の 3 つのスパニング ツリー H を実装できます。
スパニングツリーを見つける方法
次の 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