グラフ理論-基本的な特性
グラフには、構造に応じてグラフの特性評価に使用されるさまざまなプロパティがあります。これらの特性は、グラフ理論の領域に関連する特定の用語で定義されています。この章では、すべてのグラフに共通するいくつかの基本的なプロパティについて説明します。
2つの頂点間の距離
これは、頂点Uと頂点Vの間の最短パス内のエッジの数です。2つの頂点を接続するパスが複数ある場合、最短パスは2つの頂点間の距離と見なされます。
表記-d（U、V）
1つの頂点から別の頂点へのパスはいくつでも存在できます。その中から、最短のものだけを選択する必要があります。
Example
次のグラフを見てください-
ここで、頂点 'd'から頂点 'e'または単に 'de'までの距離は、それらの間に1つのエッジがあるため、1です。頂点 'd'から頂点 'e'へのパスはたくさんあります-
- da、ab、be
- df、fg、ge
- de（頂点間の距離を考慮）
- df、fc、ca、ab、be
- da、ac、cf、fg、ge
頂点の離心率
頂点から他のすべての頂点までの最大距離は、頂点の離心率と見なされます。
表記-e（V）
特定の頂点からグラフ内の他のすべての頂点までの距離が取得され、それらの距離の中で、離心率が最も高い距離になります。
Example
上のグラフでは、「a」の離心率は3です。
'a'から 'b'までの距離は1（ 'ab'）、
'a'から 'c'までは1（ 'ac'）、
'a'から 'd'までは1（ 'ad'）、
'a'から 'e'は2（ 'ab'-'be'）または（ 'ad'-'de'）であり、
'a'から 'f'は2（ 'ac'-'cf'）または（ 'ad'-'df'）であり、
'a'から 'g'までは3（ 'ac'-'cf'-'fg'）または（ 'ad'-'df'-'fg'）です。
したがって、離心率は3です。これは、最大である「ag」間の距離からの頂点「a」からの最大値です。
言い換えると、
e（b）= 3
e（c）= 3
e（d）= 2
e（e）= 3
e（f）= 3
e（g）= 3
接続されたグラフの半径
すべての頂点からの最小離心率はグラフGの半径と見なされます。頂点から他のすべての頂点までのすべての最大距離の最小値は、グラフGの半径と見なされます。
表記-r（G）
グラフ内の頂点のすべての離心率から、接続されたグラフの半径は、これらすべての離心率の最小値です。
Example
上のグラフでは、r（G）= 2であり、これは「d」の最小離心率です。
グラフの直径
すべての頂点からの最大離心率はグラフGの直径と見なされます。頂点から他のすべての頂点までのすべての距離の最大値は、グラフGの直径と見なされます。
Notation − d(G) −グラフ内の頂点のすべての離心率から、接続されたグラフの直径はそれらすべての離心率の最大値です。
Example
上のグラフでは、d（G）= 3; これが最大の離心率です。
セントラルポイント
グラフの離心率がその半径に等しい場合、それはグラフの中心点として知られています。場合
e（V）= r（V）、
その場合、「V」はグラフ「G」の中心点です。
Example
グラフの例では、「d」がグラフの中心点です。
e（d）= r（d）= 2
センター
「G」のすべての中心点のセットは、グラフの中心と呼ばれます。
Example
グラフの例では、{'d'}がグラフの中心です。
周
ザ・ number of edges in the longest cycle of ‘G’ 「G」の円周と呼ばれます。
Example
グラフの例では、円周は6であり、これは最長サイクルのacfgebaまたはacfdebaから導き出されたものです。
胴回り
「G」の最短サイクルのエッジの数は、そのガースと呼ばれます。
Notation: g（G）。
Example −グラフの例では、グラフの周囲は4であり、これは最短サイクルacfdaまたはdfgedまたはabedaから導出されています。
頂点定理の次数の合計
G =（V、E）が頂点V = {V 1、V 2、… Vn }の無向グラフである場合
Corollary 1
G =（V、E）が頂点V = {V 1、V 2、… Vn }の有向グラフである場合、
Corollary 2
無向グラフでは、奇数次数の頂点の数は偶数です。
Corollary 3
無向グラフでは、各頂点の次数がkの場合、
Corollary 4
無向グラフでは、各頂点の次数が少なくともkである場合、
| Corollary 5
無向グラフで、各頂点の次数が最大でkの場合、