图着色计算器

图着色计算器

图着色计算器用于计算任何无向图的色数 χ(G) 并生成有效的顶点着色方案。以边列表或邻接表形式输入您的图，该工具将返回使得相邻顶点不同色所需的最少颜色数，并提供交互式 SVG 可视化、动画化的 DSATUR 轨迹以及各顶点颜色的详细细分。

什么是图着色？

图 G = (V, E) 的顶点着色是为每个顶点分配一种颜色，使得每条边的两个端点颜色不同。色数记作 χ(G)，是存在此类着色方案所需的最少颜色数。计算 χ(G) 在一般情况下属于 NP-hard 问题，但它拥有优美的数学理论和许多实际应用：考试排期、无线电频率分配、编译器中的寄存器分配，以及著名的平面图四色定理。

关键定理和界限

• 平凡界限： 对于任何图，1 ≤ χ(G) ≤ |V|。
• 团数下界： χ(G) ≥ ω(G)，其中 ω(G) 是最大团的大小。
• 二分图特征： 当且仅当 G 不含奇环时，χ(G) ≤ 2 (König 定理)。
• Brooks 定理： 除非 G 是完全图或奇环，否则 χ(G) ≤ Δ(G)；对于完全图或奇环，χ(G) = Δ(G) + 1。这里 Δ(G) 为最大度。
• 四色定理： 每个平面图都是 4-可着色的。
• 贪心上界： 任何贪心算法最多使用 Δ(G) + 1 种颜色。

本计算器使用的算法

DSATUR (饱和度算法)

DSATUR 由 Daniel Brélaz 于 1979 年提出，是图着色中最强大的实用启发式算法之一。它重复选择未着色顶点中其邻居已使用不同颜色种类最多（即饱和度最高）的顶点，通过顶点度数打破平局，并为其分配邻居未使用的最小颜色编号。DSATUR 在二分图和许多结构化图族上被证明是最优的，并且可以在毫秒内为拥有数百个顶点的图生成高质量的着色方案。

Welsh-Powell

Welsh-Powell 算法按度数降序对顶点进行排序，然后进行贪心着色。它的运行时间为 O(|V|²)，并保证最多使用 Δ(G) + 1 种颜色。它的速度极快，通常是一个很好的初步近似，尽管在具有多变局部结构的图上可能会输给 DSATUR。

贪心算法 (输入顺序)

最简单的算法：按输入顺序遍历顶点，并为每个顶点分配已着色邻居未使用的最小颜色。输出结果对输入顺序很敏感，但随机排序可以作为一个基准，用于与更智能的启发式算法进行对比。

精确回溯

对于小图（最多约 18 个顶点），计算器可以通过尝试 k = 2, 3, 4, ... 并使用深度优先回溯尝试进行 k-着色，从而找到真实的色数。搜索按度数降序排列顶点，并在没有可用颜色时进行剪枝。当精确算法成功时，结果将标注为“精确”。

输入格式

边列表

将每条边写为两个顶点标签，中间用连字符、空格或箭头分隔。使用逗号或换行符分隔不同的边。顶点标签可以是字母、数字或下划线。示例：

邻接表

写下每个顶点，后跟冒号和以逗号分隔的邻居列表。示例：

自环将被拒绝，因为顶点不能被赋予与其自身不同的颜色。重复的边会被静默去重，图形将被视为无向图。

如何使用此计算器

1. 选择格式： 使用单选按钮在边列表和邻接表之间切换。
2. 输入图： 粘贴您的数据或点击快速示例（如三角形、完全图 K₅、彼得森图风格的轮图、二分图 K₃,₃、考试排期）。
3. 选择算法： 保留“自动”以使用最佳默认设置，或强制选择 Welsh-Powell、贪心、DSATUR 或精确回溯。
4. 点击“开始着色”： 下方将显示色数、颜色明细列表、带有可拖拽节点的交互式 SVG 以及动画化的逐步轨迹。
5. 探索： 按下播放键观看算法逐步为顶点着色，拖动节点以调整布局，或使用“上一步/下一步”手动查看过程。

图着色的实际应用

考试排期

将每场考试作为一个顶点，在至少共享一名学生的考试之间连一条边。使用 k 种颜色的有效着色方案可以提供一个具有 k 个时间段的排期，确保没有学生发生冲突。色数即为所需的最少时间段数量。

无线电频率分配

在彼此干扰范围内的发射器必须在不同的频率上广播。干扰图的色数即为所需的最少频率数量。

寄存器分配

在编译器中，变量的活跃范围是顶点；如果两个活跃范围在时间上重叠，则它们之间存在一条边。k-着色方案将变量分配给 k 个 CPU 寄存器而不会发生冲突。

地图着色

共享边界的国家必须被赋予不同的颜色。四色定理（Appel-Haken, 1976）证明了对于任何平面地图，四种颜色始终足够。

数独和约束谜题

完成的数独是一个包含 81 个单元格作为顶点，并在同一行、列或 3×3 方块内的单元格之间连边的图的 9-着色方案。图着色是许多约束满足类谜题的数学核心。

有趣的特殊情况

• 完全图 K_n: χ(K_n) = n。每对顶点都相邻，因此所有颜色必须互不相同。
• 圈 C_n: 如果 n 为偶数，χ(C_n) = 2；如果 n 为奇环，χ(C_n) = 3。
• 树： 任何拥有 ≥ 2 个顶点的树都有 χ = 2（树是二分图）。
• 二分图： 如果图至少有一条边，则 χ = 2。
• 彼得森图： 一个著名的 3-正则图，χ = 3。
• 轮图 W_n: 一个中心顶点连接到一个 n-圈。如果 n 为偶数，χ = 3；如果 n 为奇数，χ = 4。

常见问题解答

什么是图的色数？

色数 χ(G) 是为图的顶点着色所需的最少颜色数量，使得任何两个相邻顶点都不共享同一种颜色。二分图的色数最多为 2；任何包含三角形的图色数至少为 3；根据 Brooks 定理，除了完全图和奇环外，色数永远不会超过最大度数。

此计算器使用什么算法？

对于小图，计算器运行精确回溯搜索以查找真实的色数。对于较大的图，它使用 DSATUR 启发式算法，该算法重复地为未着色顶点中已着色邻居最多的顶点着色。您也可以在算法下拉菜单中强制选择 Welsh-Powell 或纯贪心算法。

我应该如何输入我的图？

使用边列表模式每行键入一条边，如 A-B，或用逗号分隔，如 A-B, B-C, C-A。使用邻接表模式编写每个顶点，后跟冒号及其邻居，如 A: B, C。自环将被拒绝，因为顶点不能被着色为与其自身不同的颜色。

为什么 DSATUR 并不总能找到真实的色数？

图着色是 NP-hard 问题，因此目前还没有已知的快速算法总能找到最少颜色数。DSATUR 是一种出色的实用启发式算法，通常与真实色数相符，但在某些对抗性图上，它可能会使用比必要更多的颜色。计算器会报告所用的颜色数量以及从最大团中找到的下界，以便您判断答案的紧凑程度。

图着色在现实世界中有哪些应用？

图着色模型可用于考试排期（每个考试是一个顶点，冲突是边，颜色是时间段）、无线电频率分配（顶点是发射器，边是干扰）、编译器中的寄存器分配、地图着色、数独求解以及在冲突约束下的任务分配。

色数总是等于最大团的大小吗？

不是。团数 ω(G) 始终是色数 χ(G) 的下界，对于完美图（如二分图、树、区间图和弦图），它们是相等的。对于一般图，χ(G) 可以严格大于 ω(G)；典型的例子是 Mycielski 图，它们不含三角形但需要任意多数量的颜色。

此计算器能处理的最大图形是多少？

计算器支持最多 60 个顶点和 600 条边。对于精确算法，顶点超过约 18 个的图可能会回退到 DSATUR，因为回溯会变得非常缓慢。对于实际用途，这涵盖了大多数课堂示例、考试排期问题和中小型应用。

延伸阅读

• 图着色 — 维基百科
• DSATUR 算法 — 维基百科
• 色多项式 — 维基百科
• 四色定理 — 维基百科
• Brooks 定理 — 维基百科