Four-colour map problem

Japanese: 四色問題 - よんしょくもんだい（英語表記）four-colour map problem

A topology problem posed in the early 1850s. The question is what is the minimum number of colors required to color adjacent areas of a map, i.e., areas with a common border, without the same color. The fact that three colors is not enough can be easily shown by drawing a map with four areas that cannot be colored with three colors. Map dealers and others have long known from experience that four colors are sufficient. Based on arguments in a paper published in 1879 by British lawyer Alfred Bray Kemp, it was shown that any map can be colored with five colors. It is known that a map drawn on a torus (a circular ring, the curved surface of a doughnut) requires at least seven colors. The four-coloring problem is dually equivalent to the problem of coloring a plane graph so that vertices connected by edges have different colors, and has been studied from the perspectives of topology and graph theory. In 1977, a group of mathematicians at the University of Illinois led by Kenneth I. Appel and Wolfgang Haken created a list of 1,936 possible maps, and showed that any map that cannot be colored with four colors can be reduced to one of these cases, thus proving that all maps can be colored with four colors. This proof essentially involved the use of computers. Attempts to provide non-computer proofs of the Four Color Problem are still being made today.

Source: Encyclopaedia Britannica Concise Encyclopedia About Encyclopaedia Britannica Concise Encyclopedia Information

Japanese:

1850年代初めに提出された位相幾何学（→トポロジー）に関する問題。地図の隣り合った領域，すなわち共通の境界線をもつ領域が，同じ色にならないように塗り分けるには，最低何色の色が必要かという問題である。3色では足りないことは，実際に 3色では塗り分けられない 4個の領域からなる地図を描くことによって容易に示すことができる。地図の業者などの間では，古くから 4色で十分であることが経験的に知られていたようである。1879年イギリスの弁護士アルフレッド・ブレイ・ケンプが発表した論文の議論に基づいて，どのような地図も 5色で塗り分けることができることが示された。トーラス（輪環体。ドーナツの表面の曲面）上に描かれた地図については，最低 7色が必要であることが知られている。四色問題は，双対的に考えると，平面グラフの辺で結ばれた頂点が互いに異なった色になるように彩色する問題と同値であり，位相幾何学およびグラフ理論の立場から研究されてきた。1977年にケネス・I.アッペルとウォルフガング・ハーケン率いるイリノイ大学の数学者のグループによってこの問題は解決された。アッペルとハーケンらは 1936通りの地図のリストをつくり，4色で塗り分けられない地図があるとしてもこれらのいずれかの場合に帰着されることを示し，結果としてすべての地図は 4色で塗り分けられることを証明した。この証明ではコンピュータが本質的に用いられた。四色問題に対してコンピュータを用いない証明を与える試みは今日もなされている。

出典　ブリタニカ国際大百科事典小項目事典ブリタニカ国際大百科事典小項目事典について　情報

<<: Land pawning registration rules - Land pawning registration rules

>>: Autogamous plant - Self-pollinating plant