联想企业网站建设的思路,网站建设技术外文,网站开发学习案例,wordpress英文升级为中文目录
一#xff0c;k流
二#xff0c;整数流
三#xff0c;四色问题 一#xff0c;k流
Tutte在研究四色问题时#xff0c;开创了整数流理论。
他研究的具体问题是#xff0c;给定一个有向图和一个k阶交换群#xff0c;能不能找到一个函数#xff0c;把图的每个边映…目录
一k流
二整数流
三四色问题 一k流
Tutte在研究四色问题时开创了整数流理论。
他研究的具体问题是给定一个有向图和一个k阶交换群能不能找到一个函数把图的每个边映射到群的一个非零元素使得对于每一个点进入该点的所有边的函数值之和等于离开该点的所有边的函数值之和。
如果存在那么称这个函数为一个k流
二整数流
Tutte证明是否存在k流和交换群的结构无关只和k有关。
所以我们只需要考虑整数模k的群即可这是最简单的交换群。
那么是否存在k流可以表述为给定一个有向图和一个k阶交换群能不能找到一个函数把图的每个边赋予一个权值为1到k的整数使得对于每一个点进入该点的所有边的权值之和和离开该点的所有边的权值之和模k同余。
于是k流问题也被称之为整数流问题。
三四色定理
四色定理的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”
Tutte证明一个平面图是否可以k着色等价于是否存在k流。
所以任意一个平面图都可以4着色等价于任意一个平面图都存在4流。
按照这个思路借助计算机证明四色猜想才变成四色定理。
四色定理的例子
