完全图

完全图是指所有顶点都两两连接的图. 有 $n$ 个顶点的完全图记为 $K_{n}$ , 它有 $(2 n) = n (n - 1) /2$ 条边. 下图展示了几个完全图的例子.

1定义

定义 1.1 (完全图). 称有限图 $G = (V, E, d)$ 为完全图, 如果满足以下条件:

•	映射 $d : E \to ⟨ 2 V ⟩$ 是单射, 其像为 ${[(x, y)] \in ⟨ 2 V ⟩ ∣ ∣ x \neq = y} .$ 换言之, $G$ 的每一对顶点之间恰有一条边相连.

对自然数 $n$ , 将有 $n$ 个顶点的完全图记为 $K_{n}$ .

•	$K_{0}$ 是空图.

•	对 $n \geq 1$ , 完全图 $K_{n}$ 是 $(n - 1)$ 维单形的边构成的图. 例如, $K_{1}$ 只有一个顶点且没有边; $K_{2}$ 有两个顶点和一条边, 形成一条线段; $K_{3}$ 有三个顶点和三条边, 形成一个三角形; $K_{4}$ 有四个顶点和六条边, 形成一个四面体.

•	完全图 $K_{n}$ 有 $n$ 个顶点和 $n (n - 1) /2$ 条边.

•	当 $n \geq 1$ 时, $K_{n}$ 是连通图.

•	完全图 $K_{n}$ 是平面图当且仅当 $n \leq 4$ .

•	团
•	完全二部图

术语翻译

完全图 • 英文 complete graph