最后更新: 2025-01-21 18:16 查看: 135 次反馈刷题

四色定理

## 四色定理
在1852年，一个英国青年名叫盖思里(Francis Guthrie)提出：任何连通的平面图，可以用不多于4种颜色对每一个区域着色，使相邻区域着不同颜色。
1878～1880年两年间，数学家肯普和泰勒两人分别宣布证明了四色定理。后来，人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对平面图着色，用五种颜色就够了。
1976年美国伊利诺州立大学的两位教授，阿佩尔(Kenneth Appel)和海肯(Wolfgang Haken)宣布，用计算机证明了这个问题。他们的证明需要对1900多种情况进行详尽的分析，在一台高速计算机
上耗时超过1200小时。对数学家来说总还是希望能找到数学方法的证明。
 ![图片](/uploads/2025-01/3f255c.jpg)

## 平面图的着色
 ![图片](/uploads/2025-01/531717.jpg)
 
 平面图的对偶图（面着色 $\rightarrow$ 点着色）定义7－6．1 给定平面图 $G=<V$ ， $E >$ 有面 $F _1, F_2, \ldots, F_{ n }$ ，若图 $G ^*=< V ^*, E ^*>$ 满足下述条件，则称为图G的对偶图。
（1）对于图 $G$ 中任一面 $F_i$ ，图 $G^*$ 中有且仅有一结点 $v_i \in V^*$
（2）对于图 $G$ 的面 $F_i, F_j$ 的公共边界 $e_k$ ，图 $G^*$ 中有且仅有一条边 $e_k^* \in V^*$ ，使 $e_k{ }_k=\left(v_i^*, v_j^*\right)$ 且 $e_k^*$ 与 $e_k$ 相交
（3）当且仅当 $e_k$ 只是一个面 $F_i$ 的边界时，$v^*$ 存在一个环 $e_k^*$ 与 $e_k$ 相交定义7－6．2 若图G的对偶图G＊同构于G，则称G为自对偶图
 ![图片](/uploads/2025-01/5f289e.jpg)
 
 从画法知， G和G’有相同的边数。
连通的平面图G的对偶图也必是平面图。 在本例中, G和G’同构。
一般地，未必同构。

注意图中的一度顶点和自环是怎样处理的。
 一个连通的平面图G的对偶图也必是平面图。
 ![图片](/uploads/2025-01/9eada7.jpg)
 
 
 ## 平面图的对偶图(边着色 点着色)
  ![图片](/uploads/2025-01/5aeea8.jpg)
  
   
   对偶图着色相关定理
定理7－6．1 对于 $n$ 个结点的完全图 $K_n$ ，有 $x\left(K_n\right)=n$ 。
证明：因为完全图的每一个结点与其他各个结点都邻接，故 $n$ 个结点的着色数不能少于 $n$ ，又 $n$ 个结点的着色数至多为 $n$ ，故 $x\left(K_n\right)=n$ 。定理7－6．2 设G为一个至少有三个结点的连通平面图，则G中必有一个结点u， $\operatorname{deg}(u) \leq 5$ 。
证明：设 $G=<V, E>,|V| \geq 3$ ，若 $G$ 的每个结点 $u$ 都有 $\operatorname{deg}(u) \geq 6$ ，则因所有点的度数和为 $2|E|$ ，故 $2| E | \geq 6|V|$ ，所以 $| E | \geq 3|V|>3|V|-6$ ，与定理7－ 5．3矛盾。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：同胚与库拉图斯基(Kuratowski)定理

下一篇：平面图的五色定理

本文对您是否有用？有用 (0) 无用 (0)