接続性、距離、およびスパニングツリー

スパニングツリー

簡単な定義の1つは、ツリーはサイクルに関連付けられていない連結グラフであり、サイクルでは、エッジを繰り返さずにノードからそれ自体に移動できます。

連結グラフGの全域木は、Gのすべての頂点を含む木として定義されます。

スパニングツリーは、インターネットルーティングアルゴリズム用に実装されることがよくあります。インターネットでは、コンピューター（ノード）は多くの場合、多くの冗長な物理接続で接続されています。

グラフ内のスパニングツリーの総数。グラフがnなしの完全グラフである場合。頂点の数の場合、スパニングツリーの総数はn（n-2）

ここで、nはグラフ内のノードの数として示されます。完全グラフでは、タスクは、ケイリーの公式を持つn個のノードを持つさまざまなラベル付きツリーをカウントすることと同じです。

接続性

数学とコンピュータサイエンスでは、接続性はグラフ理論の基本概念の1つです

残りのノードを分離されたサブグラフに分離するために削除する必要のある要素（ノードまたはエッジ）の最小数が必要です。

これは、ネットワークフローの問題の理論と密接に関連しています。

このグラフは、破線のエッジが削除されると切断されます。

頂点接続。グラフの頂点連結性は、削除によってグラフが切断されるノードの少なくとも数です。

頂点接続は、「ポイント接続」または単に「接続」と呼ばれることもあります。

エッジ接続。グラフからの削除が切断されたエッジの少なくとも数。ライン接続とも呼ばれます。

切断されたグラフのエッジ接続は0ですが、グラフブリッジに関連付けられた接続されたグラフのエッジ接続は1です。

距離

2つのノード間の距離は、最も低い共通の祖先で計算できます。計算式は次のとおりです。

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca)
'd1' and 'd2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of d1 and d2
Dist(d1, d2) is the distance between d1 and d2.