Graph-theory-quick-guide

グラフ理論-はじめに

数学とコンピューターサイエンスの領域では、_グラフ理論とは、エッジと頂点の関係に関係するグラフの研究です。 数例を挙げると、コンピューターサイエンス、情報技術、生物科学、数学、言語学に応用されている人気のあるテーマです。 苦労せずに、グラフの定義から始めましょう。

グラフとは何ですか？

グラフは、オブジェクトのいくつかのペアがリンクで接続されているオブジェクトのセットの図的表現です。 相互接続されたオブジェクトは、*頂点*と呼ばれるポイントで表され、頂点を接続するリンクは*エッジ*と呼ばれます。

形式的には、グラフは*（V、E）、のペアです。 *V は頂点のセットで、 E は頂点のペアを接続するエッジのセットです。 次のグラフを見てください-

グラフの例

上記のグラフでは、

V = \ {a、b、c、d、e}

E = \ {ab、ac、bd、cd、de}

グラフ理論の応用

グラフ理論は、工学のさまざまな分野でその用途があります-

• 電気工学-グラフ理論の概念は、回路接続の設計に広く使用されています。 接続のタイプまたは編成は、トポロジとして名前が付けられます。 トポロジの例には、スター、ブリッジ、シリーズ、およびパラレルトポロジがあります。
• コンピューターサイエンス-グラフ理論はアルゴリズムの研究に使用されます。 例えば、
• クラスカルのアルゴリズム
• プリムのアルゴリズム
• ダイクストラのアルゴリズム
• コンピュータネットワーク-ネットワーク内の相互接続されたコンピュータ間の関係は、グラフ理論の原則に従います。
• 科学-物質の分子構造と化学構造、生物のDNA構造などはグラフで表されます。
• 言語学-言語の構文解析ツリーと言語の文法はグラフを使用します。
• 一般-都市間のルートはグラフを使用して表すことができます。 家系図などの階層的な順序付けされた情報を描くことは、ツリーと呼ばれる特別なタイプのグラフとして使用できます。

グラフ理論-基礎

グラフは、ポイントとポイントに接続された線の図です。 頂点を接続せずに、2つの頂点のセットを結合する少なくとも1つの線があります。 グラフ理論におけるグラフの概念は、ポイント、ライン、頂点、エッジ、頂点の程度、グラフの特性などのいくつかの基本的な用語で成り立っています。 ここで、この章では、これらのグラフ理論の基礎について説明します。

ポイント

• ポイント*は、1次元、2次元、または3次元の空間における特定の位置です。 理解を深めるために、ポイントをアルファベットで示すことができます。 ドットで表すことができます。

例

ポイント

ここで、ドットは「a」という名前のポイントです。

Line

• 線*は、2点間の接続です。 実線で表すことができます。

例

line

ここで、「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

graph1

このグラフには、4つの頂点a、b、c、d、および4つのエッジab、ac、ad、cdがあります。

Loop

グラフでは、エッジが頂点からそれ自体に描かれている場合、ループと呼ばれます。

例1

ループ

上記のグラフで、Vは、ループを形成するエッジ（V、V）を持つ頂点です。

例2

ループ1

このグラフには、頂点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

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

無向グラフ1

上記のグラフでは、

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です。

有向グラフ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

隣接1

上のグラフでは-

• 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

マルチグラフ1

上のグラフでは、頂点「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

グラフ1の次数シーケンス

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}です。

グラフ理論-基本特性

グラフには、構造に応じてグラフの特徴付けに使用されるさまざまなプロパティがあります。 これらの特性は、グラフ理論の領域に関連する特定の用語で定義されます。 この章では、すべてのグラフに共通するいくつかの基本的なプロパティについて説明します。

2つの頂点間の距離

これは、頂点Uと頂点Vの間の最短経路にあるエッジの数です。 2つの頂点を接続する複数のパスがある場合、最短パスは2つの頂点間の距離と見なされます。

表記-d（U、V）

1つの頂点から別の頂点までのパスはいくつでも存在できます。 その中で、最も短いものだけを選択する必要があります。

例

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

2つの頂点間の距離

ここで、頂点「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）

グラフ内の特定の頂点から他のすべての頂点までの距離が取得され、これらの距離の中で、離心率が最も高い距離です。

例

上記のグラフでは、「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で、これは頂点「a」からの最大値であり、「ag」間の距離は最大です。

言い換えると、

e（b）= 3

e（c）= 3

e（d）= 2

e（e）= 3

e（f）= 3

e（g）= 3

接続グラフの半径

すべての頂点からの最小離心率は、グラフGの半径と見なされます。 頂点から他のすべての頂点までのすべての最大距離の最小値は、グラフGの半径と見なされます。

表記-r（G）

グラフ内の頂点のすべての離心率から、接続されたグラフの半径は、これらすべての離心率の最小値になります。

例-上記のグラフでは、r（G）= 2であり、これは「d」の最小離心率です。

グラフの直径

すべての頂点からの最大偏心は、グラフGの直径と見なされます。 頂点から他のすべての頂点までのすべての距離の最大値は、グラフGの直径と見なされます。

表記-d（G）

グラフ内の頂点のすべての離心率から、接続されたグラフの直径は、これらすべての離心率の最大値になります。

例-上記のグラフでは、d（G）= 3;これは最大の離心率です。

セントラルポイント

グラフの離心率がその半径に等しい場合、それはグラフの中心点として知られています。 If

e（V）= r（V）、

「V」はグラフ「G」の中心点です。

例-グラフの例では、「d」はグラフの中心点です。

e（d）= r（d）= 2

センター

「G」のすべての中心点のセットは、グラフの中心と呼ばれます。

例-グラフの例では、\ {’d’}はグラフの中心です。

円周

• 「G」の最長サイクルのエッジの数*は、「G」の円周と呼ばれます。

例-グラフの例では、円周は6です。これは、最長サイクルa-c-f-g-e-b-aまたはa-c-f-d-e-b-aから導き出したものです。

胴回り

「G」の最短サイクル内のエッジの数は、ガースと呼ばれます。

表記-g（G）。

例-例のグラフでは、グラフの周囲は4であり、これは最短サイクルa-c-f-d-aまたはd-f-g-e-dまたはa-b-e-d-aから導き出したものです。

頂点の定理の合計

G =（V、E）が頂点V = \ {V〜1〜、V〜2〜、…V〜n〜}の無向グラフである場合

[.intsuma]# n ∑ i=1 ＃deg（V〜i〜）= 2 | E |

結果1

G =（V、E）が頂点Vの有向グラフである場合、V = \ {V〜1〜、V〜2〜、…V〜n〜}

[.intsuma]# n ∑ i=1 ＃deg ^＆plus; ^（V〜i〜）= | E | = [.intsuma]# n ∑ i=1 ＃deg ^ − ^（V〜i〜）

帰結2

任意の無向グラフでは、奇数次の頂点の数は偶数です。

帰結3

無向グラフでは、各頂点の次数がkの場合、

k | V | = 2 | E |

結果4

無向グラフでは、各頂点の次数が少なくともkである場合、

k | V | ≤2 | E |

結果5

無向グラフでは、各頂点の次数が最大kである場合、

k | V | ≥2 | E |

グラフ理論-グラフの種類

頂点の数、エッジの数、相互接続性、およびそれらの全体的な構造に応じて、さまざまなタイプのグラフがあります。 この章では、いくつかの重要なタイプのグラフについてのみ説明します。

ヌルグラフ

• エッジのない*グラフはヌルグラフと呼ばれます。

例

ヌルグラフ

上記のグラフには、「a」、「b」、「c」という名前の3つの頂点がありますが、それらの間にエッジはありません。 したがって、Null Graphです。

自明なグラフ

頂点が1つしかない*グラフは、自明なグラフと呼ばれます。

例

Trivial

上記のグラフでは、頂点「a」は1つしかなく、他のエッジはありません。 したがって、これは単純なグラフです。

無向グラフ

無向グラフにはエッジが含まれていますが、エッジは有向グラフではありません。

例

非監督

このグラフでは、「a」、「b」、「c」、「d」、「e」、「f」、「g」が頂点、「ab」、「bc」、「cd」、「da」 '、' ag '、' gf '、' ef 'はグラフのエッジです。 無向グラフであるため、エッジ「ab」と「ba」は同じです。 同様に、他のエッジも同様に考慮されます。

有向グラフ

有向グラフでは、各エッジに方向があります。

例

有向グラフ

上記のグラフでは、7つの頂点「a」、「b」、「c」、「d」、「e」、「f」、および「g」、および8つのエッジ「ab」、「cb」、「 dc」、「ad」、「ec」、「fe」、「gf」、および「ga」。 有向グラフなので、各エッジには方向を示す矢印が付いています。 有向グラフでは、「ab」は「ba」とは異なることに注意してください。

シンプルなグラフ

• ループなし*および*平行エッジなし*のグラフは、単純グラフと呼ばれます。

• 「n」個の頂点を持つ単一のグラフで可能なエッジの最大数は^ n ^ C〜2〜です。ここで^ n ^ C〜2〜= n（n – 1）/2です。
• 「n」個の頂点= 2 ^^ n ^ c〜2〜^ = 2 ^ n（n-1）/2 ^で可能な単純なグラフの数。

例

次のグラフには、3つのエッジを持つ3つの頂点があり、最大の平行エッジとループを除外しています。 これは、上記の式を使用して証明できます。

シンプルグラフ

n = 3頂点を持つエッジの最大数-

nC2 = n(n–1)/2
   = 3(3–1)/2
   = 6/2
   = 3 edges

n = 3頂点を持つ単純なグラフの最大数-

2nC2 = 2n(n-1)/2
   = 23(3-1)/2
   = 23
   = 8

これらの8つのグラフは以下のとおりです-

8つのグラフ

接続グラフ

グラフGは、頂点のすべてのペア間にパスが存在する場合は接続されていると言われます。 グラフのすべての頂点に少なくとも1つのエッジが必要です。 そのため、エッジの反対側にある他の頂点に接続されていると言えます。

例

次のグラフでは、各頂点には他のエッジに接続された独自のエッジがあります。 したがって、接続されたグラフです。

接続グラフ

切断グラフ

少なくとも2つの接続された頂点が含まれていない場合、グラフGは切断されます。

例1

次のグラフは、「a」、「b」、「c」、「d」の頂点を持つコンポーネントと「e」、「f」、「g」を持つコンポーネントの2つのコンポーネントがある、切断グラフの例です。 'h’頂点。

切断グラフ

2つのコンポーネントは独立しており、互いに接続されていません。 したがって、非接続グラフと呼ばれます。

例2

切断グラフ1

この例では、a-b-f-eとc-dの2つの独立したコンポーネントがあり、これらは互いに接続されていません。 したがって、これは切断されたグラフです。

正則グラフ

グラフGは、すべての頂点の次数が同じであれば、規則的であると言われます*。 グラフでは、各頂点の次数が「k」の場合、そのグラフは「k-regular graph」と呼ばれます。

例

次のグラフでは、すべての頂点の次数が同じです。 したがって、これらのグラフは通常のグラフと呼ばれます。

正規グラフ

両方のグラフで、すべての頂点の次数は2です。 それらは、2-Regular Graphsと呼ばれます。

完全なグラフ

「n」の相互頂点を持つ単純なグラフは完全なグラフと呼ばれ、「K〜n〜」で示されます*。 グラフでは、頂点は他のすべての頂点とエッジを持っている必要があり、完全なグラフと呼ばれます。

つまり、頂点がグラフ内の他のすべての頂点に接続されている場合、完全なグラフと呼ばれます。

例

次のグラフでは、グラフ内の各頂点は、それ自体を除き、グラフ内の残りのすべての頂点に接続されています。

完全なグラフ

グラフIでは、

	a	b	c
a	Not Connected	Connected	Connected
b	Connected	Not Connected	Connected
c	Connected	Connected	Not Connected

グラフIIでは、

	p	q	r	s
p	Not Connected	Connected	Connected	Connected
q	Connected	Not Connected	Connected	Connected
r	Connected	Connected	Not Connected	Connected
s	Connected	Connected	Connected	Not Connected

サイクルグラフ

「n」個の頂点（n> = 3）と「n」個のエッジを持つ単純なグラフは、すべてのエッジが「n」個の長さのサイクルを形成する場合、サイクルグラフと呼ばれます。

グラフの各頂点の次数が2の場合、それはサイクルグラフと呼ばれます。

表記-C〜n〜

例

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

• グラフIには、「ab-bc-ca」というサイクルを形成する3つのエッジを持つ3つの頂点があります。
• グラフIIには、「pq-qs-sr-rp」サイクルを形成する4つのエッジを持つ4つの頂点があります。
• グラフIIIには、「ik-km-ml-lj-ji」というサイクルを形成する5つのエッジを持つ5つの頂点があります。

サイクルグラフ

したがって、指定されたグラフはすべてサイクルグラフです。

ホイールグラフ

ホイールグラフは、新しい頂点を追加することにより、サイクルグラフC〜n-1〜から取得されます。 その新しい頂点は Hub と呼ばれ、C〜n〜のすべての頂点に接続されます。

表記-W〜n〜

No. of edges in Wn = No. of edges from hub to all other vertices +
                     No. of edges from all other nodes in cycle graph without a hub.
                     = (n–1) + (n–1)
                     = 2(n–1)

例

以下のグラフをご覧ください。 それらはすべてホイールグラフです。

ホイールグラフ

グラフIでは、中央に「d」という名前の頂点を追加することにより、C〜3〜から取得されます。 W〜4〜と表示されます。

Number of edges in W4 = 2(n-1) = 2(3) = 6

グラフIIでは、中央に「t」という名前の頂点を追加することにより、C〜4〜から取得されます。 W〜5〜と表示されます。

Number of edges in W5 = 2(n-1) = 2(4) = 8

グラフIIIでは、中央に「o」という名前の頂点を追加することにより、C〜6〜から取得されます。 W〜7〜と表示されます。

Number of edges in W4 = 2(n-1) = 2(6) = 12

巡回グラフ

少なくとも1つのサイクルを持つグラフは、巡回グラフと呼ばれます。

例

巡回グラフ

上記のグラフ例では、a-b-c-d-aとc-f-g-e-cの2つのサイクルがあります。 したがって、巡回グラフと呼ばれます。

非循環グラフ

• サイクルのない*グラフは非循環グラフと呼ばれます。

例

非周期グラフ

上記のグラフの例では、サイクルはありません。 したがって、これは非循環グラフです。

二部グラフ

頂点パーティションV = \ {V〜1〜、V〜2〜}を持つ単純なグラフG =（V、E）は、2部グラフと呼ばれます* EのすべてのエッジがV〜1〜の頂点をの頂点に結合する場合V〜2〜*。

一般に、バイパータイトグラフには2つの頂点セットがあります。V〜1〜とV〜2〜で、エッジを描画する場合、セットV〜1〜の頂点をセットVの頂点に接続する必要があります。 〜2〜。

例

二部グラフ

このグラフでは、V〜1〜とV〜2〜の2組の頂点を観察できます。 ここでは、「ae」と「bd」という名前の2つのエッジが、2つのセットV〜1〜とV〜2〜の頂点を接続しています。

完全な二部グラフ

パーティションV = \ {V〜1〜、V〜2〜}を持つ2部グラフ 'G'、G =（V、E）は、V〜1〜のすべての頂点がすべてに接続されている場合、完全な2部グラフと言われます。 V〜2〜の頂点。

一般に、完全な2部グラフは、セットV〜1〜の各頂点をセットV〜2〜の各頂点に接続します。

例

次のグラフは、セットV〜1〜の各頂点をセットV〜2〜の各頂点に接続するエッジがあるため、完全な2部グラフです。

完全な二部グラフ

| V〜1〜|の場合= mおよび| V〜2〜| = nの場合、完全な2部グラフはK〜m、n〜で示されます。

• K〜m、n〜には（m + n）個の頂点と（mn）個のエッジがあります。
• K〜m、n〜は、m = nの場合、通常のグラフです。

一般的に、*完全な二部グラフは完全なグラフ*ではありません。

K〜m、n〜は、m = n = 1の場合、完全なグラフです。

*n* 頂点を持つ2部グラフのエッジの最大数は

[

n² / 4

]

n = 10、k5、5 =⌊[.fraction]＃の場合 n² / 4 ＃⌋=⌊[.fraction]＃ 10² / 4 ＃⌋= 25

同様に、K6、4 = 24

K7、3 = 21

K8、2 = 16

K9、1 = 9

n = 9、k5、4 =⌊[.fraction]＃の場合 n² / 4 ＃⌋=⌊[.fraction]＃ 9² / 4 ＃⌋= 20

同様に、K6、3 = 18

K7、2 = 14

K8、1 = 8

「G」に奇数の長さのサイクルがない場合、「G」は2部グラフです。 二部グラフの特殊なケースは、*星グラフ*です。

スターグラフ

K〜1、n-1〜の形式の完全な2部グラフは、n頂点を持つ星形グラフです。 単一の頂点が1つのセットに属し、残りのすべての頂点が他のセットに属する場合、スターグラフは完全な2部グラフです。

例

スターグラフ

上記のグラフでは、「n」個の頂点のうち、すべての「n-1」個の頂点が単一の頂点に接続されています。 したがって、星形グラフであるK〜1、n-1〜の形式です。

グラフの補数

_ '[。sy] G [.oncapital] − を 'G’の頂点と、 '[にエッジ\ {U、V}が存在するようないくつかの頂点を持つ単純なグラフとします。 sy] G [.oncapital] −' 、Gにエッジが存在しない場合 つまり、2つの頂点がGで隣接していない場合、2つの頂点は '[。sy] G [.oncapital] - _で隣接しています。

グラフIに存在するエッジが別のグラフIIに存在せず、グラフIとグラフIIの両方が組み合わされて完全なグラフを形成する場合、グラフIとグラフIIは互いに補数と呼ばれます。

例

次の例では、graph-Iには2つのエッジ「cd」と「bd」があります。 補完グラフIIには4つのエッジがあります。

グラフの補数

graph-Iのエッジはgraph-IIには存在せず、その逆も同様です。 したがって、両方のグラフを組み合わせると、「n」個の頂点の完全なグラフが得られます。

注-2つの相補的なグラフの組み合わせにより、完全なグラフが得られます。

「G」が単純なグラフの場合、

|E(G)| + |E(G-)| = |E(K_n)|, where n = number of vertices in the graph.

例

「G」を9つの頂点と12のエッジを持つ単純なグラフとし、_ '[。sy] G [.oncapital] - _でエ​​ッジの数を見つけます。

あります| E（G）| + | E（_ '[。sy] G [.oncapital] - _）| = | E（K〜n〜）|

12＆plus; | E（_ '[。sy] G [.oncapital] - _）| = [.fraction] ##

9(9-1)/2⁹₂

12＆plus; | E（_ '[。sy] G [.oncapital] - _）| = 36

|E(G-)| = 24

「G」は40のエッジを持つ単純なグラフであり、その補数_ '[。sy] G [.oncapital] − には38のエッジがあります。 グラフGまたは '[。sy] G [.oncapital] − _の頂点の数を見つけます。

グラフ内の頂点の数を「n」とします。

あります| E（G）| + | E（_ '[。sy] G [.oncapital] - _）| = | E（K〜n〜）|

40＆plus; 38 = [.fraction]＃ n(n-1) / 2 #

156 = n（n-1）

13（12）= n（n-1）

n = 13

グラフ理論-木

ツリーは、単一のサイクルさえも含まないグラフです。 これらは、グラフィカルな形式で階層構造を表します。 ツリーは、グラフの最も単純なクラスに属します。 シンプルでありながら、豊富な構造を持っています。

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

Tree

• 接続された非循環グラフ*はツリーと呼ばれます。 つまり、サイクルのない接続されたグラフはツリーと呼ばれます。

木の端は*枝*と呼ばれます。 木の要素は*ノード*と呼ばれます。 子ノードのないノードは*リーフノード*と呼ばれます。

「n」個の頂点を持つツリーには「n-1」個のエッジがあります。 「n-1」よりも余分なエッジが1つある場合、余分なエッジは明らかに2つの頂点とペアにする必要があり、サイクルを形成します。 次に、それはツリーグラフの違反である循環グラフになります。

例1

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

ツリー

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

例2

ツリー1

上記の例では、頂点「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」として塗りつぶされます。

キルヒホッフの定理の例

グラフ理論-接続性

グラフをある頂点から別の頂点に移動できるかどうかは、グラフの接続方法によって決まります。 接続性は、グラフ理論の基本概念です。 接続性は、グラフが接続されているか切断されているかを定義します。 エッジの接続性と頂点の接続性として知られる、エッジと頂点に基づくサブトピックがあります。 それらについて詳しく説明しましょう。

接続性

グラフは、頂点のすべてのペア間にパスがある場合、接続されていると言われます。 すべての頂点から他の頂点まで、横断するパスが必要です。 これは、グラフの接続性と呼ばれます。 複数の切断された頂点とエッジを持つグラフは切断されていると言われます。

例1

次のグラフでは、1つの頂点から他の頂点に移動できます。 たとえば、パス「a-b-e」を使用して、頂点「a」から頂点「e」に移動できます。

接続性

例2

次の例では、頂点「a」から頂点「f」への移動は、それらの間に直接または間接にパスがないため不可能です。 したがって、これは切断されたグラフです。

接続性1

頂点をカット

「G」を接続グラフとします。 頂点V∈Gは、「G-V」（「G」から「V」を削除）が切断されたグラフになる場合、「G」のカット頂点と呼ばれます。 カットされた頂点をグラフから削除すると、2つ以上のグラフに分割されます。

注意-カットされた頂点を削除すると、グラフが切断される場合があります。

接続されたグラフ「G」には、最大（n–2）個のカット頂点があります。

例

次のグラフでは、頂点「e」と「c」がカットされた頂点です。

頂点をカット

「e」または「c」を削除すると、グラフは切断されたグラフになります。

頂点をeで切り取る 頂点をeで切り取る

「g」がないと、頂点「c」と頂点「h」などの間にパスがありません。 したがって、これは切断された頂点が「e」の非接続グラフです。 同様に、「c」も上のグラフのカット頂点です。

カットエッジ（ブリッジ）

「G」を接続グラフとします。 「G-e」が切断されたグラフになる場合、エッジ「e」∈Gはカットエッジと呼ばれます。

グラフのエッジを削除すると、2つ以上のグラフが作成される場合、そのエッジはカットエッジと呼ばれます。

例

次のグラフでは、カットエッジは[（c、e）]です

カットエッジ

グラフからエッジ（c、e）を削除すると、切断されたグラフになります。

Cut with Edge Cut with Edge

上のグラフで、エッジ（c、e）を削除すると、グラフは2つに分割されますが、これは切断されたグラフにすぎません。 したがって、エッジ（c、e）はグラフのカットエッジです。

注-「G」を「n」個の頂点を持つ接続グラフとし、

• エッジ 'e’がGのサイクルの一部でない場合にのみ、カットエッジe∈G
• 可能なカットエッジの最大数は「n-1」です。
• カットエッジが存在する場合は常に、カットエッジの少なくとも1つの頂点がカット頂点であるため、カット頂点も存在します。
• カット頂点が存在する場合、カットエッジが存在する場合と存在しない場合があります。

グラフのカットセット

「G」=（V、E）を接続グラフとします。 EのサブセットE 'は、GからE’のすべてのエッジを削除するとGが切断される場合、Gのカットセットと呼ばれます。

グラフから特定の数のエッジを削除すると切断される場合、それらの削除されたエッジはグラフのカットセットと呼ばれます。

例

次のグラフをご覧ください。 そのカットセットはE1 = \ {e1、e3、e5、e8}です。

グラフのカットセット

グラフからカットセットE1を削除した後、次のように表示されます-

グラフ1のカットセット

同様に、グラフを切断できる他のカットセットがあります-

• E3 = \ {e9} –グラフの最小カットセット。
• E4 = \ {e3、e4、e5}

エッジ接続

「G」を接続グラフとします。 削除によって「G」が切断されるエッジの最小数は、Gのエッジ接続と呼ばれます。

表記-λ（G）

言い換えれば、Gの最小カットセットの*エッジの数は、Gのエッジ接続性と呼ばれます。

「G」にカットエッジがある場合、_λ（G）_は1です。 （Gのエッジ接続。）

例

次のグラフをご覧ください。 2つの最小エッジを削除すると、接続されたグラフは切断されます。 したがって、エッジの接続性（λ（G））は2です。

エッジ接続

ここに2つのエッジを削除してグラフを切断する4つの方法があります-

Edge Connectivity 1

頂点接続

「G」を接続グラフとします。 削除によって「G」が切断されるか、「G」が単純なグラフに減少する頂点の最小数は、その頂点接続性と呼ばれます。

表記-K（G）

例

上のグラフで、頂点「e」と「i」を削除すると、グラフが切断されます。

頂点接続

Gにカット頂点がある場合、K（G）= 1。

表記-接続されたグラフGの場合、

K（G）≤λ（G）≤δ（G）

頂点接続（K（G））、エッジ接続（λ（G））、G（δ（G））の最小次数。

例

次のグラフのλ（G）とK（G）を計算します-

頂点接続の例

溶液

グラフから、

δ（G）= 3

K（G）≤λ（G）≤δ（G）= 3（1）

K（G）≥2（2）

エッジ\ {d、e}および\ {b、h}を削除すると、Gを切断できます。

したがって、

λ（G）= 2

2≤λ（G）≤δ（G）= 2（3）

（2）および（3）から、頂点接続性K（G）= 2

グラフ理論-カバー

カバーグラフは、他のグラフに対応するすべての頂点またはすべてのエッジのいずれかを含むサブグラフです。 すべての頂点を含むサブグラフは、*ライン/エッジカバー*と呼ばれます。 すべてのエッジを含むサブグラフは、*頂点カバー*と呼ばれます。

回線カバー

G =（V、E）をグラフにします。 サブセットC（E）は、Gのすべての頂点がCの少なくとも1つのエッジに入射する場合、Gをカバーするラインと呼ばれます。

deg（V）≥1∀V∈G

各頂点は別の頂点とエッジで接続されているためです。 したがって、最小次数は1です。

例

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

ラインカバリング

線をカバーするそのサブグラフは次のとおりです-

C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}

「G」のラインカバーは、「G」に孤立した頂点がある場合にのみ存在します。 「n」個の頂点を持つグラフの線カバーには、少なくとも⌊[.fraction]＃ n / 2 ＃⌋エッジ。

最小限の回線カバー

グラフGのCを覆う線は、Cからエッジを削除できない場合*最小であると言われます。

例

上記のグラフでは、線をカバーするサブグラフは次のとおりです-

C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}

ここでは、C〜1〜、C〜2〜、C〜3〜は最小限の行カバーですが、C〜4〜は\ {b、c}を削除できるためではありません。

最小回線カバー

また、 Smallest Minimal Line Covering としても知られています。 最小数のエッジでカバーする最小ラインは、「G」の最小ラインカバーと呼ばれます。 「G」でカバーする最小ライン内のエッジの数は、「G」（α〜1〜）の「*ラインカバーナンバー」と呼ばれます。

例

上記の例では、C〜1〜とC〜2〜はGとα〜1〜= 2の最小の線カバーです。

• すべての回線カバーには、最小限の回線カバーが含まれています。
• すべての回線カバーには最小回線カバーが含まれていません（C〜3〜には最小回線カバーは含まれていません。
• サイクルを含む最小限のラインカバーはありません。
• 「C」をカバーするラインに長さ3以上のパスが含まれていない場合、「C」はすべてのコンポーネントがスターグラフであり、スターグラフからは削除できないため、「C」は最小ラインカバーです。

頂点カバー

「G」=（V、E）をグラフにします。 VのサブセットKは、「G」のすべてのエッジが「K」の頂点に入射または覆われている場合、「G」の頂点カバーと呼ばれます。

例

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

頂点被覆

上記のグラフから派生できるサブグラフは次のとおりです-

K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
K4 = {a, d}

ここで、K〜1〜、K〜2〜、およびK〜3〜は頂点をカバーしていますが、K〜4〜はエッジ\ {bc}をカバーしていないため、頂点をカバーしていません。

最小限の頂点被覆

グラフ「G」の頂点「K」は、「K」から頂点を削除できない場合、最小の頂点をカバーすると言われます。

例

上記のグラフでは、頂点をカバーするサブグラフは次のとおりです-

K〜1〜= \ {b、c}

K〜2〜= \ {a、b、c}

K〜3〜= \ {b、c、d}

ここで、K〜1〜とK〜2〜は最小の頂点カバーですが、K〜3〜では頂点「d」を削除できます。

最小頂点被覆

また、最小の最小頂点被覆としても知られています。 最小数の頂点を持つグラフ「G」の最小頂点被覆は、最小頂点被覆と呼ばれます。

「G」の最小頂点カバー内の頂点の数は、Gの頂点カバー数（α〜2〜）と呼ばれます。

例

次のグラフでは、頂点をカバーしているサブグラフは次のとおりです-

K〜1〜= \ {b、c}

K〜2〜= \ {a、b、c}

K〜3〜= \ {b、c、d}

最小頂点被覆

ここで、K〜1〜は、頂点が2つしかないため、Gの最小頂点カバーです。 α〜2〜= 2。

グラフ理論-マッチング

一致するグラフは、互いに隣接するエッジがないグラフのサブグラフです。 単純に、2つのエッジ間に共通の頂点があってはなりません。

マッチング

「G」=（V、E）をグラフにします。 サブグラフは、一致するM（G）と呼ばれます。* Gの各頂点が最大でMの1つのエッジに入射する場合、*、

deg（V）≤1∀V∈G

つまり、マッチンググラフM（G）では、頂点の次数は1または0である必要があり、エッジはグラフGから入射するはずです。

表記-M（G）

例

マッチング マッチング1

マッチングでは、

deg（V）= 1の場合、（V）は一致すると言われます

deg（V）= 0の場合、（V）は一致しません。

マッチングでは、2つのエッジが隣接していません。 これは、2つのエッジが隣接している場合、それらの2つのエッジを結合している頂点の次数は2であり、一致規則に違反するためです。

最大マッチング

グラフ「G」の一致するMは、「G」の他のエッジをM *に追加できない場合、最大と言われます。

例

最大マッチング

上記のグラフのM〜1〜、M〜2〜、M〜3〜はGの最大一致です。

最大マッチング

最大最大一致とも呼ばれます。 最大一致は、エッジの最大数との最大一致として定義されます。

「G」の最大一致のエッジの数は、*一致数*と呼ばれます。

例

最大マッチング

上記の例のグラフの場合、M〜1〜とM〜2〜は「G」の最大一致であり、その一致数は2です。 したがって、グラフGを使用すると、最大2つのエッジのみを持つサブグラフのみを形成できます。 したがって、一致する番号は2になります。

完全一致

グラフ（G）のマッチング（M）は完全に一致すると言われます*グラフg（G）のすべての頂点がマッチング（M）のちょうど1つのエッジに入射する場合、つまり

deg（V）= 1∀V

サブグラフ内の各頂点の次数は、*度*が1でなければなりません。

例

次のグラフでは、M〜1〜およびM〜2〜はGの完全一致の例です。

完全一致

注-グラフのすべての完全一致は、グラフの最大一致でもあります。完全一致グラフにもう1つのエッジを追加する可能性がないためです。

グラフの最大一致は完全である必要はありません。 グラフ「G」が完全に一致する場合、頂点の数| V（G）|偶数です。 奇数の場合、最後の頂点は他の頂点とペアになり、最終的に、次数がゼロである他の頂点とペアリングできない単一の頂点が残ります。 それは明らかに完全なマッチングの原則に違反しています。

例

完全一致の例

注-上記の説明の逆は真である必要はありません。 Gに偶数の頂点がある場合、M〜1〜は完全である必要はありません。

例

完全一致の例1

一致していますが、頂点の数が偶数であっても完全には一致しません。

グラフ理論-独立集合

独立したセットはセットで表されます。

• *互いに隣接するエッジ*があってはなりません。 2つのエッジ間に共通の頂点があってはなりません。
• 互いに隣接する頂点があってはなりません。 2つの頂点間に共通のエッジがあってはなりません。

独立ラインセット

「G」=（V、E）をグラフにします。 EのサブセットLは、Lの2つのエッジが隣接していない場合、「G」の独立したラインセットと呼ばれます。 このようなセットは、独立回線セットと呼ばれます。

例

独立ラインセット

私たちは次のサブセットを考えてみましょう-

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

この例では、サブセットL〜2〜とL〜3〜は明らかに、与えられたグラフの隣接するエッジではありません。 これらは独立したラインセットです。 ただし、L〜1〜は独立したラインセットではありません。独立したラインセットを作成するには、少なくとも2つのエッジが必要です。

最大独立線セット

「G」の他のエッジを「L」に追加できない場合、独立線セットはグラフ「G」の最大独立線セットと呼ばれます。

例

最大独立線セット

私たちは次のサブセットを考えてみましょう-

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L〜2〜およびL〜3〜は、最大独立ラインセット/最大マッチングです。 これら2つのサブセットのみに関しては、隣接していない他のエッジを追加する可能性はありません。 したがって、これらの2つのサブセットは、最大独立ラインセットと見なされます。

最大独立線セット

エッジの最大数を持つ「G」の最大独立線セットは、「G」の最大独立線セットと呼ばれます。

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

例

最大独立線セット

私たちは次のサブセットを考えてみましょう-

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L〜3〜は、グラフの隣接エッジではない最大エッジを持つGの最大独立線セットで、β〜1〜 = 3で示されます。

注-孤立した頂点のないグラフGの場合、

α〜1〜+β〜1〜=グラフ内の頂点の数= | V |

例

K〜n〜/C〜n〜/w〜n〜の行カバー数

独立した最大ラインセットの例

行に依存しない番号（マッチング番号）= *β〜1〜=⌊[.fraction]＃ n / 2 ＃⌋α〜1〜＆plus; β〜1〜= n *

独立頂点セット

「G」=（V、E）をグラフにします。 「S」内の2つの頂点が隣接していない場合、「V」のサブセットは「G」の独立セットと呼ばれます。

例

独立頂点セットの例

上記のグラフから次のサブセットを考慮してください-

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

明らかに、S〜1〜は独立した頂点セットではありません。独立した頂点セットを取得するには、グラフから少なくとも2つの頂点が必要であるためです。 しかし、ここではそうではありません。 サブセットS〜2〜、S〜3〜、およびS〜4〜は、サブセットのいずれかの頂点に隣接する頂点がないため、独立した頂点セットです。

最大独立頂点セット

「G」をグラフとし、「G」の頂点を「S」に追加できない場合、「G」の独立した頂点セットは最大であると言われます。

例

最大独立頂点セットの例

上記のグラフの次のサブセットを検討してください。

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S〜2〜およびS〜3〜は、「G」の最大独立頂点セットです。 S〜1〜およびS〜4〜では、他の頂点を追加できます。ただし、S〜2〜およびS〜3〜では、他の頂点を追加できません

最大独立頂点セット

最大数の頂点を持つ「G」の最大独立頂点セットは、最大独立頂点セットと呼ばれます。

例

最大独立頂点セットの例

上記のグラフから次のサブセットを考慮してください-

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

最大数の頂点をカバーするため、S〜3〜のみが最大独立頂点セットです。 「G」の最大独立頂点セット内の頂点の数は、Gの独立頂点数（β〜2〜）と呼ばれます。

例

For the complete graph Kn,
      Vertex covering number = α2 = n−1
      Vertex independent number = β2 = 1
You have α2 + β2 = n
In a complete graph, each vertex is adjacent to its remaining (n − 1) vertices. Therefore, a maximum independent set of Kn contains only one vertex.
Therefore,   β2=1
and          α2=|v| − β2 = n-1

注-任意のグラフ「G」=（V、E）

• α〜2〜＆plus; β〜2〜= | v |
• 「S」が「G」の独立した頂点セットである場合、（V – S）はGの頂点カバーです。

グラフ理論-彩色

グラフの色付けは、いくつかの制約の下で頂点、エッジ、領域などのグラフコンポーネントにラベルを付ける簡単な方法にすぎません。 グラフでは、2つの隣接する頂点、隣接するエッジ、または隣接する領域は、最小限の色で色付けされません。 この数は*色数*と呼ばれ、グラフは*適切に色付けされたグラフ*と呼ばれます。

グラフの色付け中、グラフに設定される制約は色、色付けの順序、色の割り当て方法などです。 頂点または特定の領域に色が付けられます。 したがって、同じ色を持つ頂点または領域は、独立したセットを形成します。

頂点カラーリング

頂点の色付けは、2つの隣接する頂点が同じ色を持たないように、グラフ「G」の頂点に色を割り当てることです。 簡単に言えば、エッジの2つの頂点が同じ色であってはなりません。

色数

グラフ「G」の頂点カラーリングに必要な色の最小数は、X（G）で示されるGの色数と呼ばれます。

？ 'G？'の場合に限り、χ（G）= 1 nullグラフです。 「G」の場合ヌルグラフではない場合、χ（G）≥2

例

色番号

注-グラフ「G」は、最大でn色を使用する頂点カラーリングがある場合、つまりX（G）≤nである場合、nカバー可能と呼ばれます。

リージョンカラーリング

領域の色付けは、2つの隣接する領域が同じ色を持たないように、平面グラフの領域に色を割り当てることです。 2つの領域は、共通のエッジがある場合、隣接していると言われます。

例

次のグラフをご覧ください。 領域「aeb」と「befc」は隣接しています。これらの2つの領域の間には共通のエッジ「be」があります。

地域のカラーリング

同様に、他の領域も隣接に基づいて色付けされます。 このグラフの色は次のとおりです-

Region Coloring 1

例

K〜n〜の色数は

{空} a）n

{空} b）n–1

c）⌊[.fraction]＃ n / 2 #⌋

d）⌈[.fraction]＃ n / 2 #⌉

K〜4〜のこの例を検討してください。

リージョンのカラーリングの例

完全なグラフでは、各頂点は残りの（n – 1）頂点に隣接しています。 したがって、各頂点には新しい色が必要です。 したがって、K〜n〜= nの色数。

グラフ彩色の応用

グラフの色付けは、グラフ理論で最も重要な概念の1つです。 次のようなコンピュータサイエンスの多くのリアルタイムアプリケーションで使用されます-

• クラスタリング
• データマイニング
• 画像キャプチャ
• 画像のセグメンテーション
• ネットワーキング
• 資源配分
• プロセスのスケジューリング

グラフ理論-同型

グラフは、同じ数の頂点、エッジ、および同じエッジ接続を持つ異なる形式で存在できます。 このようなグラフは同型グラフと呼ばれます。 この章のグ​​ラフにラベルを付けるのは、主にそれらを参照し、相互に認識できるようにするためです。

同型グラフ

2つのグラフG〜1〜およびG〜2〜は、次の場合に同型であると言われます-

• コンポーネント（頂点とエッジ）の数は同じです。
• それらのエッジ接続は保持されます。

注-要するに、2つの同形グラフのうち、1つは他の微調整されたバージョンです。 ラベルのないグラフも同型グラフと考えることができます。

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
   edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

注意

G〜1〜≡G〜2〜の場合-

• | V（G〜1〜）| = | V（G〜2〜）|
• | E（G〜1〜）| = | E（G〜2〜）|
• G〜1〜とG〜2〜の次数シーケンスは同じです。
• 頂点\ {V〜1〜、V〜2〜、.. V〜k〜}はG〜1〜で長さKのサイクルを形成し、頂点\ {f（V〜1〜）、f（V〜2〜）、…f（V〜k〜）}はG〜2〜の長さKのサイクル。

グラフG〜1〜およびG〜2〜が同型であるためには上記のすべての条件が必要ですが、グラフが同型であることを証明するには不十分です。

• （G〜1〜≡G〜2〜）if and only if（_ [。sy]＃G〜1〜[.oncapital]＃− '≡ [。sy]＃G〜2〜[.oncapital] ＃- _）ここで、G〜1〜およびG〜2〜は単純なグラフです。
• （G〜1〜≡G〜2〜）G〜1〜とG〜2〜の隣接行列が同じ場合。
• （G〜1〜≡G〜2〜）G〜1〜およびG〜2〜の対応するサブグラフ（G〜1〜のいくつかの頂点とグラフG〜2〜の画像を削除することにより得られる）が同型。

例

次のグラフのうち、同型のものはどれですか？

同形

グラフG〜3〜では、頂点「w」の次数は3のみですが、他のすべてのグラフ頂点の次数は2です。 したがって、G〜3〜はG〜1〜またはG〜2〜と同型ではありません。

G〜1〜とG〜2〜を補完すると、次のようになります-

同形の例

ここでは、（_ [。sy]＃G〜1〜[.oncapital]＃-'≡ [。sy]＃G〜2〜[.oncapital]＃- _）、したがって（G〜1〜 ≡G〜2〜）。

平面グラフ

グラフ「G」は、2つのエッジが頂点以外の点で互いに交差しないように平面または球に描画できる場合、平面であると言われます。

例

平面グラフ

地域

すべての平面グラフは、平面と呼ばれる連結された領域に平面を分割します。

例

地域

境界領域の次数* r = deg（r）* =領域を囲むエッジの数 r 。

deg(1) = 3
deg(2) = 4
deg(3) = 4
deg(4) = 3
deg(5) = 8

地域の例

無制限領域の次数* r = deg（r）* =領域を囲むエッジの数 r 。

deg(R1) = 4
deg(R2) = 6

平面グラフでは、次の特性が良好です-

• 1. 「n」個の頂点を持つ平面グラフでは、すべての頂点の次数の合計は

[.intsuma]# n ∑ i=1 ＃deg（V〜i〜）= 2 | E | * 2. Sum of Degrees of Regions Theoremによると、「n」個の領域がある平面グラフでは、領域の次数の合計は-

[.intsuma]# n ∑ i=1 ＃deg（r〜i〜）= 2 | E |

上記の定理に基づいて、次の結論を引き出すことができます-

平面グラフでは、

• 各領域の次数がKの場合、領域の次数の合計は + K | R | = 2 | E |
• 各領域の次数が少なくともK（≥K）である場合、 + K | R | ≤2 | E |
• 各領域の次数が最大K（≤K）の場合、 + K | R | ≥2 | E |

注-すべての地域が同じ程度であると仮定します。

*3.* 平面グラフの*オイラーの公式*によると、

• グラフ「G」が接続された平面の場合、 + | V | + | R | = | E | + 2
• 「K」コンポーネントの平面グラフの場合、 + | V | + | R | = | E | +（K + 1）

ここで、| V |は頂点の数| E |はエッジの数で、| R |リージョンの数です。

4. エッジ頂点の不等式

「G」が連結された平面グラフで、各領域の次数が少なくとも「K」の場合、

|E| ≤ [.fraction]# k / k − 2 ＃\ {| v | -2}

ご存知のように、| V | ＆プラス; | R | = | E | ＆プラス; 2

1. | R | ≤2 | E |

K（| E |-| V |＆plus; 2）≤2 | E |

（K-2）| E | ≤K（| V |-2）

|E| ≤ [.fraction]# k / k − 2 ＃\ {| v | -2}

5. 「G」が単純な連結平面グラフの場合、

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

deg（V）≤5となるような少なくとも1つの頂点V？∈Gが存在する

6. 「G」が単純な連結平面グラフ（少なくとも2つのエッジを持つ）であり、三角形がない場合、

|E| ≤ {2|V| – 4}

7. クラトフスキーの定理

グラフ「G」が非平面であるのは、「G」にK〜5〜またはK〜3,3〜に準同型のサブグラフがある場合のみです。

準同型

2つのグラフG〜1〜およびG〜2〜は、Gのいくつかのエッジをより多くの頂点で分割することにより、これらの各グラフが同じグラフ「G」から取得できる場合、準同型であると言われます。 次の例を見てください-

準同型

1つの頂点を追加して、エッジ「rs」を2つのエッジに分割します。

準同型1

以下に示すグラフは、最初のグラフと準同型です。

最初のグラフを持つ準同型

G〜1〜がG〜2〜に同型である場合、GはG〜2〜に同型ですが、その逆は真である必要はありません。

• 頂点が4つ以下のグラフはすべて平面です。
• エッジが8個以下のグラフはすべて平面です。
• 完全なグラフK〜n〜は、n≤4の場合にのみ平面です。
• 完全な2部グラフK〜m、n〜は、m≤2またはn≤2の場合にのみ平面です。
• 頂点の数が最小の単純な非平面グラフは、完全なグラフK〜5〜です。
• エッジの最小数を持つ単純な非平面グラフはK〜3、3〜です。

多面体グラフ

単純な連結平面グラフは、各頂点の次数が3以上、つまりdeg（V）≥3？∀V？∈Gの場合、多面体グラフと呼ばれます。

• 3 | V | ≤2 | E |
• 3 | R | ≤2 | E |

グラフ理論-トラバーサビリティ

同じパスを再トレースせずにすべての頂点間にパスを描画できる場合、グラフはトラバース可能です。 このパスに基づいて、オイラーのパスやオイラーの回路など、この章で説明するカテゴリがいくつかあります。

オイラーの道

オイラーのパスには、「G」の各エッジが1回だけ、「G」の各頂点が少なくとも1回含まれています。 連結グラフGは、オイラーのパスが含まれている場合に通過可能であると言われます。

例

オイラーの道

オイラーのパス = d-c-a-b-d-e。

オイラーのサーキット

オイラーのパスで、開始頂点が終了頂点と同じである場合、オイラーの回路と呼ばれます。

例

オイラーのサーキット

オイラーのパス = a-b-c-d-a-g-f-e-c-a

オイラーの回路定理

接続されたグラフ「G」は、Gの次数が奇数の頂点の数が正確に2または0である場合にのみ通過できます。 接続されたグラフGには、オイラーのパスは含まれますが、オイラーの回路は含まれません。奇数次の頂点がちょうど2つある場合です。

注意-このオイラーパスは奇数次の頂点で始まり、奇数次の頂点で終わります。

例

オイラーの回路定理

オイラーのパス-b-e-a-b-d-c-aはオイラーのサーキットではなく、オイラーのパスです。 明らかに、ちょうど2つの奇数次の頂点があります。

注-接続されたグラフGで、次数が奇数の頂点の数= 0の場合、オイラーの回路が存在します。

ハミルトニアングラフ

連結グラフGは、Gのすべての頂点を含むサイクルが存在する場合、ハミルトニアングラフと呼ばれます。

すべてのサイクルは回路ですが、回路には複数のサイクルが含まれる場合があります。 このようなサイクルは、Gの*ハミルトニアンサイクル*と呼ばれます。

ハミルトニアンパス

連結グラフは、Gの各頂点を1回だけ含む場合、ハミルトニアンと呼ばれます。 このようなパスは、*ハミルトニアンパス*と呼ばれます。

例

ハミルトニアンパス

ハミルトニアンパス-e-d-b-a-c。

注-

• オイラーの回路には、グラフの各エッジが1回だけ含まれています。
• ハミルトニアンサイクルでは、グラフの一部のエッジをスキップできます。

例

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

ハミルトンパスの例

上記のグラフの場合-

• オイラーパスが存在する-false
• オイラー回路が存在する-false
• ハミルトニアンサイクルが存在する-true
• ハミルトニアンパスが存在する-true

Gには次数が奇数の4つの頂点があるため、通過できません。 内部エッジをスキップすることにより、グラフはすべての頂点を通過するハミルトニアンサイクルを持ちます。

グラフ理論-例

この章では、以前の章ですでに説明した概念を示すために、いくつかの標準的な例を取り上げます。

例1

次のグラフでスパニングツリーの数を見つけます。

スパニングツリーの例

溶液

上記のグラフから得られたスパニングツリーの数は3です。 彼らは次のとおりです-

取得スパニングツリー

これらの3つは、指定されたグラフのスパニングツリーです。 ここで、グラフIとIIは互いに同型です。 明らかに、非同型スパニングツリーの数は2です。

例2

• 3つの頂点でいくつの単純な非同型グラフが可能ですか？*

溶液

3つの頂点で4つの非同型グラフが可能です。 それらを以下に示します。

非同型の例

実施例３

「G」を20個の頂点を持つ連結平面グラフとし、各頂点の次数は3です。 グラフ内の領域の数を見つけます。

溶液

度の定理の合計により、

[.intsuma]# 20 ∑ i=1 ＃deg（V〜i〜）= 2 | E |

20（3）= 2 | E |

|E| = 30

オイラーの公式により、

|V| + |R| = |E| + 2

20+ | R | = 30 + 2

|R| = 12

したがって、リージョンの数は12です。

実施例４

完全なグラフの色数K〜n〜

溶液

色番号の例

完全なグラフでは、各頂点は残りの（n–1）頂点に隣接しています。 したがって、各頂点には新しい色が必要です。 したがって、色数_K〜n〜= n_。

実施例５

次のグラフに一致する数字は何ですか？

溶液

マッチング番号の例

頂点の数= 9

一致できる頂点は8つだけです。

一致する番号は4です。

マッチング番号の例1

実施例６

次のグラフの数をカバーする線は何ですか？

溶液

回線カバー番号の例

頂点の数= | V | = n = 7

行カバー番号=（α〜1〜）≥⌈[.fraction]＃ n / 2 ＃⌉= 3

α〜1〜≥3

3つのエッジを使用することにより、すべての頂点をカバーできます。

したがって、ラインカバリング番号は3です。