Ganti BAHASA

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Masuk ke Mathigon

atau

Akun baru     Setel Ulang Kata Sandi     

Graphs and Networks
Introduction
The Bridges of Königsberg
Handshakes and Dating
Planar Graphs
Map Colouring
The Travelling Salesman Problem
Scheduling Problems
Graphs in Everyday Life

Bagikan

Setel Ulang Kemajuan

Ini akan menghapus kemajuan dan data obrolan Anda untuk semua bab dalam kursus ini, dan tidak dapat dibatalkan!

Glosarium

Pilih salah satu kata kunci di sebelah kiri…

Graphs and NetworksMap Colouring

Waktunya membaca: ~15 min

We have already used graph theory with certain maps. As we zoom out, individual roads and bridges disappear and instead we see the outline of entire countries.

When colouring a map – or any other drawing consisting of distinct regions – adjacent countries cannot have the same colour. We might also want to use as few different colours as possible.

Some simple “maps”, like a chessboard, only need two colours (black and white), but most complex maps need more.

When colouring the map of US states, 50 colours are obviously enough, but far fewer are necessary. Try colouring the maps below with as few colours as possible:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

All of these maps can be coloured with only four different colours, but it is not hard to imagine that other, very complicated maps might need many more colours. In fact, some maps need at least four colours, whenever they contain four countries all connected to each other.

Like before, we can convert a map with countries and borders into a planar graph: every country becomes , and countries which get connected by an edge:

Now we want to colour the vertices of a graph, and two vertices must have a different colour if they are connected by an edge.

In 1852, the botany student Francis Guthrie had to colour a map of counties in England. He observed that four colours seemed to suffice for any map he tried, but he was not able to find a proof that worked for all maps. This turned out to be an extremely difficult problem, and became known as the four colour theorem.

During the following 100 years, many mathematicians published “proofs” to the four colour theorem, only for mistakes to be found later. Some of these invalid proofs were so convincing that it took more than 10 years to discover errors.

For a long time, mathematicians were unable to either prove that four colours are enough, or to find a map that needed more than four colours.

Little progress was made on the four colour problem until 1976, when Wolfgang Haken and Kenneth Appel used a computer to finally solve it. They reduced infinitely many possible maps to 1936 special cases, which were each checked by a computer taking over 1000 hours in total.

The four colour theorem is the first well-known mathematical theorem to be proven using a computer, something that has become much more common and less controversial since. Faster computers and a more efficient algorithm mean that today you can prove the four colour theorem on a laptop in just a few hours.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

The four colour theorem only works for maps on a flat plane or a sphere, and where all countries consist of a single area.

However, mathematicians have also looked at maps of empires, where countries can consist of multiple disconnected components, and at maps on differently-shaped planets, such as a torus (doughnut shape). In these cases you may need more than four colours, and the proofs become even more difficult.

This map on a torus requires seven colours.

Archie