Bóna · 枚举与解析组合学导论 · 第 5 章 图的计数
5.4 着色顶点上的图Graphs on colored vertices
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标把“给图的顶点涂颜色，并且要求相邻的两个顶点颜色不同”这件事说清楚。在此基础上提出本节要研究的两类计数问题：（一）给定一张图与可用颜色数，合法的涂色方案有多少种？（二）给定一组已经涂好色的顶点，能在它们上画出多少张图，使得这种涂色恰好合法？
从一个外交谈判的例子说起
假设四个国家的代表聚在一起进行一系列谈判。这些谈判由一轮“一对一”的对话组成，每场对话都发生在来自不同国家的两个人之间。如果我们想用一张图（graph）来表示这些谈判，那么顶点（vertex）就对应于各位谈判者，并且当两个对应的人彼此交谈过时，就在这两个顶点之间连一条边（edge）。然而，这样得到的图会有一种特殊的结构：来自同一个国家的人所对应的顶点之间，不会有任何边。参见图 5.28 的示例。
这个例子表明：有时我们想研究这样的图——在某些顶点子集之间，我们不希望出现边。另一个这样的例子是通信塔（communication tower）以及它们广播所用的频率。我们可以用图的顶点表示通信塔，并在两座塔彼此距离小于某个指定距离 \(d\) 时，用一条边把对应的两个顶点连起来。彼此距离小于 \(d\) 的塔不应在同一频率上广播。因此，如果我们用颜色表示频率，那么把频率分配给各座塔，就等价于给图的顶点涂色，使得相邻顶点颜色不同。
使用“着色”的想法，是把这类要求可视化的一种简便方式，也就是说，它能帮我们记录住哪些顶点对是不能相邻的。在谈判者的例子里，我们会把对应于同一国家代表的顶点涂上同一种颜色（或者，把对应于建得彼此很近的通信塔的顶点涂上同一种颜色），然后我们就不用边去连接同色的顶点。
例（一个具体的小三角形） 取三座彼此都很近的塔，两两之间都有边，构成一个三角形。要给它们分配频率（颜色），且相邻两座必须不同频。
- 三座塔两两相邻，所以三种颜色必须两两不同。
- 若只有 \(2\) 种频率可用：第三座塔无论选哪种都会和某座邻塔撞色——无法合法分配。
- 若有 \(3\) 种频率可用：第一座有 \(3\) 种选择，第二座要避开第一座（剩 \(2\) 种），第三座要同时避开前两座（剩 \(1\) 种），共 \(3\times2\times1=6\) 种合法方案。
合法着色的定义
定义 5.35 设 \(G\) 是一张图。我们称 \(G\) 的顶点的一种着色（coloring）是合法的（proper，又译“正常的”），如果相邻的顶点具有不同的颜色。
读定义的要点“合法着色”只对有边相连的顶点提要求：相邻就必须异色。对于不相邻的两个顶点，颜色相同与否完全自由。注意：合法着色并不要求把所有可用颜色都用上，也不要求用最少的颜色——它只是一种“满足异色约束”的涂法。
本节要研究的两类问题
在本节中，我们将考察两类问题：
- 给定一张图 \(G\) 与颜色数 \(n\)，在只允许使用这 \(n\) 种颜色的前提下，\(G\) 有多少种合法着色？
- 给定一个已经着色的顶点集，在该顶点集上有多少张图，能使这一着色是合法的？
两类问题的区别第一类问题：图固定不变，变化的是“怎么涂色”，要数合法着色的方案数（这会引出按颜色数 \(n\) 写成的多项式，即图的色多项式 chromatic polynomial）。第二类问题：颜色（即顶点的分组）固定不变，变化的是“怎么连边”，要数使该着色合法的图的个数——也就是只在异色顶点对之间“可连可不连”的所有连边方式。
例（第二类问题的最小情形） 设有 \(3\) 个顶点，已被涂成：两个红、一个蓝。哪些图能让这种着色合法？
- 合法的唯一约束是“同色不连边”。两个红顶点是同色，一定不能有边相连——这条边被禁止。
- 剩下的顶点对：红-蓝、红-蓝 共 \(2\) 对，都是异色，每对都可连可不连。
- 每对各有“连”与“不连”两种选择，互相独立，故合法图共 \(2\times2=4\) 张。
返回 全书目录