无向完全图

定义

无向完全图是一种无向图，它的任意两个不同顶点之间都恰好有一条边相连，边没有方向，图中不含顶点到自身的自环，也不允许两点之间存在重边。^[1][2] 换言之，在这类图里只要两个顶点互不相同，它们就一定是相邻的。^[1]

含有 n 个顶点的无向完全图通常记作 $K_n$，下标 n 表示顶点个数。^[2] 它也可以从边数来刻画：n 个顶点的简单无向图边数不超过 n(n-1)/2，恰好取到这个上界的图就是无向完全图；与之对应的有向完全图边数为 n(n-1)。^[1][3]

以 4 个顶点的情形为例，它的顶点两两相连，边数为 4×3/2=6 条。^[6][1]

原理

设图中顶点数为 n。每个顶点都与其余 n-1 个顶点相连，按顶点逐个统计会得到 n(n-1) 个“边的端点”，而每条边在它的两个端点处各被计了一次，所以边数为 $E=\frac{n(n-1)}{2}$。^[7][6] 这一结果也相当于从 n 个顶点中任取 2 个的组合数，因为每条边由唯一的一对顶点确定。^[7]

在无向完全图中，每个顶点的度都等于 n-1，因此它是 n-1 阶正则图。^[8] 它的补图不含任何边；若给它的每条边都指定一个方向，所得的有向图称为竞赛图。

例如 5 个顶点的无向完全图 K_5 共有 10 条边，其中每个点都与其他 4 个点直接相连。^[7]

graph LR

A((1)) --- B((2))

A --- C((3))

A --- D((4))

A --- E((5))

B --- C

B --- D

B --- E

C --- D

C --- E

D --- E

发展历程

图论通常被认为始于 1736 年欧拉对哥尼斯堡七桥问题的解决。^[9][10] 不过在 13 世纪，把顶点摆在正多边形各顶点上绘制完全图的做法已经出现，这类图形有时被称为神秘玫瑰。^[10][9]

记号 K_n 的来历并无定论：有资料称字母 K 取自德语 komplett，但德语中完全图写作 vollständiger Graph，其中并不含 K；也有资料认为该记号是为纪念卡齐米日·库拉托夫斯基对图论的贡献。^[8]

1930 年，波兰数学家卡齐米日·库拉托夫斯基提出了平面图的禁用子图判别准则，即库拉托夫斯基定理，无向完全图由此成为平面性理论中的关键对象。^[11]

应用

无向完全图用于表达“两两都相连”的全连接关系，例如通信网络的拓扑结构，或社交关系建模中每个人都与其余所有人相识的情形。^[4][6] 在网络分析、算法设计与密码学等领域，它也被当作基本模型使用。^[6]

在拉姆齐理论中，完全图提供了讨论的框架：把 K_n 的每条边任意染上 m 种颜色之一，拉姆齐数 R(p;m) 定义为最小的 n，使得每一种这样的染色都一定含有单色的 K_p 子图。^[5]

在极值图论里，完全图是衡量连接程度的参照物：无向完全图的边数是同阶图的边数上限，而图兰定理刻画的是不含完全子图 K_r 的图最多能有多少条边。^[7]

局限

无向完全图的边数按顶点数的平方增长，规模稍大就难以实际部署。若把 100 个节点两两直连，所需链路数为 4950 条。^[7]

平面性是一道硬限制。K_1 至 K_4 都能画在平面上而边不交叉，但顶点数达到 5 的完全图无论怎样绘制，都至少会有一对边相交。^[10] 根据库拉托夫斯基定理，一个图是平面图当且仅当它不包含 K_5 或完全二分图 K_3,3 的细分作为子图。^[11]

把完全图放进三维空间也无法消除全部限制：康威与戈登证明，K_6 在三维空间中的任何嵌入都包含至少一对相扣的三角形。^[10] 与平面性密切相关的交叉数问题同样不易处理，只有一部分完全图的交叉数被确定。^[10]

参见

• 完全图 —— 无向完全图是它的无向情形，另有边都带方向的有向完全图

• 有向完全图 —— 与无向完全图对应的定向版本，边数为 n(n-1)

• 平面图 —— 顶点数达到 5 的无向完全图不再是平面图

• 竞赛图 —— 给完全图的每条边指定方向后得到的有向图

• 拉姆齐理论 —— 以完全图的边着色为基本框架的研究方向

• 正则图 —— 无向完全图是每个顶点度都为 n-1 的正则图