自 2010 年 · 每月支持超过 200 万次工具运行
自 2010 年
添加到 Chrome

我的工具箱

自动模式

还没有收藏的工具。

升级为高级版
相关工具
图度数序列验证器邻接矩阵计算器最小生成树计算器镶嵌图案生成器迷宫生成器
主页 > 数学 > 进阶数学计算
 

图着色计算器

为任意无向图找出色数和有效的顶点着色方案。输入边或邻接表,得到所需最少颜色数、颜色分配方案、动态DSATUR算法演示和图形可视化。

免费使用无需注册即时出结果
图着色计算器立即免费试用 ▼

⚡ 尝试示例：

4-圈 C₄ 三角形 K₃ 完全图 K₅ 五边形 C₅ 轮图 W₆ 二分图 K₃,₃ 邻接表示例 考试排期
边格式：A-B 或 A B，使用逗号或换行符分隔。最多 60 个顶点和 600 条边。
自动模式会为小图选择精确回溯算法，为大图选择 DSATUR 算法。

Embed 图着色计算器 Widget

图着色计算器

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

什么是图着色？

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

色数定义
χ(G) = min { k : G 允许进行有效的 k-着色 }

关键定理和界限

本计算器使用的算法

DSATUR (饱和度算法)

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

Welsh-Powell

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

贪心算法 (输入顺序)

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

精确回溯

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

输入格式

边列表

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

A-B, B-C, C-D, D-A
A-C

邻接表

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

A: B, C, D
B: A, D
C: A
D: A, B

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

如何使用此计算器

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

图着色的实际应用

考试排期

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

无线电频率分配

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

寄存器分配

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

地图着色

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

数独和约束谜题

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

有趣的特殊情况

常见问题解答

什么是图的色数？

色数 χ(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，因为回溯会变得非常缓慢。对于实际用途，这涵盖了大多数课堂示例、考试排期问题和中小型应用。

延伸阅读

引用此内容、页面或工具为：

"图着色计算器" 于 https://MiniWebtool.com/zh-cn/图着色计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队。更新日期：2026年4月20日

开发者 API 可用: 用一次 JSON HTTP 请求，把这个工具接入你的应用、自动化流程或智能体。 查看 API 文档

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

进阶数学计算:

热门与最新工具:

平面图检查器📊 柱状图制作工具📈 折线图制作工具查看全部 →
主页 > 数学 > 进阶数学计算 > 图着色计算器