グラフとグラフモデル

前のパートでは、推論、校正、問題解決のためのさまざまなツールを紹介しました。このパートでは、多くの現実の問題を定式化する基礎を形成する離散構造を研究します。

ここで取り上げる2つの離散構造は、グラフとツリーです。グラフは、ノードまたは頂点と呼ばれる点のセットであり、エッジと呼ばれる線のセットによって相互接続されています。グラフの研究、またはgraph theory は、数学、工学、コンピュータサイエンスの分野における多くの分野の重要な部分です。

グラフとは何ですか？

Definition −グラフ（$ G =（V、E）$として示される）は、空でない頂点またはノードのセットVとエッジのセットEで構成されます。

Example −グラフは$ G =（V、E）$であると考えてみましょう。ここで、$ V = \ lbrace a、b、c、d \ rbrace $および$ E = \ lbrace \ lbrace a、b \ rbrace、\ lbrace a 、c \ rbrace、\ lbrace b、c \ rbrace、\ lbrace c、d \ rbrace \ rbrace $

Degree of a Vertex −グラフGの頂点Vの次数（deg（V）で示される）は、頂点Vに入射するエッジの数です。

バーテックス	程度	偶数/奇数
A	2	でも
b	2	でも
c	3	奇数
d	1	奇数

Even and Odd Vertex −頂点の次数が偶数の場合、その頂点は偶数の頂点と呼ばれ、頂点の次数が奇数の場合、その頂点は奇数の頂点と呼ばれます。

Degree of a Graph−グラフの次数は、そのグラフの最大の頂点次数です。上記のグラフの場合、グラフの次数は3です。

The Handshaking Lemma −グラフでは、すべての頂点のすべての次数の合計は、エッジの数の2倍に等しくなります。

グラフの種類

グラフにはさまざまな種類があり、次のセクションで学習します。

空グラフ

空グラフにはエッジがありません。$ n $頂点の空グラフは$ N_n $で表されます

シンプルなグラフ

グラフが無向であり、ループや複数のエッジが含まれていない場合、グラフは単純グラフ/厳密グラフと呼ばれます。

マルチグラフ

グラフで同じ頂点のセット間の複数のエッジが許可されている場合、それはマルチグラフと呼ばれます。言い換えれば、それは少なくとも1つのループまたは複数のエッジを持つグラフです。

有向グラフと無向グラフ

グラフ$ G =（V、E）$は、エッジセットが順序付けられた頂点ペアで構成されている場合は有向グラフと呼ばれ、エッジセットが順序付けられていない頂点ペアで構成されている場合はグラフは無向グラフと呼ばれます。

接続および切断されたグラフ

グラフの任意の2つの頂点がパスで接続されている場合、グラフは接続されます。グラフの少なくとも2つの頂点がパスで接続されていない場合、グラフは切断されます。グラフGが切断されている場合、$ G $のすべての最大連結部分グラフは、グラフ$ G $の連結成分と呼ばれます。

正則グラフ

グラフのすべての頂点の次数が同じである場合、グラフは正則です。次数$ r $の正則グラフGでは、$ G $の各頂点の次数はrです。

完全グラフ

2つの頂点ペアごとに1つのエッジが結合されている場合、グラフは完全グラフと呼ばれます。n個の頂点を持つ完全グラフは$ K_n $で表されます

サイクルグラフ

グラフが単一のサイクルで構成されている場合、それはサイクルグラフと呼ばれます。n個の頂点を持つ閉路グラフは$ C_n $で表されます

2部グラフ

グラフGの頂点セットを$ V_1 $と$ V_2 $の2つのばらばらのセットに分割して、グラフの各エッジが$ V_1 $の頂点を$ V_2 $の頂点に結合できる場合。また、Gには$ V_1 $の2つの頂点または$ V_2 $の2つの頂点を接続するエッジがないため、グラフ$ G $は2部グラフと呼ばれます。

完全2部グラフ

完全2部グラフは、最初のセットの各頂点が2番目のセットのすべての単一頂点に結合されている2部グラフです。完全2部グラフは$ K_ {x、y} $で表され、グラフ$ G $には最初のセットに$ x $の頂点が含まれ、2番目のセットに$ y $の頂点が含まれます。

グラフの表現

グラフを表現する方法は主に2つあります-

隣接行列
隣接リスト

隣接行列

隣接行列$ A [V] [V] $は、サイズ$ V \ times V $の2D配列です。ここで、$ V $は無向グラフの頂点の数です。$ V_x $と$ V_y $の間にエッジがある場合、$ A [V_x] [V_y] = 1 $と$ A [V_y] [V_x] = 1 $の値、それ以外の場合、値はゼロになります。また、有向グラフの場合、$ V_x $と$ V_y $の間にエッジがある場合は、$ A [V_x] [V_y] = 1 $の値になります。それ以外の場合、値はゼロになります。

Adjacency Matrix of an Undirected Graph

次の無向グラフを考えて、隣接行列を作成しましょう。

上記の無向グラフの隣接行列は次のようになります。

	a	b	c	d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

Adjacency Matrix of a Directed Graph

次の有向グラフを考えて、その隣接行列を作成しましょう。

上記の有向グラフの隣接行列は次のようになります。

	a	b	c	d
a	0	1	1	0
b	0	0	1	0
c	0	0	0	1
d	0	0	0	0

隣接リスト

隣接リストでは、リンクリストの配列$（A [V]）$を使用して、頂点の数が$ V $のグラフGを表します。エントリ$ A [V_x] $は、$ Vx-th $頂点に隣接する頂点のリンクリストを表します。無向グラフの隣接リストは下図のようになります−

平面グラフと非平面グラフ

Planar graph−グラフ$ G $は、エッジを交差させずに平面に描画できる場合、平面グラフと呼ばれます。エッジが交差せずに平面にグラフを描く場合、それは平面へのグラフの埋め込みと呼ばれます。

Non-planar graph −グラフのエッジが交差せずに平面に描画できない場合、グラフは非平面です。

同型

2つのグラフGとHに、同じ方法で接続された同じ数の頂点が含まれている場合、それらは同型グラフと呼ばれます（$ G \ cong H $で示されます）。

同型よりも非同型をチェックする方が簡単です。これらの次の条件のいずれかが発生した場合、2つのグラフは非同型です-

接続されているコンポーネントの数が異なります
頂点セットのカーディナリティが異なります
エッジセットのカーディナリティが異なります
次数シーケンスが異なります

例

次のグラフは同型です-

準同型

グラフ$ G $からグラフ$ H $への準同型は写像です（全単射写像ではないかもしれません）$ h：G \ rightarrow H $次のように-$（x、y）\ in E（G）\ rightarrow （h（x）、h（y））\ in E（H）$。グラフ$ G $の隣接する頂点をグラフ$ H $の隣接する頂点にマップします。

準同型の性質

全単射写像の場合、準同型は同型です。
準同型は常にグラフのエッジと接続性を保持します。
準同型の構成も準同型です。
別のグラフの準同型グラフが存在するかどうかを調べることは、NP完全問題です。

オイラーグラフ

接続されたグラフ$ G $は、グラフ$ G $のすべてのエッジを含む閉じた軌跡がある場合、オイラーグラフと呼ばれます。オイラーパスは、グラフのすべてのエッジを1回だけ使用するパスです。オイラーパスは、さまざまな頂点で開始および終了します。

オイラー回路は、グラフのすべてのエッジを1回だけ使用する回路です。オイラー回路は常に同じ頂点で開始および終了します。連結グラフ$ G $は、$ G $のすべての頂点が偶数次である場合にのみオイラーグラフであり、連結グラフ$ G $は、そのエッジセットをサイクルに分解できる場合にのみオイラーグラフです。

上記のグラフは、$“ a \：1 \：b \：2 \：c \：3 \：d \：4 \：e \：5 \：c \：6 \：f \：7のオイラーグラフです。 \：g” $は、グラフのすべてのエッジをカバーします。

ハミルトングラフ

$ G $のすべての頂点を含む閉路があり、その閉路がハミルトン閉路と呼ばれる場合、連結グラフ$ G $はハミルトン閉路と呼ばれます。グラフ$ G $のハミルトンウォークは、各頂点を1回だけ通過するウォークです。

$ G $がn個の頂点を持つ単純なグラフである場合、ここで$ n \ geq 3 $各頂点$ v $に対して$ deg（v）\ geq \ frac {n} {2} $の場合、グラフ$ G $は次のようになります。ハミルトングラフ。これは呼ばれますDirac's Theorem。

$ G $が$ n $の頂点を持つ単純なグラフである場合、$ n \ geq 2 $は、隣接しない頂点xとyの各ペアに対して$ deg（x）+ deg（y）\ geq n $の場合、グラフ$ G $はハミルトングラフです。これは呼ばれますOre's theorem。