完全图

概述

完全图（Complete Graph）是一种每对不同的顶点之间都恰好有一条边相连的图，记为 $K_n$，其中 $n$ 为顶点数。

定义

形式化定义

完全图 $K_n$ 是一个含 $n$ 个顶点的简单无向图 $G=(V,E)$，满足： $E=\{\{u,v\}\mid u,v\in V,u\ne v\}$

即 $V$ 中任意两个不同顶点之间都有且仅有一条边相连。

类似地，完全有向图（tournament）中每对顶点之间有且仅有一条有向边。

基本性质

边数

$K_n$ 的边数为：

$|E|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$

这是从 $n$ 个元素中选取 2 个的组合数，直观理解：每对顶点贡献一条边。

色数

• $K_n$ 的色数 $\chi (K_n)=n$：每个顶点都需要不同颜色，因为任意两个顶点都相邻
• 这是色数上界 $\chi (G)\le \Delta (G)+1$（其中 $\Delta$ 为最大度）取等号的情况

度数

• $K_n$ 中每个顶点的度数为 $n-1$（与所有其他顶点相连）
• 由握手定理验证：$n\times (n-1)=2\times \frac{n(n-1)}{2}$，成立

连通性

• $K_n$ 是 $(n-1)$-连通的：删除任意 $n-2$ 个顶点后图仍然连通
• $K_n$ 的直径为 1（任意两顶点间距离恰好为 1）

特殊情况

图	顶点数	边数	说明
$K_1$	1	0	单个孤立顶点
$K_2$	2	1	一条边
$K_3$	3	3	三角形
$K_4$	4	6	四面体骨架
$K_5$	5	10	平面性的临界点（$K_5$ 不可平面）

核心性质

• 非平面性：当 $n\ge 5$ 时，$K_n$ 不是平面图（$K_5$ 和 $K_{3,3}$ 是 Kuratowski 定理的两个禁止子图）
• Hamilton 性：$K_n$ 总是 Hamilton 图（存在经过所有顶点恰好一次的环），共有 $\frac{(n-1)!}{2}$ 条不同的 Hamilton 回路
• 团（clique）：完全图是”团”概念的特例——图 $G$ 中任意 $k$ 个两两相邻的顶点构成一个 $k$-团，即 $G$ 中存在 $K_k$ 作为子图

应用场景

• 旅行商问题（TSP）：TSP 通常定义在完全图上——给定 $n$ 个城市及每对城市间的距离，求访问所有城市恰好一次并返回起点的最短回路。$K_n$ 上的 Hamilton 回路共有 $\frac{(n-1)!}{2}$ 条
• 团问题（Clique Problem）：判定图中是否存在大小为 $k$ 的团是 NP 完全问题，等价于判定补图中是否存在大小为 $k$ 的独立集
• Ramsey 理论：$R(s,t)$ 表示满足以下条件的最小 $n$：$K_n$ 的任意红蓝二染色中，要么存在红色 $K_s$，要么存在蓝色 $K_t$

参见

• 图论
• 二部图