五色定理希伍德定理.pptVIP

对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。 图的点色数 example1 对任意的图G，有： 分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为Δ，因此，正常着色过程中，其邻点最多用去Δ种颜色，所以，至少还有一种色可供该点正常着色使用。 证明：我们对顶点数作归纳证明。 当n=1时，结论显然成立。 设对顶点数少于n的图来说，结论成立。考虑一般的n阶图G 任取v ∈V(G), 令G1=G-v， 由归纳假设： 设п是G1的一种Δ(G)+1正常点着色方案，因为v的邻点在п下至多用去Δ(G)种色，所以给v染上其邻点没有用过的色，就把п扩充成了G的Δ(G)+1着色方案。 因此对于G来说п也是其正常着色方案，即可以对其进行Δ(G)+1正常点着色。所以有结论 五色定理 (1890, Heaword) 希伍德定理 [五色定理] (1890, Heaword) 任何简单平面图都是5-可着色的。 [证明]设简单平面图G=(V, E)， 分别用c1~c5五种颜色对 n=|V| 作归纳。 n ? 5时，结论成立。 设 n = k(≥ 6)时，结论成立。 当 n = k +1时，由[P364,Corollary 2]简单平面图G至少有一个顶点的度小于等于5。设 v0?V，deg(v0)? 5。设G?=G?v0，由归纳假设，G?是5-可着色的。给G?固定一种5-着色方案,再将 v0 加回G?得到G，在此情况下讨论 v0 的着色。 (1) 若deg(v0) ? 4，则 v0 最多邻接4种颜色的顶点，给 v0 着以第5种颜色得到G 的一种5-着色方案。 (2) 否则deg(v0) = 5，设 v0 的邻接点按逆时针排列为v1, v2, v3, v4, v5, 如图所示。 ① 若v1~ v5 的着色数? 4，则 v0 最多邻接4种颜色的顶点，给 v0 着以第5种颜色得到G 的一种5-着色方案。 ② 否则 v1~ v5 分别被着以颜色 c1~c5 ，此时v0的着色就成了问题，考虑如下情况： V13=｛v|v着色c1或c3的顶点）｝ 、设G13是V13在G? 的导出子图,即G13 =G（ V13 ） v0 v2 v1 v5 v4 v3 v4 v0 v2 v1 v5 v3 c1 c2 c3 c4 c5 c3 c3 c1 c1 c3 v0 v2 v1 v5 v4 v3 c1 c2 c3 c4 c5 c3 c3 c1 c1 c3 (a) 若 v1 和 v3 在G13中不连通，将G13中 v1 所在连通分支所有顶点颜色对换，得到G?的另外一种5-着色方案。此时 v1 和v3 都着色 c3，即v1~ v5 的着色数= 4。由①得到G 的一种5-着色方案。 v5 v0 v2 v1 v4 v3 c1 c2 c3 c4 c5 c3 c3 c1 c1 c3 c1 (b) 若 v1 和 v3 在G13中有连通路径P13， V24=｛v|v着色c2或c4的顶点）｝ 、设G24是V24在G? 的导出子图,即G24 =G（ V24 ），在G? 中v2 和 v4 的通路P24一定不存在，否则不是平面图。对 v2 和 v4 作类似 (a) 的讨论，可以得到G 的一种5-着色方案。 v0 v2 v1 v5 v4 v3 c1 c2 c3 c4 c5 c3 c3 c1 c1 c3 c1 v0 v2 v1 v5 v4 v3 P13 P24 结论：综合上述讨论，n = k+1 时结论仍然成立。由归纳原理，定理得证。