Promjena jezika

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

Prijavite se u Mathigon

ili

Novi profil     Resetiranje lozinke     

Grafikoni i mreže
Uvod
Königsberški mostovi
Rukovanje i druženje
Ravni grafikoni
Bojanje karte
Problem putničkog prodavca
Problemi s planiranjem
Grafovi u svakodnevnom životu

Podijeli

Poništavanje napretka

Ovim ćete izbrisati podatke o napretku i chatu za sva poglavlja ovog tečaja i ne možete ih poništiti!

Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeBojanje karte

Vrijeme čitanja: ~10 min

Već smo koristili teoriju grafova s određenim mapama. Kako smanjivamo, pojedini putevi i mostovi nestaju i umjesto toga vidimo obris cijelih zemalja. Prilikom bojanja karte - ili bilo kojeg drugog crteža koji se sastoji od različitih regija - susjedne zemlje ne mogu imati istu boju. Također bismo željeli koristiti što manje različitih boja. Neke jednostavne "mape", poput šahovske ploče, trebaju samo dvije boje (crnu i bijelu), ali većina složenih karata treba više.

Pri bojanju karte američkih država 50 boja je očigledno dovoljno, ali je potrebno mnogo manje. Pokušajte obojiti donje karte s što manje boja:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

Sve ove karte mogu se obojiti sa samo četiri različite boje, ali nije teško zamisliti da su druge, vrlo složene karte možda će trebati mnogo više boja. Zapravo, nekim mapama je potrebno najmanje četiri boje, kad god sadrže četiri zemlje koje su međusobno povezane.

Kao i prije, kartu možemo pretvoriti sa zemljama i granicama u ravni plan: svaka zemlja postaje , i zemlje koje spojite se rubom:

Sada želimo obojiti vrhove grafa, a dvije vrhove moraju imati drugu boju ako su povezane rubom.

  1. student botanike Francis Guthrie morao je obojiti kartu županija u Engleskoj. Primijetio je da mu se čini da su četiri boje dovoljne za bilo koju kartu koju je pokušao, ali nije uspio pronaći dokaz koji bi funkcionirao za sve karte. Pokazalo se da je to bio izuzetno težak problem, i postao je poznat kao teorema sa četiri boje. Tijekom sljedećih 100 godina, mnogi su matematičari objavili "dokaze" za teoremu o četiri boje, samo da su kasnije otkrili pogreške. Neki od tih nevaljanih dokaza bili su toliko uvjerljivi da im je trebalo više od 10 godina da otkriju pogreške. Dugo vremena matematičari nisu bili u stanju ni dokazati da su dovoljne četiri boje, niti pronaći kartu koja treba više od četiri boje.

Mali napredak postignut je u vezi s problemom četiri boje do 1976. godine, kada su Wolfgang Haken i Kenneth Appel upotrijebili računalo da bi ga konačno riješili. Smanjili su beskonačno mnogo mogućih karata na posebne slučajeve iz 1936., koje je svaki provjeravao računar koji je ukupno trajao više od 1000 sati.

Teorema s četiri boje prva je poznata matematička teorema dokazana pomoću računala, što je od tada postalo mnogo češći i manje kontroverzni. Brži kompjuteri i učinkovitiji algoritam znače da danas možete dokazati teoremu o četiri boje na prijenosnom računalu u samo nekoliko sati.

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

Teorema s četiri boje djeluje samo za karte na ravnoj ravnini ili sferi, a gdje se sve zemlje sastoje od jednog područja.

Međutim, matematičari su također pogledali mape carstava, gdje se zemlje mogu sastojati od više isprepletenih komponenti, i karte na planetima različitog oblika, poput torusa (krofni oblik). U tim će vam slučajevima trebati više od četiri boje i dokazi će postati još teži.

This map on a torus requires seven colours.

Archie