グラフ理論-木

ツリーは、1つのサイクルも含まないグラフです。これらは、階層構造をグラフィック形式で表します。ツリーは、最も単純なクラスのグラフに属します。それらの単純さにもかかわらず、それらは豊かな構造を持っています。

ツリーは、家系図のように単純なものから、コンピュータサイエンスのデータ構造のツリーのように複雑なものまで、さまざまな便利なアプリケーションを提供します。

木

A connected acyclic graph木と呼ばれます。言い換えれば、サイクルのない接続されたグラフはツリーと呼ばれます。

木の端はとして知られています branches。ツリーの要素はノードと呼ばれます。子ノードのないノードは呼び出されますleaf nodes。

頂点が「n」のツリーには、エッジが「n-1」です。'n-1'よりも1つ多いエッジがある場合、余分なエッジは明らかに2つの頂点とペアになって、サイクルを形成する必要があります。すると、ツリーグラフに違反する閉路グラフになります。

Example 1

ここに示されているグラフは、サイクルがなく、接続されているため、ツリーです。これには、4つの頂点と3つのエッジがあります。つまり、定義で説明されているように、「n」頂点の場合は「n-1」エッジです。

Note −すべてのツリーには、次数1の頂点が少なくとも2つあります。

Example 2

上記の例では、頂点「a」と「d」の次数は1です。そして、他の2つの頂点「b」と「c」の次数は2です。これが可能なのは、サイクルを形成しないために、グラフのどこかに少なくとも2つの単一のエッジが存在する必要があるためです。これは、次数が1の2つのエッジに他なりません。

森林

A disconnected acyclic graph森と呼ばれています。言い換えれば、ばらばらの木の集まりは森と呼ばれます。

Example

次のグラフは、2つのサブグラフのように見えます。しかし、それは単一の切断されたグラフです。このグラフにはサイクルはありません。したがって、明らかにそれは森です。

スパニングツリー

Gを連結グラフとすると、Gの部分グラフHは、次の場合にGの全域木と呼ばれます。

Hは木です
HにはGのすべての頂点が含まれます。

無向グラフGの全域木Tは、Gのすべての頂点を含む部分グラフです。

Example

上記の例では、Gは連結グラフであり、HはGのサブグラフです。

明らかに、グラフHにはサイクルがなく、頂点の総数より1つ少ない6つのエッジを持つツリーです。したがって、HはGのスパニングツリーです。

回路ランク

「G」を「n」個の頂点と「m」個のエッジを持つ連結グラフとします。Gの全域木「T」には（n-1）個のエッジが含まれます。

したがって、スパニングツリー= m-（n-1）を取得するために、「G」から削除する必要のあるエッジの数。これは、Gの回路ランクと呼ばれます。

スパニングツリーでは「n-1」のエッジが必要なため、この式は真です。'm'エッジのうち、 'n–1'エッジをグラフに保持する必要があります。

したがって、「m」から「n–1」のエッジを削除すると、循環を形成してはならないスパニングツリーを取得するためにグラフからエッジが削除されます。

Example

次のグラフを見てください-

上記の例のグラフでは、m = 7のエッジとn = 5の頂点があります。

その場合、回路ランクは−です。

G = m –（n – 1）

= 7 –（5 – 1）

= 3

Example

'G'を6つの頂点を持つ連結グラフとし、各頂点の次数は3です。'G'の回路ランクを見つけます。

頂点の次数の定理の合計により、

n Σ i=1deg（V _i）= 2 | E |

6×3 = 2 | E |

| E | = 9

回路ランク= | E | –（| V | – 1）

= 9 –（6 – 1）= 4

キルヒホッフの定理

キルヒホッフの定理は、接続されたグラフから形成できる全域木の数を見つけるのに役立ちます。

Example

行列「A」は、2つの頂点の間にエッジがある場合は「1」、それ以外の場合は「0」として入力する必要があります。

$$ A = \ begin {vmatrix} 0＆a＆b＆c＆d \\ a＆0＆1＆1＆1 \\ b＆1＆0＆0＆1 \\ c＆1＆0＆0＆ 1 \\ d＆1＆1＆1＆0 \ end {vmatrix} = \ begin {vmatrix} 0＆1＆1＆1 \\ 1＆0＆0＆1 \\ 1＆0＆0＆1 \\ 1＆1＆1＆0 \ end {vmatrix} $$

キルヒホッフの定理を使用することにより、主な対角値を頂点の次数に置き換え、他のすべての要素を-1.Aに置き換えるように変更する必要があります。

$$ = \ begin {vmatrix} 3＆-1＆-1＆-1 \\-1＆2＆0＆-1 \\-1＆0＆2＆-1 \\-1＆-1＆-1 ＆3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3＆-1＆-1＆-1 \\-1＆2＆0＆-1 \\-1＆0＆2＆ -1 \\-1＆-1＆-1＆3 \ end {vmatrix} = 8 $$ $$ Co \：\：factor \：\：of \：\：m1 \：\：= \ begin {vmatrix } 2＆0＆-1 \\ 0＆2＆-1 \\-1＆-1＆3 \ end {vmatrix} $$

したがって、スパニングツリーの数= 8です。