Graph-theory-examples

グラフ理論-例

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

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