图着色

关于这个计算器

图着色计算器求出色数 χ(G)——即为图的顶点着色使得没有任何边连接两个同色顶点所需的最少颜色数——并展示一种最优着色。输入顶点数和边的列表；它用分支定界搜索精确计算 χ，报告最大度 Δ 和最大团 ω（χ 的下界），标记出二部图和完全图，并绘制着色后的图。适用于调度、寄存器分配、地图着色以及色数研究。

如何为图着色

1. 输入顶点数；它们从 1 到 n 编号。
2. 将边列为像 1-2, 2-3 这样的顶点对——每个连接一对。
3. 读取色数 χ(G) 以及分配给每个顶点的颜色。
4. 将 χ 与最大团 ω 相比较，理解为何需要这么多颜色，或加载一个预设进行探索。

常见示例

• 三角形 (K₃) 需要 3 种颜色——它的每对顶点都相邻。
• 偶圈是二部图，只需 2 种颜色；像 C₅ 这样的奇圈需要 3 种。
• 完全图 Kₙ 恰好需要 n 种颜色。
• 大小为 ω 的最大团迫使至少需要 ω 种颜色，因此 χ(G) ≥ ω。
• Grötzsch 图需要 4 种颜色但不含任何三角形，因此 χ 可以超过团数。