完全グラフ
概要
完全グラフ（complete graph）とは、相異なる任意の二頂点が辺で結ばれている単純無向グラフであり、$n$ 頂点の場合 $K_n$ と書く。辺数は $\binom n2$、各頂点の次数は $n-1$ で、同じ頂点数をもつ単純グラフの中で辺数が最大である。相異なる頂点間の距離は1、彩色数とクリーク数は $n$、自己同型群は対称群 $S_n$ となる。誘導部分グラフも完全グラフであり、補グラフは空グラフである。また $K_n$ が平面グラフであることと $n\leq4$ は同値で、$K_5$ の非平面性は平面単純グラフの辺数評価から従う。
前提知識: グラフ, 頂点, 辺, 部分グラフ, グラフの同型
定義と直感
$V$ を集合とする。相異なる任意の $2$ 頂点が辺で結ばれている単純無向グラフ
$$
K_V=(V,[V]^2)
$$
を $V$ 上の完全グラフ（complete graph）という。ここで $[V]^2$ は $V$ の $2$ 元部分集合全体である。空でない有限頂点集合について $|V|=n$（$n$ は正整数）のとき、同型を除いて完全グラフは一つだけなので $K_n$ と書く。
完全グラフは、与えられた頂点集合上で入れられる辺をすべて入れたグラフである。したがって「どの二者も直接つながっている」関係を表す。たとえば全員が互いに知り合いである集団、全計算機間に専用回線がある通信網は完全グラフでモデル化される。図の形は定義に含まれず、頂点間の接続だけが重要である。
$K_1$ は孤立頂点一つ、$K_2$ は辺一本、$K_3$ は三角形である。$K_4$ は正四面体の頂点と辺の接続を表すグラフであり、平面上では三角形の内部に第4頂点を置いて三つの頂点すべてと結べば、辺の交差なしに描ける。
空グラフ $E_n$ は $n$ 頂点をもち、辺を一つももたない。$n\geq2$ では $K_n$ と $E_n$ は正反対の例であり、互いに補グラフである。$K_1=E_1$ だけは両方の条件を満たす。
基本的な量
$K_n$ の辺数は
$$
|E(K_n)|=\binom n2=\frac{n(n-1)}2
$$
であり、各頂点の次数は $n-1$ である。特に $K_n$ は $(n-1)$-正則グラフである。
辺は相異なる二頂点の順序をもたない組に一対一に対応するので、その個数は $n$ 元集合の $2$ 元部分集合の個数 $\binom n2$ である。頂点 $v$ を一つ固定すると、$v$ は残りの $n-1$ 頂点のすべてと隣接するから、$\deg(v)=n-1$ である。$v$ は任意なので全頂点の次数が等しい。
$G=(V,E)$ を $n$ 頂点の単純無向グラフとする。このとき
$$
|E|\leq\binom n2
$$
であり、等号が成り立つことと $G\cong K_n$ であることは同値である。
単純無向グラフの各辺は $V$ の $2$ 元部分集合なので $E\subseteq[V]^2$ である。よって $|E|\leq|[V]^2|=\binom n2$ となる。有限集合の包含 $E\subseteq[V]^2$ のもとで個数が等しいことは $E=[V]^2$ と同値であり、これは $G$ が $V$ 上の完全グラフであることにほかならない。
$$
\overline{K_n}=E_n,\qquad \overline{E_n}=K_n
$$
である。
補グラフは、相異なる二頂点について元のグラフにない辺だけをもつ。$K_n$ には可能な辺がすべてあり、$E_n$ には一つもないので、二つの等式が従う。
距離・彩色・対称性
$n\geq2$ とする。$K_n$ は連結で、相異なる任意の頂点 $u,v$ の距離(グラフ)は $d(u,v)=1$ である。したがって半径と直径はいずれも $1$ で、すべての頂点が中心頂点である。$K_1$ の半径と直径は $0$ である。
相異なる $u,v$ は定義により辺 $\{u,v\}$ で結ばれる。この辺は長さ $1$ の道であり、相異なる頂点を結ぶ長さ $0$ の道はないので $d(u,v)=1$ である。特に任意の二頂点が道で結ばれるから $K_n$ は連結であり、各頂点の偏心度は $1$ である。半径・直径・中心に関する主張は定義から従う。$K_1$ では唯一の頂点から自分自身への距離が $0$ である。
$K_n$ では相異なる任意の二頂点が隣接するので、正しい頂点彩色では異なる頂点に異なる色を割り当てなければならない。したがって少なくとも $n$ 色が必要であり、各頂点に別々の色を与えれば $n$ 色で彩色できる。よって彩色数は $n$ である。また頂点全体が大きさ $n$ のクリークであり、これより大きい頂点集合は存在しないからクリーク数も $n$ である。
$K_n$ のグラフ自己同型群は対称群 $S_n$ と同型である。
頂点集合の任意の置換は、相異なる二頂点を再び相異なる二頂点へ写す。$K_n$ では相異なる二頂点の組がすべて辺なので、任意の置換が辺を保ち、グラフ自己同型になる。逆にグラフ自己同型は定義上頂点集合の置換である。したがって自己同型全体は頂点集合の置換全体に一致し、$S_n$ と同型である。
この大きな自己同型群は、完全グラフのどの頂点にも構造上の違いがないことを表している。実際、任意の頂点を任意の頂点へ移す自己同型が存在するので $K_n$ は頂点推移的であり、任意の辺を任意の辺へ移せるので辺推移的でもある。
部分グラフと平面性
$W\subseteq V(K_n)$ とする。$W$ が誘導する部分グラフは $K_{|W|}$ と同型である。特に完全グラフの任意の誘導部分グラフは完全グラフである。
誘導部分グラフは、$W$ の二頂点を結ぶ元の辺をすべて残す。$K_n$ では $W$ の相異なる二頂点も必ず隣接するので、その辺集合は $[W]^2$ である。したがって得られるグラフは $W$ 上の完全グラフである。
有限完全グラフ $K_n$ が平面グラフであることと $n\leq4$ は同値である。
$K_1,K_2,K_3$ は明らかに平面に描ける。$K_4$ は三角形の内部に第4頂点を置き、外側の三頂点および内部の頂点を必要な三本の辺で結べば交差なしに描ける。
$n\geq5$ とする。平面グラフから頂点や辺を削除して得る部分グラフは、同じ平面描画から該当する点や曲線を除けば交差なしに描けるので、平面性を保つ。したがって $K_n$ は $K_5$ を部分グラフにもつため、$K_5$ が非平面であることを示せばよい。一般に、頂点数 $v\geq3$、辺数 $e$、面数 $f$ の連結な単純平面グラフを考える。各面の境界は少なくとも $3$ 本の辺をもち、各辺は両側の面から高々2回数えられるので $3f\leq2e$ である。Eulerの公式(平面グラフ) $v-e+f=2$ と合わせると
$$
2=v-e+f\leq v-e+\frac{2e}{3}=v-\frac e3,
$$
したがって $e\leq3v-6$ を得る。ところが $K_5$ では $v=5$、$e=\binom52=10$ であり、$10>3\cdot5-6=9$ である。よって $K_5$ は平面グラフでなく、それを部分グラフにもつ $K_n$ も平面グラフではない。
$K_4$ の平面描画と $K_5$ の非平面性は、完全グラフの平面性が $n=4$ と $n=5$ の間で切り替わることを示している。非平面性は図の描き方が下手だから起こるのではなく、どのように描いても辺の交差を避けられないという組合せ的性質である。
例と反例
同じ $n$ 頂点をもつ単純無向グラフのうち、$K_n$ は辺数が最大である。ランダムグラフ $G(n,p)$ では、可能な各辺を確率 $p$ で独立に選ぶため、$p=1$ の場合がちょうど $K_n$ である。
$n\geq4$ の閉路グラフ $C_n$ は各頂点の次数が $2$ なので正則であるが、$K_n$ では各頂点の次数が $n-1\geq3$ である。したがって「正則グラフなら完全グラフである」は成り立たない。満たす性質は全頂点の次数が等しいこと、満たさない性質は任意の二頂点が隣接することである。
完全二部グラフ $K_{m,n}$ は、異なる二部に属する頂点どうしをすべて結ぶが、同じ部に属する頂点どうしは結ばない。$m,n\geq1$ かつ $m+n\geq3$ なら完全グラフ $K_{m+n}$ ではない。「完全」という語は、完全グラフでは全頂点対、完全二部グラフでは異なる部の頂点対に対して用いられている。
他の概念との接続
完全グラフは、クリーク、彩色、Ramsey理論、平面グラフなどの基準例である。グラフ $G$ のクリークは、$G$ の中で完全グラフを誘導する頂点集合である。したがって完全グラフを探す問題は、複雑なネットワークの中から互いにすべて接続された部分集団を探す問題になる。
辺を削除して性質がどう変わるかを調べる際にも $K_n$ は出発点になる。たとえば $K_n$ から辺を一本削除すると辺数の最大性は失われるが、$n\geq3$ ならなお連結である。一方、補グラフを取ると最も密な $K_n$ と最も疎な $E_n$ が入れ替わる。標準的な定義と基本性質は Die17 §1.1、平面性は同書第4章を参照した。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
