Graph-theory-trees
グラフ理論-木
ツリーは、単一のサイクルさえも含まないグラフです。 これらは、グラフィカルな形式で階層構造を表します。 ツリーは、グラフの最も単純なクラスに属します。 シンプルでありながら、豊富な構造を持っています。
ツリーは、家系図のように単純なものから、コンピューターサイエンスのデータ構造のツリーのように複雑なものまで、さまざまな有用なアプリケーションを提供します。
Tree
- 接続された非循環グラフ*はツリーと呼ばれます。 つまり、サイクルのない接続されたグラフはツリーと呼ばれます。
木の端は*枝*と呼ばれます。 木の要素は*ノード*と呼ばれます。 子ノードのないノードは*リーフノード*と呼ばれます。
「n」個の頂点を持つツリーには「n-1」個のエッジがあります。 「n-1」よりも余分なエッジが1つある場合、余分なエッジは明らかに2つの頂点とペアにする必要があり、サイクルを形成します。 次に、それはツリーグラフの違反である循環グラフになります。
例1
ここに示されているグラフは、サイクルがなく、接続されているため、ツリーです。 定義に記載されているように、4つの頂点と3つのエッジ、つまり「n」個の頂点「n-1」個のエッジがあります。
注-すべてのツリーには、1次の頂点が少なくとも2つあります。
例2
上記の例では、頂点「a」と「d」の次数は1です。 そして、他の2つの頂点「b」と「c」の次数は2です。 これは、サイクルを形成しないために、グラフ内のどこかに少なくとも2つの単一のエッジがある必要があるため可能です。 程度が1つの2つのエッジにすぎません。
森林
- 切断された非循環グラフ*はフォレストと呼ばれます。 言い換えれば、ばらばらになった木のコレクションはフォレストと呼ばれます。
例
次のグラフは、2つのサブグラフのように見えます。しかし、それは単一の切断されたグラフです。 このグラフにはサイクルはありません。 したがって、明らかに森林です。
スパニングツリー
Gを接続グラフとし、Gの部分グラフHをGのスパニングツリーと呼びます-
- Hは木です
- HにはGのすべての頂点が含まれます。
無向グラフGのスパニングツリーTは、Gのすべての頂点を含むサブグラフです。
例
上記の例では、Gは連結グラフであり、HはGのサブグラフです。
明らかに、グラフHにはサイクルがありません。これは、頂点の総数より1つ少ない6つのエッジを持つツリーです。 したがって、HはGのスパニングツリーです。
回路ランク
「G」を「n」個の頂点と「m」個のエッジを持つ接続グラフとします。 Gのスパニングツリー「T」には、（n-1）個のエッジが含まれます。
したがって、スパニングツリーを得るために「G」から削除する必要があるエッジの数= m-（n-1）であり、これはGの回線ランクと呼ばれます。
スパニングツリーでは「n-1」個のエッジが必要であるため、この式は当てはまります。 「m」個のエッジのうち、グラフに「n–1」個のエッジを保持する必要があります。
したがって、「m」から「n–1」のエッジを削除すると、スパニングツリーを取得するためにグラフからエッジが削除され、サイクルが形成されないはずです。
例
次のグラフを見てください-
上記の例のグラフでは、m = 7のエッジとn = 5の頂点があります。
次に、回路ランクは
G = m – (n – 1)
= 7 – (5 – 1)
= 3例
「G」を6つの頂点を持つ連結グラフとし、各頂点の次数は3です。 「G」の回線ランクを見つけます。
頂点の定理の合計により、
[.intsuma]# n ∑ i=1 ＃deg（V〜i〜）= 2 | E |
6×3 = 2 | E |
|E| = 9
回線ランク= | E | –（| V | – 1）
9 –（6 – 1）= 4
キルホフの定理
キルヒホッフの定理は、接続されたグラフから形成できるスパニングツリーの数を見つけるのに役立ちます。
例
マトリックス「A」は、2つの頂点の間にエッジがある場合は「1」、それ以外の場合は「0」として塗りつぶされます。
