请输入您要查询的字词:

 

单词 FourcolorConjecture
释义

four-color conjecture


The four-color conjecture was a long-standing problem posed by Francis Guthrie to his professor Augustus De Morgan in 1852, while coloringMathworldPlanetmath a map of England. The conjecture states that every map on a plane or a sphere can be colored using only four colors such that no two adjacent countries are assigned the same color. There are maps that need four colors to be colored as the figure below shows. This conjecture equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the statement that chromatic numberMathworldPlanetmath of every planar graphMathworldPlanetmath is no more than four.

\\scale1 1\\gsave\\code00.5 0 setrgbcolor newpath 180 100 moveto 100 100 80 0 360 arc 150100 moveto 100 100 50 360 0 arcn fill 1 0 0 setrgbcolor newpath100 100 moveto 150 100 lineto 100 100 50 0 120 arc closepath fill0 0 1 setrgbcolor newpath 100 100 moveto 120 cos 50 mul120 sin 50 mul rlineto 100 100 50 120 240 arc closepathfill 1 1 0 setrgbcolor newpath 100 100 moveto 240 cos 50 mul240 sin 50 mul rlineto 100 100 50 240 360 arc closepathfill \\grestore
Figure 1: Four mutuallyadjacent countries

After many unsuccessful attempts the conjecture was proven by Appel and Haken in 1976 with the aid of a computer. Before it was known that every planar map can be five-colored by the work of Heawood in 1890.

Interestingly, the seemingly harder problem of determining themaximal number of colors needed for all surfaces other than thesphere was solved long before the four-color conjecture wassettled. This is the Heawood number of the surface unless the surfaceis the Klein bottle in which case it is 6.

References

  • 1 Kenneth O. May. The origin of the four-color conjecture. Isis, 56(3):346–348, 1965. http://links.jstor.org/sici?sici=0021-1753%28196523%2956%3A3%3C346%3ATOOTFC%3E2.0.CO%3B2-ZAvailableonline at http://www.jstor.orgJSTOR.
  • 2 Thomas L. Saaty and Paul C. Kainen. The Four-Color Problem: Assaults and Conquest. Dover, 1986. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0463.05041Zbl0463.05041.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 12:07:14