1701005841
我和数学有约：趣味数学及算法解析 [:1701004196]
1701005842
我和数学有约：趣味数学及算法解析 4.2 四色定理
1701005843
1701005844
四色猜想是数学的难题之一。
1701005845
1701005846
四色猜想首先是在简单平面上成立的，对于地图上的各个国家来讲，需要说明的是，国家就是简单的国家，即一个国家是一个可以单独连通的一块曲面，一个国家分成几个独立的几部分在这里不考虑。对于国中国的现象和环形的国家也暂时不考虑。在这两点的前提下，再对地图作简化，将国家和国家之间的相连关系变成点和线的关系。
1701005847
1701005848
可以用点来代替国家，用点之间的连线表示国家的相连关系，对点涂色来代表对国家的着色，每一个线的两个端点颜色不能相同。这样就可以研究点和线之间的关系，用这个关系来代替对国家的着色。
1701005849
1701005850
如图4-1所示的地图，A、B、C和D代表四个国家。
1701005851
1701005852
1701005853
1701005854
1701005855
图4-1 四色地图
1701005856
1701005857
将图4-1转化为点和线的关系图，如图4-2所示。
1701005858
1701005859
1701005860
1701005861
1701005862
图4-2 点线连接图
1701005863
1701005864
点和线的关系图完全和图4-1相对应，四种颜色就可以用四种数字表示，点A代表国家A，由组合论知识可知，点A的颜色有四种选择，点B有三种选择，点C有两种选择，点D有两种选择。用四种颜色对上面的图着色，可以有4×3×2×2＝48种着色方式。
1701005865
1701005866
1701005867
1701005868
1701005869
图4-3 连接关系图2
1701005870
1701005871
如果图4-2中，D和A相接壤，则点线连接关系如图4-3所示。
1701005872
1701005873
D和A、B、C都相接，D就只有一个选择，这时有4×3×2＝24种着色方式。图4-3中的每一个点都和其他三个点相接，虽然有24种着色方式，但总是需要四种颜色。
1701005874
1701005875
1701005876
注意：文中用点来代表国家，用线来表示相连关系，这样和对国家的着色是一致的，可以使关系简化。
1701005877
1701005878
对于四色问题，有下面一些推导过程。
1701005879
1701005880
【问题】出现第五种颜色国家的充要条件是这个国家与四个两两相邻的国家都相邻。
1701005881
1701005882
【分析】
1701005883
1701005884
1701005885
1701005886
1701005887
图4-4 四个国家连接关系
1701005888
1701005889
四个国家两两相邻，用四个点和六条连线可以很清楚地表示出来，如图4-4所示。
1701005890