完全图

定义

完全图指这样一类简单无向图：任意两个不同的顶点之间都存在且只存在一条边，顶点自身不带自环，任意一对顶点之间也不重复连边^[1]。按照这一定义，n 个顶点的完全图记作 $K_n$，它是 (n−1)-正则图，即每个顶点的度都相同^[2]。

若给完全图的每一条边都确定一个方向，得到的有向图称为完全有向图；若任意两点之间恰好只有一条单向边，这样的图称为竞赛图^[1]。无向情形下边的数目上限为 $n(n-1)/2$，有向情形下上限为 $n(n-1)$，达到上限的图分别称为无向完全图与有向完全图^[3]。

完全图与补图互为对照：与 $K_n$ 互补的图不含任何边，称为空图或零图；反过来，任何简单图都可以通过补上缺失的边扩充为同阶完全图。完全图中的每个顶点集合本身都构成团，因此完全图是团概念的极端情形^[2]。

原理

完全图的边数可由计数得到：n 个顶点两两配对，共有 $\binom{n}{2}=\frac{n(n-1)}{2}$ 对，每一对恰好对应一条边，这个数也是三角数序列中的一项^[1]。因为任意两点之间都有边，去掉任何一个顶点后其余部分仍然连成一片，图只有在删去全部顶点时才会断开^[2]。

完全图具有高度对称性：它的自同构群是 n 个顶点的对称群，阶为 $n!$，任意顶点之间、任意边之间都可以通过同构互换^[1]。其色数等于 n，因为两两相邻的顶点必须使用互不相同的颜色^[1]。

在计数方面，完全图的匹配数随阶数排成 1, 1, 2, 4, 10, 26, 76, 232 …… 这一序列，即通常所称的电话号码序列，这些数值同时给出了 n 阶图 Hosoya 指数的最大可能值^[1]。下图以 $K_5$ 为例示意完全图的边配置。

graph LR

A --- B

A --- C

A --- D

A --- E

B --- C

B --- D

B --- E

C --- D

C --- E

D --- E

发展历程

图论作为数学分支形成于 18 世纪，通常以欧拉1736 年对哥尼斯堡七桥问题的研究为起点，图论的基本概念正是在这一工作的过程中逐步建立起来^[3]。相比之下，完全图的图形出现得更早：把顶点摆在正多边形顶点上、两两相连的画法在 13 世纪已经见于拉蒙·柳利的著作，这类图形有时被称为神秘玫瑰^[1]。

符号 $K_n$ 中字母 K 的来源并无定论：一种说法认为它取自德语 komplett，但完全图的德文名称并不含 K；另一种说法认为它取自数学家库拉托夫斯基的名字缩写^[2]。20 世纪以来，围绕完全图的交叉数、嵌入与分解问题形成了系统的研究，$K_n$ 成为检验平面图判定定理的标准反例^[1]。

应用

在平面图理论中，完全图充当判定基准。库拉托夫斯基定理指出，一个图是平面图当且仅当它不包含 $K_5$ 或 $K_{3,3}$ 的细分；瓦格纳定理则用收缩子图给出等价刻画^[1]。据此可以知道，$K_1$ 到 $K_4$ 都能画在平面上而不产生交叉，而 5 个及以上顶点的完全图在平面画法中必然出现边的交叉^[2]。

在组合设计与赛事建模中，完全图用来描述两两之间都存在对抗或配对关系的情形：把每条边定向后得到的竞赛图可以表示单循环赛的胜负结构，相关研究涉及哈密顿路径与边的分解^[1]。完全图的匹配计数则与配对方案、化学分子结构指标的极值估计有关^[2]。

在几何与拓扑中，$K_3$、$K_4$、$K_7$ 分别对应三角形、四面体等结构的骨架，具有环面拓扑的 Császár 多面体以 $K_7$ 为骨架，4 维及以上维度的多面体骨架也包含完全图^[1]。此外，$K_6$ 在三维空间中的任何嵌入都含有两两相扣的三角形环，这是空间图论中的经典结论^[1]。

局限

完全图的适用范围受规模限制。边数随顶点数按平方增长，n 稍大时边集就非常庞大，用邻接矩阵存储需要 $n^2$ 个单元，稠密图上的算法也只能在同一量级上运行，因此实际计算中很少构造大规模完全图。

完全图在平面上无法无交叉地绘制，5 个顶点起就需要交叉，交叉数的最小值只能逐阶研究，$K_{28}$ 的交叉数至今仍只确定到 7233 或 7234 两种可能^[1]。符号来源、德文命名等细节在文献中说法不一，也说明完全图的部分术语沿革缺少统一记载^[2]。

参见

• 补图 —— 由同阶完全图删去原图边集得到的图，与完全图互补。

• 团 —— 两两相邻的顶点子集，其导出子图即完全图。

• 竞赛图 —— 完全图边集全部定向后得到的有向图。

• 完全二分图 —— 顶点分两部分、只有跨部连边的另一类极值图。

• 平面图 —— 完全图 $K_5$ 是判断图能否平面绘制的关键反例。