Discrete-mathematics-graph-and-graph-models
グラフとグラフモデル
前のパートでは、推論、証明、問題解決のためのさまざまなツールを紹介しました。 このパートでは、現実の多くの問題を定式化する基礎を形成する離散構造を研究します。
カバーする2つの離散構造は、グラフとツリーです。 グラフは、ノードまたは頂点と呼ばれる一連のポイントであり、エッジと呼ばれる一連の線で相互接続されます。 グラフ、または*グラフ理論*の研究は、数学、工学、およびコンピューターサイエンスの分野における多くの分野の重要な部分です。
グラフとは何ですか？
定義-グラフ（$ G =（V、E）$と表示）は、空でない頂点またはノードVのセットとエッジEのセットで構成されます。
例-グラフは$ 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 $
頂点の程度-グラフGの頂点Vの次数（deg（V）で示される）は、頂点Vに入射するエッジの数です。
| Vertex | Degree | Even/Odd |
|---|---|---|
| a | 2 | even |
| b | 2 | even |
| c | 3 | odd |
| d | 1 | odd |
偶数および奇数の頂点-頂点の次数が偶数の場合、その頂点は偶数頂点と呼ばれ、頂点の次数が奇数の場合、その頂点は奇数頂点と呼ばれます。
グラフの次数-グラフの次数は、そのグラフの最大頂点次数です。 上記のグラフでは、グラフの次数は3です。
ハンドシェイク補題-グラフでは、すべての頂点のすべての次数の合計は、エッジの数の2倍に等しくなります。
グラフの種類
さまざまなタイプのグラフがありますが、それらについては次のセクションで学習します。
ヌルグラフ
ヌルグラフにはエッジがありません。 $ n $頂点のヌルグラフは、$ N_n $で示されます。
シンプルなグラフ
グラフが無向であり、ループまたは複数のエッジが含まれていない場合、グラフは単純グラフ/厳密グラフと呼ばれます。
マルチグラフ
グラフ内で同じ頂点セット間の複数のエッジが許可されている場合、それはマルチグラフと呼ばれます。 つまり、少なくとも1つのループまたは複数のエッジを持つグラフです。
有向グラフと無向グラフ
グラフ$ G =（V、E）$は、エッジセットが順序付けられた頂点ペアで構成されている場合は有向グラフと呼ばれ、エッジセットが順序付けられていない頂点ペアで構成されている場合は無向と呼ばれます。
接続グラフと切断グラフ
グラフの2つの頂点がパスで接続されている場合、グラフは接続されます。グラフの少なくとも2つの頂点がパスで接続されていない場合、グラフは切断されます。 グラフGが切断されている場合、$ G $のすべての最大接続サブグラフは、グラフ$ G $の接続コンポーネントと呼ばれます。
Connected graph Unconnected graph
正則グラフ
グラフのすべての頂点が同じ次数を持つ場合、グラフは規則的です。 次数$ r $の通常のグラフGでは、$ G $の各頂点の次数はrです。
完全なグラフ
2つの頂点のペアがすべて1つのエッジで結合されている場合、グラフは完全グラフと呼ばれます。 n個の頂点を持つ完全なグラフは、$ K_n $で示されます。
サイクルグラフ
グラフが単一のサイクルで構成される場合、サイクルグラフと呼ばれます。 n個の頂点を持つサイクルグラフは、$ C_n $で示されます。
二部グラフ
グラフGの頂点セットが、グラフの各エッジが$ V_1 $の頂点を$ V_2 $の頂点に結合するように、2つの互いに素なセット$ V_1 $と$ V_2 $に分割できる場合、また、Gには、$ V_1 $の2つの頂点または$ V_2 $の2つの頂点を接続するエッジがないため、グラフ$ G $は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 $の値、それ以外の場合、値はゼロになります。
無向グラフの隣接行列
私たちは次の無向グラフを考慮し、隣接行列を構築しましょう-
上記の無向グラフの隣接行列は-
| a | b | c | d | |
| a | 0 | 1 | 1 | 0 |
| b | 1 | 0 | 1 | 0 |
| c | 1 | 1 | 0 | 1 |
| d | 0 | 0 | 1 | 0 |
有向グラフの隣接行列
私たちは次の有向グラフを考慮し、その隣接行列を構築しましょう-
上記の有向グラフの隣接行列は-
| 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番目の頂点に隣接する頂点のリンクリストを表します。 無向グラフの隣接リストは、次の図に示すとおりです-
平面対 非平面グラフ
平面グラフ-グラフ$ G $は、エッジが交差することなく平面に描画できる場合、平面グラフと呼ばれます。 エッジを交差させずにグラフを平面に描画する場合、グラフを平面に埋め込むと呼ばれます。
非平面グラフ-グラフのエッジが交差せずに平面に描画できない場合、グラフは非平面です。
同型
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 $の隣接する頂点にマッピングします。
準同型の性質
- 準同型写像は、全単射マッピングであれば同型写像です。
- 準同型は常にグラフのエッジと接続性を保持します。
- 準同型の構成も準同型です。
- 別のグラフの準同型グラフが存在するかどうかを調べることは、NPcomplete問題です。
オイラーグラフ
グラフ$ G $のすべてのエッジを含む閉じた軌跡がある場合、接続グラフ$ G $はオイラーグラフと呼ばれます。 オイラーパスは、グラフのすべてのエッジを1回だけ使用するパスです。 オイラーパスは、異なる頂点で開始および終了します。
オイラー回路は、グラフのすべてのエッジを1回だけ使用する回路です。 オイラー回路は常に同じ頂点で開始および終了します。 接続グラフ$ 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の定理*と呼ばれます。
$ G $が$ n $頂点を持つ単純なグラフである場合、$ n \ geq 2 $ if $ deg（x）+ deg（y）\ geq n $各非隣接頂点xおよびyのペアに対して、 graph $ G $はハミルトニアングラフです。 これは、*鉱石の定理*と呼ばれます。
