五色定理
五色定理是图论中的一个结论:将一个平面分成若干区域,给这些区域染色,且保证任意相邻区域没有相同颜色,那么所需颜色不超过五种。五色定理比四色定理弱,也比四色定理更容易证明。1879年,阿尔弗雷德·布雷·肯普给出了四色定理的一个证明,当时为人所接受,但11年后,珀西·约翰·希伍德却发现了肯普的证明中存在错误,他把肯普的证明加以修改,得到了五色定理。
证明编辑
以下是对五色定理的证明[1]。
给定 阶平面图 ,我们对 的阶数进行归纳证明。
当 时,正确性显然。
假设 且对于任意的 阶平面图该结论成立。因为 是平面图,那么存在点 ,满足 (通过欧拉公式可知对任意平面图 , )。
考虑图 。因为 ,由归纳假设知 能进行5-着色。假设 使用 五种颜色着色。考虑 的相邻点,如果在 中它们用了不到五种颜色着色,那么我们从剩下的颜色中选一个为 着色,就得到了 的一个5-着色方式。如果在 中它们用上了所有五种颜色,这就意味着 有且仅有5个相邻点( ),从顺时针方向我们依次称它们为 ,不失一般性,假设 的颜色为 。
我们希望通过调整 的着色方式,使得 有色可染。考虑 中所有颜色为 或 的点。
- 如果 中不存在这样一条连接 与 的路径,路径上所有点的颜色均为 或 。定义 是满足以下条件的所有路径的并集:以 为起点且路径上所有点的颜色均为 或 。注意到 。此时我们可以将 中所有点的颜色互换:把 换成 ,把 换成 。交换之后也是 的一个5-着色方式。此时 的颜色变成了 ,我们将 染为 。因此, 能进行5-着色。
- 如果 中存在这样一条连接 与 的路径,路径上所有点的颜色均为 或 ,我们称之为 。注意到 与 共同形成了一个环,这个环要么把 要么把 圈在里面。此时我们发现,不存在这样一条连接 与 的路径,路径上所有点的颜色均为 或 。我们只需按照情况1中的方式调整颜色即可。因此, 能进行5-着色。
综上所述, 能进行5-着色。
参考资料编辑
- Heawood, P. J., Map-Colour Theorems, Quarterly Journal of Mathematics, Oxford 24, 1890, 24: 332–338
- ^ Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael, Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag New York: 98–99, 2008, ISBN 978-0-387-79711-3, doi:10.1007/978-0-387-79711-3
🔥 Top keywords: Baike: 首页Special:搜索毛泽东家族榮耀之繼承者天之驕女鐵拳英雄九龍城寨之圍城黃循財背着善宰跑篠崎泫妮妃雅新生 (网络剧)劉偉健斯洛伐克习近平劉俊謙 (香港)李显龙歌手2024佛誕淚之女王2024年泰國羽球公開賽新加坡總理邊佑錫新加坡Energy (組合)庆余年九龍寨城六四事件家族榮耀金智媛彌助菲律宾胖猫跳江事件劉寶傑DAY6林峯張文傑李光耀神耆小子張鳳妮黃世聰Seventeen (組合)维基百科願榮光歸香港中華民國鬼滅之刃 柱訓練篇2024年英雄联盟季中邀请赛中华人民共和国TripleS金秀賢 (男演員)罗伯特·菲佐井柏然2024年世界女排联赛黃偉哲怪獸8號佘詩曼Foodpanda金惠奫新加坡总统香緹·摩爾于北辰 (1968年)王嘉爾笑看風雲排球少年!!角色列表林飛帆郭葦昀馴鹿寶貝翁靜晶猩球崛起:王國誕生ILLIT尼古拉·約基奇春色寄情人周殷廷鬼滅之刃排球少年!!吳釗燮逆天奇案2不夠善良的我們BABYMONSTER李正皓尚达曼BOYNEXTDOOR胡子彤IVE (組合)陳靜 (香港)香港吴作栋黃道十二宮凡希亚·奥伊亚胡宇威長洲太平清醮張員瑛搜查班長1958伍允龍习明泽黄岩岛賴清德偶然遇見的你虽然不是英雄