この記事ではグラフ理論の完全グラフ（Complete Graph）について解説します。
完全グラフ（Complete Graph）とは
完全グラフ（Complete Graph）とは、グラフ理論における特別なグラフの一種で、次のように定義されます：
💡
定義：
完全グラフとは、グラフのすべての頂点が互いにエッジ（辺）で直接接続されているグラフです。
簡単に言えば、「頂点同士が1つも漏れなくつながっているグラフ」です。
完全グラフの記法
完全グラフは通常、Kₙ（Kの後に頂点数nを添えた表記）で表されます。
- K₁: 頂点が1つのグラフ（孤立点）。
- K₂: 頂点が2つあり、1本のエッジで結ばれたグラフ（線分に相当）。
- K₃: 3つの頂点が三角形状につながったグラフ。
- K₄: 4つの頂点がすべて接続されたグラフ。
完全グラフの特徴
- 辺の数辺の数=2n(n−1)
完全グラフKₙのエッジの総数は、次の式で計算されます：
ここで、nは頂点数です。
例：
- K₃の辺の数
- K5 の辺の数
- K₃の辺の数
- 最大の隣接数
各頂点は他のすべての頂点と接続されているため、隣接する頂点の数（次数）は常に n−1n-1n−1 です。
- 対称性
完全グラフは非常に対称的で、どの頂点から見ても同じ構造をしています。
完全グラフの例と応用
- 小さな完全グラフの例
-
- K₃: 三角形のようなグラフ。簡単なグラフ構造を説明するのに便利です。
- K₄: 立方体の頂点を一面として見ることができる構造。
- 実世界での応用例
- 通信ネットワーク: すべてのノードが直接接続されている理想的な完全ネットワーク。
- 組み合わせ数学: 組み合わせ問題をグラフ理論で解くときに、完全グラフが登場することが多い。
- トラベリングセールスマン問題: 頂点が都市、辺が都市間の道を表すグラフとして完全グラフが使われる。
完全グラフと平面性の関係
完全グラフは頂点数が増えると非常に密な構造になるため、平面的グラフではなくなることがあります。具体的には：
- K₅（5頂点以上）は平面上に描画できない（交差するエッジが必ず出てくる）。
- これが「平面グラフ」や「平面的グラフ」の議論で重要な役割を果たします。
まとめ
完全グラフは「全ての頂点が直接接続されたグラフ」であり、そのシンプルかつ密な構造が多くの数学的応用やアルゴリズムに役立ちます。特に頂点数やエッジ数の計算が容易で、グラフ理論を学ぶ際の基本概念として重要な位置を占めています。
