Graph-theory-fundamentals
グラフ理論-基礎
グラフは、ポイントとポイントに接続された線の図です。 頂点を接続せずに、2つの頂点のセットを結合する少なくとも1つの線があります。 グラフ理論におけるグラフの概念は、ポイント、ライン、頂点、エッジ、頂点の程度、グラフの特性などのいくつかの基本的な用語で成り立っています。 ここで、この章では、これらのグラフ理論の基礎について説明します。
ポイント
- ポイント*は、1次元、2次元、または3次元の空間における特定の位置です。 理解を深めるために、ポイントをアルファベットで示すことができます。 ドットで表すことができます。
例
ここで、ドットは「a」という名前のポイントです。
Line
- 線*は、2点間の接続です。 実線で表すことができます。
例
ここで、「a」と「b」がポイントです。 これらの2つのポイント間のリンクは、ラインと呼ばれます。
頂点
頂点は、複数の線が交わる点です。 また、*ノード*とも呼ばれます。 ポイントと同様に、頂点もアルファベットで示されます。
例
ここでは、頂点にはアルファベット「a」で名前が付けられています。
Edge
エッジは、2つの頂点を結ぶ線の数学用語です。 1つの頂点から多くのエッジを形成できます。 頂点がないと、エッジを形成できません。 エッジには開始頂点と終了頂点が必要です。
例
ここで、「a」と「b」は2つの頂点であり、それらの間のリンクはエッジと呼ばれます。
グラフ
グラフ「G」は、G =（V、E）として定義されます。Vはすべての頂点のセットで、Eはグラフのすべてのエッジのセットです。
例1
上記の例では、ab、ac、cd、およびbdがグラフのエッジです。 同様に、a、b、c、およびdはグラフの頂点です。
例2
このグラフには、4つの頂点a、b、c、d、および4つのエッジab、ac、ad、cdがあります。
Loop
グラフでは、エッジが頂点からそれ自体に描かれている場合、ループと呼ばれます。
例1
上記のグラフで、Vは、ループを形成するエッジ（V、V）を持つ頂点です。
例2
このグラフには、頂点aと頂点bで形成される2つのループがあります。
頂点の程度
これは、頂点Vに隣接する頂点の数です。
表記-deg（V）。
n個の頂点を持つ単純なグラフでは、頂点の次数は-
deg(v) ≤ n – 1 ∀ v ∈ G頂点は、それ自体を除き、他のすべての頂点とエッジを形成できます。 そのため、頂点の次数は、グラフ内の頂点の数から1を引いた値までです。 この1は、それ自体ではループを形成できないため、自己頂点用です。 頂点のいずれかにループがある場合、それは単純なグラフではありません。
頂点の程度は、グラフの2つのケースの下で考慮することができます-
- 無向グラフ
- 有向グラフ
無向グラフの頂点の度合い
無向グラフには有向エッジがありません。 次の例を検討してください。
例1
次のグラフを見てください-
上記の無向グラフでは、
- deg（a）=2。頂点「a」で2つのエッジが交わっています。
- deg（b）=3。頂点「b」で3つのエッジが交わっています。
- deg（c）= 1、頂点「c」に1つのエッジが形成されるため +したがって、「c」は*垂れ下がった頂点*です。
- deg（d）=2。頂点「d」で2つのエッジが交わっています。
- deg（e）=0。頂点 'e’に0個のエッジが形成されるため。 +したがって、「e」は*独立した頂点*です。
例2
次のグラフを見てください-
上記のグラフでは、
deg（a）= 2、deg（b）= 2、deg（c）= 2、deg（d）= 2、deg（e）= 0
頂点「e」は孤立した頂点です。 グラフにはペンダント頂点がありません。
有向グラフの頂点の度合い
有向グラフでは、各頂点に indegree と outdegree があります。
グラフの次数
- 頂点Vの次数は、頂点Vに入るエッジの数です。
- 表記-deg ^ − ^（V）。
グラフの次数
- 頂点Vの次数は、頂点Vから出るエッジの数です。
- 表記-deg ^＆plus; ^（V）。
次の例を検討してください。
例1
次の有向グラフをご覧ください。 頂点「a」には「ad」と「ab」の2つのエッジがあり、外側に向かっています。 したがって、その次数は2です。 同様に、頂点「a」に向かうエッジ「ga」があります。 したがって、「a」の程度は1です。
他の頂点の次数と次数は次の表に示されています-
| Vertex | Indegree | Outdegree |
|---|---|---|
| a | 1 | 2 |
| b | 2 | 0 |
| c | 2 | 1 |
| d | 1 | 1 |
| e | 1 | 1 |
| f | 1 | 1 |
| g | 0 | 2 |
例2
次の有向グラフをご覧ください。 頂点「a」には、頂点「a」から外側に向かうエッジ「ae」があります。 したがって、その次数は1です。 同様に、グラフには、頂点「a」に向かうエッジ「ba」があります。 したがって、「a」の程度は1です。
他の頂点の次数と次数は次の表に示されています-
| Vertex | Indegree | Outdegree |
|---|---|---|
| a | 1 | 1 |
| b | 0 | 2 |
| c | 2 | 0 |
| d | 1 | 1 |
| e | 1 | 1 |
ペンダント頂点
頂点の次数を使用することにより、2つの特別なタイプの頂点があります。 次数1の頂点は、ペンダント頂点と呼ばれます。
例
ここで、この例では、頂点「a」と頂点「b」には接続されたエッジ「ab」があります。 したがって、頂点「a」に関しては、頂点「b」に向かって1つのエッジのみがあり、同様に頂点「b」に関しては、頂点「a」に向かって1つのエッジしかありません。 最後に、頂点「a」と頂点「b」は、ペンダント頂点とも呼ばれる次数を持っています。
孤立した頂点
次数がゼロの頂点は、孤立頂点と呼ばれます。
例
ここで、頂点「a」と頂点「b」は相互に接続できず、他の頂点にも接続できません。 したがって、頂点「a」と「b」の両方の次数はゼロです。 これらは孤立した頂点とも呼ばれます。
隣接関係
ここに隣接関係の規範があります-
- グラフでは、2つの頂点の間にエッジがある場合、2つの頂点は*隣接*と呼ばれます。 ここでは、頂点の隣接関係は、これら2つの頂点を接続している単一のエッジによって維持されます。
- グラフでは、2つのエッジの間に共通の頂点がある場合、2つのエッジは隣接していると言われます。 ここで、エッジの隣接は、2つのエッジを接続する単一の頂点によって維持されます。
例1
上のグラフでは-
- 「a」と「b」は、それらの間に共通のエッジ「ab」があるため、隣接する頂点です。
- 「a」と「d」は隣接する頂点です。それらの間に共通のエッジ「ad」があります。
- ab」と「be」は隣接するエッジです。これらの間に共通の頂点「b」があります。
- beとdeは隣接するエッジです。それらの間に共通の頂点「e」があります。
例2
上のグラフでは-
- a」と「d」は隣接する頂点です。それらの間に共通のエッジ「ad」があるためです。
- 「c」と「b」は、それらの間に共通のエッジ「cb」があるため、隣接する頂点です。
- 「ad」と「cd」は、それらの間に共通の頂点「d」があるため、隣接するエッジです。
- acとcdは隣接するエッジです。それらの間に共通の頂点「c」があります。
平行エッジ
グラフでは、頂点のペアが複数のエッジで接続されている場合、それらのエッジは平行エッジと呼ばれます。
上記のグラフでは、「a」と「b」は、それらの間の2つのエッジ「ab」と「ab」で接続された2つの頂点です。 したがって、それは平行エッジと呼ばれます。
マルチグラフ
平行なエッジを持つグラフは、マルチグラフとして知られています。
例1
上記のグラフには、「ab」、「ac」、「cd」、「cd」、「bd」の5つのエッジがあります。 「c」と「d」の間に2つの平行なエッジがあるため、マルチグラフになります。
例2
上のグラフでは、頂点「b」と「c」には2つのエッジがあります。 頂点「e」と「d」にも2つのエッジがあります。 したがって、マルチグラフです。
グラフの次数シーケンス
グラフ内のすべての頂点の次数が降順または昇順で配置されている場合、取得されるシーケンスはグラフの次数シーケンスとして知られています。
例1
| Vertex | A | b | c | d | e |
| Connecting to | b,c | a,d | a,d | c,b,e | d |
| Degree | 2 | 2 | 2 | 3 | 1 |
上記のグラフでは、頂点\ {d、a、b、c、e}の場合、次数列は\ {3、2、2、2、1}です。
例2
| Vertex | A | b | c | d | e | f |
| Connecting to | b,e | a,c | b,d | c,e | a,d | - |
| Degree | 2 | 2 | 2 | 2 | 2 | 0 |
上記のグラフでは、頂点\ {a、b、c、d、e、f}の場合、次数列は\ {2、2、2、2、2、0}です。
