1. 概述
在本教程中，我们将深入探讨完美图的定义及其定理，解析其数学意义与核心特征。接着我们会讨论完美图的实际应用场景，并介绍强完美图（Strongly Perfect）和弱完美图（Weakly Perfect）这两个用于分类完美图的概念。
2. 图论基础简介
图论是计算机科学与数学中研究图结构的基础理论。图是一种用于描述对象之间成对关系的数学结构，由节点（也称为顶点）和连接这些节点的边组成：
以上图示含义如下：
- 图 G = (V, E)
- 顶点集合 V = {A, B, C, D}
- 边集合 E = {AB, AC, BC, CD}
3. 什么是完美图？
一个图 G 是完美图，当且仅当它的每一个导出子图都满足：其团数（clique number）等于色数（chromatic number），即 ω(G) = χ(G)。反之，若不满足该条件，则称为非完美图（imperfect graph）。下面我们详细解释这两个关键概念。
3.1. 色数（Chromatic Number）
图 G 的色数是指对该图进行着色时，使得相邻节点颜色不同的前提下所需的最少颜色数。
图 G 的色数通常记作 χ(G)。
以下图示展示了几种图的最小着色方式及其对应的色数：
3.2. 团数（Clique Number）
团（clique）是指图中一个顶点集合，其中任意两个顶点之间都有边相连，即该子图是完全图。一个图 G 的团数 ω(G) 是其最大团所包含的顶点数。
换句话说：
- 团是图的一个完全子图
- 最大团指的是图中包含顶点最多的团
以下图示展示了图中团的分布以及图 G 的团数（红色数字）：
3.3. 完美图的定义
对于图 G = (V, E)，如果对于任意子集 S ⊆ V，其导出子图 G[S] 的团数 ω(G[S]) 与色数 χ(G[S]) 相等，则称图 G 为完美图。
换句话说，完美图的每一个导出子图都必须满足 ω = χ。
来看几个例子：
- 图 G1 中 ω(G) = 2，χ(G) = 2 ⇒ ω = χ，因此是完美图
- 图 G2 中 χ(G) = 4，ω(G) = 3 ⇒ ω ≠ χ，因此不是完美图
再来看一个具体例子：
这是一个包含 3 个顶点的环图 C3：
- 色数 χ(G) = 3
- 团数 ω(G) = 3
- A、B、C 三者构成最大团，且 ω(G) = χ(G)
因此，C3 是一个完美图 ✅
4. 强完美图（Strong Perfect Graph）
一个图是强完美图，当且仅当其每一个导出子图 H 都存在一个顶点集合，使得该集合与 H 的每一个极大团都有一个交点。
强完美图一定是完美图，但反过来不一定成立 ❗
下图展示了一个强完美图的例子：
5. 弱完美图（Weak Perfect Graph）
一个图 G 是弱完美图，当且仅当其团数 ω(G) 等于色数 χ(G)。注意，弱完美图不要求其所有导出子图都满足这个条件。
换句话说：
- 弱完美图只关心图本身是否满足 ω = χ
- 完美图则要求所有导出子图都满足 ω = χ
所以，完美图是弱完美图的子集。
下图展示了一个弱完美图的例子：
6. 总结
本文介绍了图论中一个重要而有趣的概念：完美图。我们从图论基础出发，解释了色数与团数的定义，并据此给出了完美图的正式定义。随后我们进一步介绍了强完美图与弱完美图的概念，帮助读者更全面地理解完美图的分类与特性。
完美图在组合优化、图着色、调度问题等领域有广泛应用，是理论与实践结合非常紧密的一个图论方向。掌握其基本概念，有助于在算法设计与图建模中避免“色数过高”等常见问题，是进阶图论学习的重要一步 ✅