グラフ理論-例
この章では、前の章ですでに説明した概念を示すために、いくつかの標準的な例を取り上げます。
例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 Kn?
解決
完全グラフでは、各頂点は残りの（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
行カバー数=（α 1）≥[N / 2] = 3
α 1 ≥3
3つのエッジを使用することで、すべての頂点をカバーできます。
したがって、番号をカバーする行は3です。