四色定理简便证明论文

四色定理的简便证明在每一张地图上，不论行政区域多么复杂，最多使用四种颜色，就能够给所有有公共边界的不同地区着有不同的颜色加以区别开来，这就是著名的四色定理.下面，我们给出四色定理的一种简便证法.一、没有公共边界的不同地区没有公共边界的不同地区，只需要使用同一种颜色就可以区别开来.例如，山东省与黑龙江省没有公共边界，这两个省可以使用同一种颜色；再如，海南省、台湾省以及海域中的诸岛等也可以使用同一种颜色.二、含有公共边界的不同地区含有公共边界的不同地区，着有颜色的种数多少与不同地区两两彼此有公共边界的多少有关，两两彼此有公共边界的不同地区越多，着有颜色的种数就越多.两两彼此有公共边界的含义是指每两个地区都含有公共边界.例如，甲、乙、丙三个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，乙地与丙地有公共边界；甲、乙、丙、丁四个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，甲地与丁地有公共边界，乙地与丙地有公共边界，乙地与丁地有公共边界，丙地与丁地有公共边界.地图上的不同地区，我们可以分别用点a，b，c，d，e…来表示；不同地区所着用的不同的颜色分别用a，b，c，d…来表示；相邻不同地区的公共边界，用连接两点（表示该相邻的地区）之间的一条线段来表示，并且每条线段的两个端点所表示不同的地区所使用的颜色是不同的，这样，不同地区的着色问题可以看做是不同点的着色问题.规定1：每两个有公共边界的不同地区，有且只有一条公共边界线，即不存在有三个或三个以上的不同地区共有一条边界线（共用连接点除外），也就是说，两点之间用且只用一条线段来连接.规定2：连接的所有线段除端点外，既不能重合，也不能相交.这样我们将上述四色问题可以转化为：在同一个平面上有m个不同的点，从中任取一个点pi（i=1，2，…，m）与其余（m-1）个点连接，并且连接任意两点之间的线段除端点外，既不能重合，也不能相交，则在这m个不同的点中，能够两两彼此相连接的点最多有4个.下面我们给出证明.证明：一个点或多个孤立（互不相连接）的点均可以使用同一种颜色；一条线段有两个端点，这两个端点表示不同的两个地区，该线段表示有公共边界，这样的两个地区，只需要两种不同的颜色即可区别开来.现在，我们来研究由线段组成的图形.1n（n为正整数）条线段组成的一条或多条没有封闭的图形我们知道，每一个端点（或拐点）表示不同的地区，两个相邻的不同地区的公共边界用一条线段来表示，由n（n为正整数）条线段组成的一条或多条没有封闭的图形，其所有端点（所表示的不同地区），可以需要使用a和b两种不同的颜色即可区别开来.如图1和图2所示.需要特别指出的是在同一条线段（或直线）上的点，如图3所示，当a，b，c三点在同一条线段上时，线段ac与线段ab，bc重合，这意味着它们有两条公共边界线，这与“不同地区有且只有一条公共边界线”矛盾，因此，我们说“连接ab，bc”，此时不能说“连接ac”.不能说“连接ac”的意思是说地区a和c没有公共边界，它们可以取同一种颜色.2.由n（n≥3）条线段组成的一条封闭的图形（1）当n为奇数时，该图形中的所有顶点（所表示的不同地区），可以需要使用a，b，c三种不同的颜色即可区别开来，如图4所示.图4（2）当n为偶数时，该图形中的所有顶点（所表示的不同地区），可以需要使用a，b两种不同的颜色即可区别开来，如图5所示.图5三、在三角形的基础上，增加一个点所构成的图形从上面的分析来看：一个点只使用一种颜色；一条线段有两个端点，该端点需要使用两种不同的颜色；一个三角形有三个顶点，该顶点需要使用三种不同的颜色.设存在有三个不同的地区两两彼此有公共边界，即存在不共线的三个点a，b，c连接成一个三角形，如图6所示，在这个平面上增加一个点d，有如下情况：图6图7由于不同的点表示不同的地区，所以点d与三角形的顶点不能重合，即点d不能在三角形的顶点处；当点d在△abc的任一条边上时，不妨假设点d在边ac上，如图7所示，由于线段ac与线段ad，cd重合，这与规定“所有线段不能重合”矛盾，所以点d不能在△abc的任一条边上.显然，如果有4个不同的点，其中有三个点a，b，d两两彼此相连接（即a，b，d三点所表示的地区两两彼此有公共边界），也就是说点b与a连接、点b与d连接、点d与a连接；第4个点c 与点b连接，与点d连接，而点c与a不连接（此时，点a，c所表示的两个不同地区没有公共边界线），且a，d，c三点共线，此时，点a与c可以取同一种颜色（我们可以看做点c在△abd的外部如图7所示），那么这样的4个点所表示的不同地区，可以使用a，b，c三种不同的颜色就可以区别开来.这样，我们只研究点在三角形的内部和外部两种情况就可以了.1.当点d在△abc内部时，如果第4个点d与三角形的三个顶点a，b，c两两彼此相连接，如图8所示，那么所有顶点所表示的不同地区，需要使用a，b，c，d四种不同的颜色就可以区别开来.图8图92.当点d在△abc外部时，（1）不妨假设点d在线段ac所在的直线上，即点d，a，c三点共线，如果能够连接db，da，那么所有顶点或端点所表示的不同地区，需要使用a，b，c三种不同的颜色就可以区别开来，如图9所示.（2）不妨假设点d不在线段ac所在的直线上，且点d与b在线段ac所在直线的两侧，如果能够连接da，db，dc，且线段db与线段ac不相交，那么所有顶点（或端点）所表示的不同地区，需要使用a，b，c，d四种不同的颜色即可区别开来，如图10所示；若能够连接da，dc，当连接db时，线段db与线段ac有可能“相交”，则所有顶点（或端点）所表示的不同地区，需要使用a，b，c 三种不同的颜色即可区别开来，如图11所示.图10图11（3）不妨假设点d不在线段ac所在的直线上，且点d与b在线段ac所在直线的同侧，如图12和图13所示，此时，结果与②类似，不必赘述.图12图13由上述所知，如果每4个点满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的4个点所表示的不同地区，只需要使用a，b，c，d四种不同的颜色即可区别开来.四、在如图8所示的基础上，增加一个点所构成的图形我们从上面的分析可以得到一般结论：在同一个平面上，存在3个点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的3个点所表示的不同地区，需要使用三种不同的颜色；在同一个平面上，存在4个点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的4个点所表示的不同地区，需要使用四种不同的颜色.我们自然要问：在同一个平面上，存在5个点或5个以上的点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的5个点或5个以上的点所表示的不同地区，就需要使用五种或更多种不同的颜色吗？回答是不可能的.这是因为，在同一个平面上，有5个点或5个以上的不同点是不可能存在两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交的，从而说明，在同一个平面上，不存在超过四种不同的颜色.我们给出如下推理：在如图8所示的基础上，再增加一个点e，共计5个点，有如下几种情况：（1）如果第5个点e落在△abc的外部，那么点e与△abc内部的点d不能够连接.假设点e与d能够连接，由于△abc是一个封闭的图形，一个点e在△abc的外部，一个点d在△abc的内部，当连接ed时，必然与△abc中的某一条边相交，这与规定（所有的线段不相交）矛盾，所以说尽管点e能够与点a，b，c两两彼此相连接，但点e与点d不能够连接，因此，5个不同的点两两彼此不能够相连接.此时，点e和点d可以使用同一种颜色着色，这样的5个不同点所表示的不同地区，可以需要使用a，b，c，d四种不同的颜色就可以区别开来，如图14所示.图14图15（2）如果第5个点e落在△abc的内部，那么点e必然会落在△abc内部中△abd，△bcd和△acd三个三角形中的某一个三角形的内部.不妨假设点e落在△abd的内部，如图15所示，此时，点c在△abd的外部，由（1）知点e与c不能够连接，因此，5个不同的点两两彼此不能够连接.此时，点e与c可以使用同一种颜色着色，这样的5个不同的点所表示的不同地区，可以需要使用a，b，c，d四种不同的颜色就可以区别开来.由上述所知，5个不同的点两两彼此不能够连接，这就是说，在同一个平面上，尽管由原来不同的4个点增加到5个点，多了一个点，但颜色的种数并没有增加，这是因为有一对点不能连接，该两点所表示的不同地区可以取同一种颜色，即存在有1对点着色相同，此时，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.五、在如图15所示的基础上，增加一个点所构成的图形在如图15所示的基础上，再增加一个点f，共计6个点.1.如果第6个点f在△abc的外部，那么点f与△abc内部的点e或d不能够连接，也就是说，6个不同的点两两彼此不能够连接，如图16所示.新增加的点f的着色可以取与点d的颜色相同（新增加一对着色点），点e的着色可以取与点c的颜色相同（原有的一对着色点），这样共有2对相同的着色点，这说明颜色的种数并没有增加，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.图16图172.如果第6个点f在△abc的内部，那么点f必然会落在△abe，△bed，△aed，△bcd，△acd这5个三角形中的某一个三角形的内部.不妨假设点f落在△bdc的内部，如图17所示.显然，新增加的点f与a不能够连接，它们可以取相同的颜色（新增加一对着色点）；点e与c不能够连接，它们可以取相同的颜色（原有的一对着色点），这样存在2对相同的着色点，因此，6个不同的点两两彼此不能够连接.也就是说，尽管由5个不同的点增加到6个不同的点，又多了一个点，但颜色的种数并没有增加，这是因为有2对点着色相同，此时，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.类似地，第k（5≤k≤m）个点落在如图8所示的图形中，（1）如果第k个点落在△abc的外部，那么第k个点与△abc的内部的某一点不能够连接，因此，有k个点两两彼此不能够连接，同时可以看出，第k个点可以取与△abc的内部的某一对应点（不能连接）的着色的颜色相同，这样颜色的种数没有增加，第k个点的情形与第（k-1）个点的情形的着色相同；（2）如果第k个点落在△abc的内部，那么必然会落在且只能落在△abc被分割成（2k-5）个不重叠三角形中的某一个三角形的内部，此时，该点与该三角形的外部的点不能够连接，且有（k-4）对点（不能连接的）着有对应相同的颜色，这说明颜色的种数并没有增加.综上所述，在同一个平面上，超过4个不同的点，两两彼此不能够连接，这就是说能够两两彼此连接的点最多有4个，所以，在一张地图上的所有有公共边界的不同地区，最多使用四种不同的颜色就可以加以区别开来，四色定理成立.证毕.我们根据上述判定方法来诠释中国政区地图，为何最多使用四种不同的颜色.在《中华人民共和国地图》（人民交通出版社，2003年8月第3版）上，因为最多有4个不同地区两两彼此有公共边界，这4个省两两彼此有公共边界的地区分别是宁夏回族自治区、内蒙古自治区、甘肃省和陕西省，即甘肃省与内蒙古自治区有公共边界，甘肃省与陕西省有公共边界，甘肃省与宁夏回族自治区有公共边界；内蒙古自治区与陕西省有公共边界，内蒙古自治区与宁夏回族自治区有公共边界；陕西省与宁夏回族自治区有公共边界.换句话说，如果把这4个不同地区分别看成a，b，c，d四个不同的点，由于它们两两彼此有公共边界，也就是说这4个不同点能够两两彼此相连接.如图8所示，甘肃省相当于点b，内蒙古自治区相当于点a，陕西省相当于点c，该三点a，b，c能连接成一个三角形，宁夏回族自治区相当于△abc的内部的一个点d，根据上面得到的结论，可以判断这张《中华人民共和国地图》的着色，最多使用a，b，c，d 四种不同的颜色就可以绘制而成.见附件一：《中国政区四色地图》着色分布图.再如，在《世界地图》（人民交通出版社，2003年8月第3版）上，我们看到有公共边界的国家，最多有巴拉圭、巴西、玻利维亚及阿根廷这4个国家两两彼此有公共边界（还有坦桑尼亚、莫桑比克、赞比亚和马拉维4个国家两两彼此有公共边界），它们分别用4个不同的点来表示，则这4个点之间两两彼此相连接，根据上面得到的结论，可以判断这张《世界地图》也需要使用a，b，c，d四种不同的颜色，就能够保证相邻国家着有不同的颜色加以区别开来（图形略）.附件一：方案不唯一，仅供参考.我们如果用a，b，c，d分别表示四种不同的颜色，那么不同地区的着色可以分别记成：着有a色的地区有新疆、陕西、安徽、湖南、云南以及海洋；着有b色的地区有黑龙江、辽宁、山东、山西、浙江、广东、贵州、甘肃、西藏；着有c色的地区有宁夏、吉林、河北、福建、江苏、湖北、四川、广西；着有d色的地区有内蒙古、青海、重庆、河南、江西；没有公共边界的海南和台湾及其海洋中的诸岛均可取同一种颜色（可以取不同于a色绘制），如选d色；上海市可以取d色；北京市可以取a色；天津市可以取d色；香港或澳门可以取d或c色.。