グラフ理論-クイックガイド

数学とコンピュータサイエンスの分野では、グラフ理論は、辺と頂点の関係に関係するグラフの研究です。これは、コンピュータサイエンス、情報技術、生物科学、数学、言語学などに応用されている人気のある科目です。さらに面倒なことはせずに、グラフの定義から始めましょう。

グラフとは何ですか？

グラフは、オブジェクトのペアがリンクで接続されているオブジェクトのセットを図で表したものです。相互接続されたオブジェクトは、次のように呼ばれるポイントで表されます。vertices、および頂点を接続するリンクは呼び出されます edges。

正式には、グラフはセットのペアです (V, E)、 どこ Vは頂点のセットであり、Eは頂点のペアを接続するエッジのセットです。次のグラフを見てください-

上のグラフでは、

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

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

グラフ理論の応用

グラフ理論は、工学のさまざまな分野で応用されています。

Electrical Engineering−グラフ理論の概念は、回路接続の設計に広く使用されています。接続のタイプまたは編成は、トポロジーと呼ばれます。トポロジの例としては、スタートポロジ、ブリッジトポロジ、シリーズトポロジ、およびパラレルトポロジがあります。

Computer Science−アルゴリズムの研究にはグラフ理論が使用されます。例えば、

• クラスカルのアルゴリズム
• プリムのアルゴリズム
• ダイクストラのアルゴリズム

Computer Network −ネットワーク内の相互接続されたコンピューター間の関係は、グラフ理論の原則に従います。

Science −物質の分子構造や化学構造、生物のDNA構造などをグラフで表しています。

Linguistics −言語の構文解析ツリーと言語の文法はグラフを使用します。

General−都市間のルートはグラフを使用して表すことができます。家系図などの階層的な順序情報を描くことは、ツリーと呼ばれる特殊なタイプのグラフとして使用できます。

グラフは、ポイントとポイントに接続された線の図です。2つの頂点のセットを結ぶ線が少なくとも1つあり、頂点がそれ自体を接続していません。グラフ理論におけるグラフの概念は、点、線、頂点、辺、頂点の次数、グラフの特性などのいくつかの基本的な用語に基づいています。ここでは、この章では、グラフ理論のこれらの基礎について説明します。

ポイント

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

例

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

ライン

A Line2点間の接続です。実線で表すことができます。

Example

ここで、「a」と「b」がポイントです。これらの2点間のリンクは線と呼ばれます。

バーテックス

頂点は、複数の線が交わる点です。とも呼ばれますnode。ポイントと同様に、頂点もアルファベットで示されます。

Example

ここで、頂点はアルファベット「a」で名前が付けられています。

縁

エッジは、2つの頂点を結ぶ線の数学用語です。1つの頂点から多くのエッジを形成できます。頂点がないと、エッジを形成できません。エッジの開始頂点と終了頂点が必要です。

Example

ここで、「a」と「b」は2つの頂点であり、それらの間のリンクはエッジと呼ばれます。

グラフ

グラフ「G」は、G =（V、E）として定義されます。ここで、Vはすべての頂点のセットであり、Eはグラフ内のすべてのエッジのセットです。

Example 1

上記の例では、ab、ac、cd、およびbdがグラフのエッジです。同様に、a、b、c、およびdはグラフの頂点です。

Example 2

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

ループ

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

Example 1

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

Example 2

このグラフでは、頂点aと頂点bに形成される2つのループがあります。

頂点の次数

頂点Vに隣接する頂点の数です。

Notation − deg（V）。

n個の頂点を持つ単純なグラフでは、任意の頂点の次数は−です。

deg（v）≤n–1∀v∈G

頂点は、それ自体を除いて、他のすべての頂点とエッジを形成できます。したがって、頂点の次数は最大になりますnumber of vertices in the graph minus 1。この1は、それ自体ではループを形成できないため、自己頂点用です。いずれかの頂点にループがある場合、それは単純なグラフではありません。

頂点の次数は、グラフの2つのケースで考慮することができます-

• 無向グラフ

• 有向グラフ

無向グラフの頂点の次数

無向グラフには有向エッジがありません。次の例を検討してください。

Example 1

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

上記の無向グラフでは、

• 頂点 'a'で交わる2つのエッジがあるため、deg（a）= 2です。

• 頂点 'b'で交わる3つのエッジがあるため、deg（b）= 3。

• 頂点 'c'に1つのエッジが形成されているため、deg（c）= 1

• したがって、「c」は pendent vertex。

• 頂点 'd'で交わる2つのエッジがあるため、deg（d）= 2です。

• 頂点 'e'に0個のエッジが形成されているため、deg（e）= 0です。

• したがって、「e」は isolated vertex。

Example 2

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

上のグラフでは、

deg（a）= 2、deg（b）= 2、deg（c）= 2、deg（d）= 2、およびdeg（e）= 0。

頂点 'e'は孤立した頂点です。グラフにはペンダント頂点がありません。

有向グラフの頂点の次数

有向グラフでは、各頂点に indegree と outdegree。

グラフの程度

• 頂点Vの次数は、頂点Vに入るエッジの数です。

• Notation − deg−（V）。

グラフのアウトディグリー

• 頂点Vのアウトディグリーは、頂点Vから出て行くエッジの数です。

• Notation − deg +（V）。

次の例を検討してください。

Example 1

次の有向グラフを見てください。頂点「a」には、「ad」と「ab」の2つのエッジがあり、これらは外側に向かっています。したがって、そのアウトディグリーは2です。同様に、頂点 'a'に向かってくるエッジ 'ga'があります。したがって、「a」の次数は1です。

他の頂点のインディグリーとアウトディグリーを次の表に示します-

バーテックス	インディグリー	アウトディグリー
a	1	2
b	2	0
c	2	1
d	1	1
e	1	1
f	1	1
g	0	2

Example 2

次の有向グラフを見てください。頂点 'a'には、頂点 'a'から外側に向かうエッジ 'ae'があります。したがって、そのアウトディグリーは1です。同様に、グラフには頂点「a」に向かうエッジ「ba」があります。したがって、「a」の次数は1です。

他の頂点のインディグリーとアウトディグリーを次の表に示します-

バーテックス	インディグリー	アウトディグリー
a	1	1
b	0	2
c	2	0
d	1	1
e	1	1

ペンダント頂点

頂点の次数を使用することにより、2つの特別なタイプの頂点があります。次数1の頂点は、ペンダント頂点と呼ばれます。

Example

ここで、この例では、頂点「a」と頂点「b」に接続されたエッジ「ab」があります。したがって、頂点「a」に関しては、頂点「b」に向かってエッジが1つだけであり、同様に、頂点「b」に関しては、頂点「a」に向かってエッジが1つだけです。最後に、頂点 'a'と頂点 'b'の次数は、ペンダント頂点とも呼ばれます。

孤立した頂点

次数がゼロの頂点は、孤立頂点と呼ばれます。

Example

ここで、頂点 'a'と頂点 'b'は、相互に接続されておらず、他の頂点にも接続されていません。したがって、頂点「a」と「b」の両方の次数はゼロです。これらは、孤立した頂点とも呼ばれます。

隣接性

ここに隣接の規範があります-

• グラフでは、2つの頂点は adjacent、2つの頂点の間にエッジがある場合。ここで、頂点の隣接性は、これら2つの頂点を接続している単一のエッジによって維持されます。

• グラフでは、2つのエッジの間に共通の頂点がある場合、2つのエッジは隣接していると言われます。ここで、エッジの隣接性は、2つのエッジを接続している単一の頂点によって維持されます。

Example 1

上のグラフでは-

• 「a」と「b」は隣接する頂点です。これらの間に共通のエッジ「ab」があるためです。

• 「a」と「d」は隣接する頂点です。これらの間に共通のエッジ「ad」があるためです。

• ab 'と' be 'は隣接するエッジです。これは、それらの間に共通の頂点' b 'があるためです。

• be 'と' de 'は隣接するエッジであり、それらの間に共通の頂点' e 'があります。

Example 2

上のグラフでは-

• 「a」と「d」は隣接する頂点です。これらの間に共通のエッジ「ad」があるためです。

• 「c」と「b」は隣接する頂点です。これらの間に共通のエッジ「cb」があるためです。

• 「ad」と「cd」は隣接するエッジです。これらの間に共通の頂点「d」があるためです。

• 「ac」と「cd」は隣接するエッジです。これらの間に共通の頂点「c」があるためです。

平行辺

グラフでは、頂点のペアが複数のエッジで接続されている場合、それらのエッジは平行エッジと呼ばれます。

上のグラフでは、「a」と「b」は、それらの間の2つのエッジ「ab」と「ab」によって接続されている2つの頂点です。したがって、それは平行エッジと呼ばれます。

マルチグラフ

平行なエッジを持つグラフは、マルチグラフと呼ばれます。

Example 1

上のグラフには、「ab」、「ac」、「cd」、「cd」、「bd」の5つのエッジがあります。'c'と 'd'の間に2つの平行なエッジがあるため、マルチグラフになります。

Example 2

上のグラフでは、頂点「b」と「c」に2つのエッジがあります。頂点「e」と「d」にも2つのエッジがあります。したがって、それはマルチグラフです。

グラフの次数シーケンス

グラフ内のすべての頂点の次数が降順または昇順で配置されている場合、取得されたシーケンスはグラフの次数シーケンスと呼ばれます。

Example 1

バーテックス	A	b	c	d	e
への接続	紀元前	広告	広告	c、b、e	d
程度	2	2	2	3	1

上のグラフでは、頂点{d、a、b、c、e}の場合、次数シーケンスは{3、2、2、2、1}です。

Example 2

バーテックス	A	b	c	d	e	f
への接続	b、e	交流	b、d	c、e	広告	-
程度	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つの頂点から別の頂点へのパスはいくつでも存在できます。その中から、最短のものだけを選択する必要があります。

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 ₁、V ₂、… _Vn }の無向グラフである場合

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

Corollary 1

G =（V、E）が頂点V = {V ₁、V ₂、… _Vn }の有向グラフである場合、

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

Corollary 2

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

Corollary 3

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

k | V | = 2 | E |

Corollary 4

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

k | V | ≤2| E |

| Corollary 5

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

k | V | ≥2| E |

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

空グラフ

A graph having no edges ヌルグラフと呼ばれます。

例

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

トリビアルグラフ

A graph with only one vertex トリビアルグラフと呼ばれます。

例

上に示したグラフでは、頂点 '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」とは異なることに注意してください。

シンプルなグラフ

グラフ with no loops といいえ parallel edges 単純グラフと呼ばれます。

• 'N'の頂点を持つ単一のグラフで可能なエッジの最大数は^N C ₂ここで^、N C ₂ = N（N - 1）/ 2。

• 'n'頂点= 2 _{ⁿ c 2} = 2 ^{n（n-1）/ 2で}可能な単純なグラフの数。

例

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

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

ⁿ C ₂ = n（n–1）/ 2

= 3（3–1）/ 2

= 6/2

= 3つのエッジ

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

2 _{ⁿ C 2} = 2 ^{n（n-1）/ 2}

= 2 ^{3（3-1）/ 2}

= 2 ³

8

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

コネクテッドグラフ

グラフGは接続されていると言われています if there exists a path between every pair of vertices。グラフのすべての頂点に少なくとも1つのエッジが必要です。つまり、エッジの反対側にある他の頂点に接続されていると言えます。

例

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

切断されたグラフ

グラフGには、接続された頂点が2つ以上含まれていない場合、切断されます。

例1

次のグラフは、切断されたグラフの例です。1つは「a」、「b」、「c」、「d」の頂点を持ち、もう1つは「e」、「f」、「g」、 'h'頂点。

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

例2

この例では、abfeとcdの2つの独立したコンポーネントがあり、これらは互いに接続されていません。したがって、これは切り離されたグラフです。

正則グラフ

グラフGは規則的であると言われていますが、 if all its vertices have the same degree。グラフでは、各頂点の次数が「k」の場合、そのグラフは「k-正則グラフ」と呼ばれます。

例

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

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

完全グラフ

'n'の相互頂点を持つ単純なグラフは完全グラフと呼ばれ、 denoted by ‘K_n’。グラフでは、a vertex should have edges with all other vertices、それからそれは完全グラフと呼ばれました。

言い換えると、頂点がグラフ内の他のすべての頂点に接続されている場合、それは完全グラフと呼ばれます。

例

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

グラフIでは、

	a	b	c
a	接続されていません	接続済み	接続済み
b	接続済み	接続されていません	接続済み
c	接続済み	接続済み	接続されていません

グラフIIでは、

	p	q	r	s
p	接続されていません	接続済み	接続済み	接続済み
q	接続済み	接続されていません	接続済み	接続済み
r	接続済み	接続済み	接続されていません	接続済み
s	接続済み	接続済み	接続済み	接続されていません

サイクルグラフ

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

グラフの各頂点の次数が2の場合、それは閉路グラフと呼ばれます。

Notation− _cn

例

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

• グラフIには、サイクル「ab-bc-ca」を形成している3つのエッジを持つ3つの頂点があります。

• グラフIIには、サイクル「pq-qs-sr-rp」を形成している4つのエッジを持つ4つの頂点があります。

• グラフIIIには、サイクル「ik-km-ml-lj-ji」を形成している5つのエッジを持つ5つの頂点があります。

したがって、与えられたすべてのグラフは閉路グラフです。

ホイールグラフ

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

表記法- W _N

Wのエッジの_数n =ハブから他のすべての頂点までのエッジの数+

ハブのない閉路グラフの他のすべてのノードからのエッジの数。

=（n–1）+（n–1）

= 2（n–1）

例

次のグラフを見てください。それらはすべてホイールグラフです。

グラフIにおいて、Cから得られる₃「D」と命名中央に頂点を追加することによって。これは、Wと表記される₄。

W4のエッジの数= 2（n-1）= 2（3）= 6

グラフIIでは、C4から「t」という名前の頂点を中央に追加することで取得されます。これは、Wと表記される₅。

W5のエッジの数= 2（n-1）= 2（4）= 8

グラフIIIには、Cから得られる₆「O」と命名中央に頂点を追加することによって。これは、Wと表記される₇。

W4のエッジの数= 2（n-1）= 2（6）= 12

閉路グラフ

グラフ with at least one サイクルは循環グラフと呼ばれます。

例

上記のグラフの例では、abcdaとcfgecの2つのサイクルがあります。したがって、それは閉路グラフと呼ばれます。

非巡回グラフ

グラフ with no cycles 非巡回グラフと呼ばれます。

例

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

2部グラフ

頂点パーティションVとの単純なグラフG =（V、E）= {V ₁ V、₂部グラフと呼ばれています}if every edge of E joins a vertex in V1 to a vertex in V₂。

一般に、Bipertiteグラフ頂点の二組を有している、私たちは、言うV1とV2、およびエッジが描かれている場合、それはセットV内の任意の頂点を接続する必要がありましょう₁セットV内の任意の頂点に₂。

例

V -このグラフでは、頂点の二組を観察することができます₁及びV _2を。ここで、「AE」と「BD」という名前の2つの縁部は、二組のVの頂点接続されている₁及びV ₂。

完全2部グラフ

パーティションVとの二部グラフ「G」、G =（V、E）= {V ₁、V _2は} V内のすべての頂点の場合、完全な二部グラフであることが言われている_1がVのすべての頂点に接続されている₂。

一般に、完全な二部グラフは、集合Vの各頂点を接続する₁セットVから各頂点に₂。

例

それは集合Vの各頂点を接続するエッジ持っているので、次のグラフは、完全な二部グラフである₁組のVから各頂点に₂。

| V ₁ |の場合 = mおよび| V ₂ | = nの場合、完全2部グラフはK _m、nで表されます。

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

一般的に、 complete bipartite graph is not a complete graph。

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

n個の頂点を持つ2部グラフのエッジの最大数は-です。

[N ² /4]

もしN = 10、K5、5 = [N 2/4] = [10 ² /4] = 25。

同様に、K6、4 = 24

K7、3 = 21

K8、2 = 16

K9、1 = 9

n = 9の場合、k5、4 = [n2 / 4] = [92/4] = 20

同様に、K6、3 = 18

K7、2 = 14

K8、1 = 8

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

スターグラフ

K1、n-1の形式の完全2部グラフは、n個の頂点を持つスターグラフです。スターグラフは、1つの頂点が一方のセットに属し、残りのすべての頂点がもう一方のセットに属している場合、完全2部グラフです。

例

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

グラフの補集合

エッジがGに存在しない場合、「G-」を「G」の頂点と同じようにいくつかの頂点を持ち、エッジ{U、V}が「G-」に存在する単純なグラフとします。つまり、2つの頂点が隣接しています。 2つの頂点がGで隣接していない場合は、「G-」で。

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

例

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

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

Note − 2つの補グラフを組み合わせると、完全なグラフが得られます。

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

| E（G）| + | E（ 'G-'）| = | E（Kn）|、ここでn =グラフ内の頂点の数。

例

'G'を9つの頂点と12のエッジを持つ単純なグラフとし、 'G-'のエッジの数を見つけます。

あなたが持っている、| E（G）| + | E（ 'G-'）| = | E（Kn）|

12 + | E（ 'G-'）| =

9（9-1）/ 2 = ⁹ C ₂

12 + | E（ 'G-'）| = 36

| E（ 'G-'）| = 24

「G」は40個のエッジを持つ単純なグラフであり、その補集合「G-」には38個のエッジがあります。グラフGまたは「G-」で頂点の数を見つけます。

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

| E（G）| + | E（ 'G-'）| = | E（Kn）|

40 + 38 = n（n-1）/ 2

156 = n（n-1）

13（12）= n（n-1）

n = 13

ツリーは、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です。

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

接続性

グラフは connected if there is a path between every pair of vertex。すべての頂点から他の頂点まで、トラバースするためのパスが必要です。これは、グラフの接続性と呼ばれます。複数の頂点とエッジが切断されているグラフは、切断されていると言われます。

Example 1

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

Example 2

次の例では、頂点 'a'から頂点 'f'へのトラバースは、それらの間に直接または間接的にパスがないため不可能です。したがって、それは切り離されたグラフです。

切断点

'G'を連結グラフとします。頂点V∈Gは、「G-V」（「G」から「V」を削除）によってグラフが切断される場合、「G」の切断点と呼ばれます。グラフから切断点を削除すると、2つ以上のグラフに分割されます。

Note −切断点を削除すると、グラフが切断される場合があります。

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

Example

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

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

'g'がないと、頂点 'c'と頂点 'h'および他の多くの間にパスがありません。したがって、それは切断点が「e」である切断されたグラフです。同様に、「c」も上のグラフの切断点です。

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

'G'を連結グラフとします。エッジ 'e'∈Gは、' G-e 'によってグラフが切断される場合、カットエッジと呼ばれます。

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

Example

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

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

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

Note −「G」を「n」個の頂点を持つ連結グラフとすると、

• エッジ 'e'がGのどのサイクルの一部でもない場合に限り、カットエッジe∈G。

• 可能なカットエッジの最大数は「n-1」です。

• 切断されたエッジの少なくとも1つの頂点が切断された頂点であるため、切断されたエッジが存在する場合は常に、切断された頂点も存在します。

• 切断点が存在する場合、切断エッジが存在する場合と存在しない場合があります。

グラフのカットセット

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

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

Example

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

グラフからカットセットE1を削除すると、次のように表示されます。

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

• E3 = {e9} –グラフの最小カットセット。

• E4 = {e3、e4、e5}

エッジ接続

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

Notation −λ（G）

言い換えれば、 number of edges in a smallest cut set of G Gのエッジ接続と呼ばれます。

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

Example

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

2つのエッジを削除してグラフを切断する4つの方法は次のとおりです-

頂点接続

'G'を連結グラフとします。削除によって「G」が切断されるか、「G」が簡単なグラフに縮小される頂点の最小数は、頂点接続と呼ばれます。

Notation − K（G）

Example

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

Gに切断点がある場合、K（G）= 1です。

Notation −接続されたグラフGの場合、

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

頂点連結（K（G））、エッジ連結（λ（G））、G（δ（G））の最小度数。

Example

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

Solution

グラフから、

δ（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

カバーグラフは、他のグラフに対応するすべての頂点またはすべてのエッジを含むサブグラフです。すべての頂点を含むサブグラフは、line/edge covering。すべてのエッジを含むサブグラフは、vertex covering。

ラインカバー

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

deg（V）≥1∀V∈G

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

Example

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

ラインカバーのあるサブグラフは次のとおりです。

C ₁ = {{a、b}、{c、d}}

C ₂ = {{a、d}、{b、c}}

C ₃ = {{a、b}、{b、c}、{b、d}}

C ₄ = {{a、b}、{b、c}、{c、d}}

'G'が孤立した頂点を持っている場合に限り、 'G'のラインカバーは存在しません。'n'頂点を持つグラフの線被覆には、少なくとも[n / 2]個のエッジがあります。

最小限のラインカバー

グラフGのCを覆う線は最小と言われます if no edge can be deleted from C。

Example

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

C ₁ = {{a、b}、{c、d}}

C ₂ = {{a、d}、{b、c}}

C ₃ = {{a、b}、{b、c}、{b、d}}

C ₄ = {{a、b}、{b、c}、{c、d}}

ここで、C ₁、C ₂、C ₃は最小限のラインカバーですが、C ₄は{b、c}を削除できるためではありません。

最小ラインカバー

としても知られています Smallest Minimal Line Covering。エッジの数が最小の最小ラインカバーは、「G」の最小ラインカバーと呼ばれます。'G'でカバーする最小ラインのエッジの数は、line covering number（α 'G'の₁）。

Example

上記の例では、C ₁及びC _2は、 Gの被覆最小線であり、α ₁ = 2。

• すべてのラインカバーには、最小限のラインカバーが含まれています。

• 被覆最小線が含まれていないすべての行被覆（C _3は、任意の最小線被覆を含んでいません。

• 最小限のラインカバーにはサイクルが含まれていません。

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

頂点被覆

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

Example

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

上記のグラフから導き出せるサブグラフは次のとおりです。

K ₁ = {b、c}

K ₂ = {a、b、c}

K ₃ = {b、c、d}

K ₄ = {a、d}

ここで、K ₁、K ₂、およびK _3には頂点被覆がありますが、K ₄はエッジ{bc}を覆わないため、頂点被覆はありません。

最小限の頂点被覆

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

Example

上のグラフで、頂点被覆を持つサブグラフは次のとおりです。

K ₁ = {b、c}

K ₂ = {a、b、c}

K ₃ = {b、c、d}

ここで、K ₁及びK _2は、 Kで、一方、最小頂点被覆されている₃、頂点「d」は削除することができます。

Minimum Vertex Covering

It is also known as the smallest minimal vertex covering. A minimal vertex covering of graph ‘G’ with minimum number of vertices is called the minimum vertex covering.

The number of vertices in a minimum vertex covering of ‘G’ is called the vertex covering number of G (α₂).

Example

In the following graph, the subgraphs having vertex covering are as follows −

K₁ = {b, c}

K₂ = {a, b, c}

K₃ = {b, c, d}

Here, K₁ is a minimum vertex cover of G, as it has only two vertices. α₂ = 2.

A matching graph is a subgraph of a graph where there are no edges adjacent to each other. Simply, there should not be any common vertex between any two edges.

Matching

Let ‘G’ = (V, E) be a graph. A subgraph is called a matching M(G), if each vertex of G is incident with at most one edge in M, i.e.,

deg(V) ≤ 1 ∀ V ∈ G

which means in the matching graph M(G), the vertices should have a degree of 1 or 0, where the edges should be incident from the graph G.

Notation − M(G)

Example

In a matching,

if deg(V) = 1, then (V) is said to be matched

if deg(V) = 0, then (V) is not matched.

In a matching, no two edges are adjacent. It is because if any two edges are adjacent, then the degree of the vertex which is joining those two edges will have a degree of 2 which violates the matching rule.

Maximal Matching

A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M.

Example

M1, M2, M3 from the above graph are the maximal matching of G.

Maximum Matching

It is also known as largest maximal matching. Maximum matching is defined as the maximal matching with maximum number of edges.

The number of edges in the maximum matching of ‘G’ is called its matching number.

Example

For a graph given in the above example, M1 and M2 are the maximum matching of ‘G’ and its matching number is 2. Hence by using the graph G, we can form only the subgraphs with only 2 edges maximum. Hence we have the matching number as two.

Perfect Matching

A matching (M) of graph (G) is said to be a perfect match, if every vertex of graph g (G) is incident to exactly one edge of the matching (M), i.e.,

deg(V) = 1 ∀ V

The degree of each and every vertex in the subgraph should have a degree of 1.

Example

In the following graphs, M1 and M2 are examples of perfect matching of G.

Note − Every perfect matching of graph is also a maximum matching of graph, because there is no chance of adding one more edge in a perfect matching graph.

A maximum matching of graph need not be perfect. If a graph ‘G’ has a perfect match, then the number of vertices |V(G)| is even. If it is odd, then the last vertex pairs with the other vertex, and finally there remains a single vertex which cannot be paired with any other vertex for which the degree is zero. It clearly violates the perfect matching principle.

Example

Note − The converse of the above statement need not be true. If G has even number of vertices, then M1 need not be perfect.

Example

It is matching, but it is not a perfect match, even though it has even number of vertices.

Independent sets are represented in sets, in which

• there should not be any edges adjacent to each other. There should not be any common vertex between any two edges.

• there should not be any vertices adjacent to each other. There should not be any common edge between any two vertices.

Independent Line Set

Let ‘G’ = (V, E) be a graph. A subset L of E is called an independent line set of ‘G’ if no two edges in L are adjacent. Such a set is called an independent line set.

Example

Let us consider the following subsets −

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

In this example, the subsets L2 and L3 are clearly not the adjacent edges in the given graph. They are independent line sets. However L1 is not an independent line set, as for making an independent line set, there should be at least two edges.

Maximal Independent Line Set

An independent line set is said to be the maximal independent line set of a graph ‘G’ if no other edge of ‘G’ can be added to ‘L’.

Example

Let us consider the following subsets −

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

L₂ and L₃ are maximal independent line sets/maximal matching. As for only these two subsets, there is no chance of adding any other edge which is not an adjacent. Hence these two subsets are considered as the maximal independent line sets.

Maximum Independent Line Set

A maximum independent line set of ‘G’ with maximum number of edges is called a maximum independent line set of ‘G’.

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

Example

Let us consider the following subsets −

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

L₃ is the maximum independent line set of G with maximum edges which are not the adjacent edges in graph and is denoted by β1 = 3.

Note − For any graph G with no isolated vertex,

α1 + β1 = number of vertices in a graph = |V|

Example

Line covering number of K_n/C_n/w_n,

$$\alpha 1 = \lceil\frac{n}{2}\rceil\begin{cases}\frac{n}{2}\:if\:n\:is\:even \\\frac{n+1}{2}\:if\:n\:is\:odd\end{cases}$$

Line independent number (Matching number) = β₁ = [n/2] α₁ + β₁ = n.

Independent Vertex Set

Let ‘G’ = (V, E) be a graph. A subset of ‘V’ is called an independent set of ‘G’ if no two vertices in ‘S’ are adjacent.

Example

Consider the following subsets from the above graphs −

S1 = {e}

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

Clearly S₁ is not an independent vertex set, because for getting an independent vertex set, there should be at least two vertices in the from a graph. But here it is not that case. The subsets S₂, S₃, and S₄ are the independent vertex sets because there is no vertex that is adjacent to any one vertex from the subsets.

最大の独立した頂点セット

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

Example

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

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

S ₂とS _3が「G」の最大独立頂点集合です。Sでは₁及びS ₄、我々は他の頂点を追加することができます。しかしSで₂及びS ₃、我々は他の頂点を追加することはできません。

最大独立頂点セット

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

Example

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

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

S ₃のみが、最大数の頂点をカバーするため、最大の独立した頂点セットです。「G」の最大独立頂点集合の頂点の数はGの独立した頂点数（βと呼ばれる₂）。

Example

完全グラフKnの_場合、

頂点被覆番号=α ₂ = n-1の

頂点独立番号=β ₂ = 1

あなたはα持っている₂ +β ₂ = Nを

完全グラフでは、各頂点は残りの（n − 1）頂点に隣接しています。したがって、K _nの最大独立集合には、頂点が1つだけ含まれます。

したがって、β ₂ = 1

及びα ₂ = | V | - β ₂ = n-1の

Note −任意のグラフの場合 'G' =（V、E）

• α ₂ +β ₂ = | V |
• 「S」が「G」の独立した頂点セットである場合、（V – S）はGの頂点被覆です。

グラフ彩色は、いくつかの制約の下で頂点、エッジ、領域などのグラフコンポーネントにラベルを付ける簡単な方法に他なりません。グラフでは、2つの隣接する頂点、隣接するエッジ、または隣接する領域が最小数の色で色付けされていません。この番号は、chromatic number グラフは properly colored graph。

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

頂点彩色

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

彩色数

グラフ 'G'の頂点彩色に必要な最小色数はGの彩色数と呼ばれ、X（G）で表されます。

'G'が空グラフである場合に限り、χ（G）= 1。'G'が空グラフでない場合、χ（G）≥2。

Example

Note −グラフ 'G'は、最大n色を使用する頂点彩色がある場合（つまり、X（G）≤n）、n-coverableであると言われます。

地域のカラーリング

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

Example

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

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

Example

Knの彩色数は

• n
• n–1
• [n/2]
• [n/2]

Kと、この例を考える₄。

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

グラフ彩色の応用

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

• Clustering
• データマイニング
• 画像キャプチャ
• 画像セグメンテーション
• Networking
• 資源配分
• プロセスのスケジューリング

グラフは、同じ数の頂点、エッジ、および同じエッジ接続を持つさまざまな形式で存在できます。このようなグラフは同型グラフと呼ばれます。この章では、主にグラフを参照し、相互に認識することを目的として、グラフにラベルを付けていることに注意してください。

同型グラフ

二つのグラフG ₁及びG _2が場合同型であると言われています-

• コンポーネント（頂点とエッジ）の数は同じです。

• それらのエッジ接続は保持されます。

Note−要するに、2つの同型グラフのうち、一方は他方の微調整バージョンです。ラベルのないグラフは、同型グラフと考えることもできます。

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.

Note

Gもし₁ ≡G ₂、次いで-

| V（G ₁）| = | V（G ₂）|

| E（G ₁）| = | E（G ₂）|

Gの程度の配列₁及びG _2は同一です。

頂点場合{V ₁、V ₂、.. Vkは} Gにおける長さKのサイクルを形成する₁は、頂点{F（V ₁）、F（V ₂）、...、F（VKが）}サイクルを形成すべきですGの長さKの₂。

グラフGのために上記のすべての条件が必要である₁及びG _2は、グラフは同型であることを証明するのに十分な同形ではなくなるように。

• （G ₁ ≡G ₂）及び場合だけ（G ₁ - ≡G ₂ - ）ここで、G ₁及びG _2は、単純なグラフです。

• （G ₁ ≡G ₂）Gの隣接行列場合₁及びG _2は同一です。

• （G ₁ ≡G ₂）であれば、Gの対応するサブグラフ場合にのみ₁とG ₂（グラフGにおいて、いくつかのG1内の頂点とその画像を削除することによって得られる₂）同型です。

Example

次のグラフのどれが同型ですか？

グラフGにおいて₃、3のみ度を有する「W」頂点は、他のすべてのグラフの頂点に対し、したがってGと同形ではないG3度2を有する₁又はG ₂。

Gの補撮影₁およびG _2を、あなたが持っています-

ここで、（G ₁ - ≡G ₂ - ）、したがって（G ₁ ≡G ₂）。

平面グラフ

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

Example

地域

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

Example

有界領域の次数 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

平面グラフでは、次のプロパティが有効です。

'n'個の頂点を持つ平面グラフでは、すべての頂点の次数の合計は-です。

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

による Sum of Degrees of Regions/定理、「n」個の領域を持つ平面グラフでは、領域の次数の合計は−です。

nΣi= 1 deg（ri）= 2 | E |

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

平面グラフでは、

各領域の次数がKの場合、領域の次数の合計は-です。

K | R | = 2 | E |

各領域の次数が少なくともK（≥K）である場合、

K | R | ≤2| E |

各領域の次数が最大でK（≤K）の場合、

K | R | ≥2| E |

Note −すべての領域の次数が同じであると想定します。

による Euler’s Formulae 平面グラフでは、

グラフ「G」が接続された平面である場合、

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

'K'成分を含む平面グラフの場合、

| V | + | R | = | E | +（K + 1）

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

エッジ頂点の不等式

'G'が、各領域の次数が少なくとも 'K'である接続された平面グラフである場合、

| E | ≤k/（k-2）{| v | --2}

あなたが知っている、| V | + | R | = | E | + 2

K. | R | ≤2| E |

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

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

| E | ≤k/（k-2）{| v | --2}

'G'が単純な接続平面グラフの場合、

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

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

'G'が単純な接続平面グラフ（少なくとも2つのエッジを持つ）であり、三角形がない場合、

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

クラトフスキの定理

グラフ「G」は、非平面である場合に「G」はKに同相であるサブグラフている場合にのみ₅またはK _3,3。

準同型

二つのグラフG ₁及びG _2は、これらのグラフのそれぞれが複数の頂点とGの一部のエッジを分割して同じグラフ「G」から得ることができる場合には、準同型であると言われます。次の例を見てください-

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

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

G場合_1がGと同形である₂は、GはG2に同相であるが、逆必要が真ではありません。

• 頂点が4つ以下のグラフはすべて平面です。

• エッジが8以下のグラフはすべて平面です。

• 完全グラフK _nが平面の場合に限り、N≤4です。

• 完全2部グラフKm _、nは_、 m≤2またはn≤2の場合に限り、平面です。

• 頂点の最小数を有する単純な非平面グラフは、完全グラフKである₅。

• エッジの最小数を有する単純な非平面グラフはKである_3,3。

多面体グラフ

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

• 3 | V | ≤2| E |

• 3 | R | ≤2| E |

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

オイラーの道

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

Example

オイラーのパス= dcabde。

オイラー回路

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

Example

Euler’s Path = abcdagfeca。

オイラーの回路定理

連結グラフ「G」は、Gの次数が奇数の頂点の数が正確に2または0である場合にのみトラバース可能です。連結グラフGは、オイラーのパスを含むことができますが、オイラーの回路を含めることはできません。奇妙な程度。

Note −このオイラーパスは、奇数次数の頂点で始まり、奇数次数の他の頂点で終わります。

Example

Euler’s Path− beabdcaはオイラーの回路ではありませんが、オイラーの経路です。明らかに、2つの奇数次数の頂点があります。

Note −連結グラフGで、次数が奇数の頂点の数= 0の場合、オイラーの回路が存在します。

ハミルトングラフ

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

すべてのサイクルは回路ですが、回路には複数のサイクルが含まれる場合があります。このようなサイクルは、Hamiltonian cycle Gの。

ハミルトンパス

接続されたグラフは、Gの各頂点が1回だけ含まれている場合、ハミルトンと呼ばれます。このようなパスは、Hamiltonian path。

Example

Hamiltonian Path−edbac。

Note

• オイラーの回路には、グラフの各エッジが1回だけ含まれています。

• ハミルトン閉路では、グラフの一部のエッジをスキップできます。

Example

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

上記のグラフの場合-

• オイラーパスが存在します– false

• オイラー回路が存在する– false

• ハミルトン閉路が存在する– true

• ハミルトン経路が存在する– true

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

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

例1

Find the number of spanning trees in the following graph.

解決

上のグラフから得られた全域木の数は3本です。

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

例2

How many simple non-isomorphic graphs are possible with 3 vertices?

解決

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

例3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

解決

度の定理の合計により、

20Σi= 1 deg（Vi）= 2 | E |

20（3）= 2 | E |

| E | = 30

オイラーの公式により、

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

20歳以上| R | = 30 + 2

| R | = 12

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

例4

What is the chromatic number of complete graph K_n?

解決

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

例5

What is the matching number for the following graph?

解決

頂点の数= 9

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

一致する番号は4です。

例6

What is the line covering number of for the following graph?

解決

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

行カバー数=（α ₁）≥[N / 2] = 3

α ₁ ≥3

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

したがって、番号をカバーする行は3です。