i

Aktuální číslo:

2018/11

Téma měsíce:

Psychosomatika

Barvení grafů včera a dnes

 |  4. 5. 2017
 |  Vesmír 96, 264, 2017/5

Představte si mapu světa, kde je každý stát vybarvený – samozřejmě se sousední státy barvou liší. Jaké nejmenší množství barev je potřeba? Zdánlivě jednoduchá otázka, ale dává matematikům pořádně „zabrat“ dodnes.

Jako první si tuto otázku v polovině 19. století položil anglický student F. Guthrie. Vyšlo mu, že čtyři barvy stačí na mapu anglických hrabství a na všechny mapy, které zkusil – ale nevěděl, jestli to funguje vždycky. Ukázalo se, že to neví ani žádný ze slovutných profesorů, kterých se zeptal. Po třiceti letech jiný Angličan, A. Kempe, problém vyřešil, za což byl povýšen do rytířského stavu – navzdory tom, že se v jeho řešení později našla chyba a problém zůstal otevřený další dlouhá desetiletí. Až v roce 1976 problém pomocí počítače vyřešili američtí vědci K. Appel a W. Hakken. I v jejich důkazu se posléze objevila nejasná místa a definitivní řešení našla až v roce 1996 skupina matematiků, mezi nimiž byl i český rodák Robin Thomas.

Problém, který vznikl jako studentská hříčka, tak zaměstnává přední matematiky už přes 150 let a zájem o něj stále trvá. Všechna známá řešení jsou totiž tak složitá, že pro jejich zvládnutí je potřeba počítač. Během řešení problému (a díky němu) se rozvinula nová matematická disciplína, teorie grafů: Dovnitř každého státu si nakreslíme bod (vrchol). Pokud spolu dva státy sousedí, jejich vrcholy spojíme čarou (hranou). Dostaneme něco, čemu se říká graf, v tomto případě rovinný, tj. nakreslený bez křížení hran na rovinu – list papíru. Na státy můžeme zapomenout, a budeme barvit jenom jejich reprezentace, vrcholy, přičemž stejně barevné vrcholy nesmějí být spojené hranou. Tím se problém nezměnil, ale je lépe vidět, co je důležité, a je možné o řešení lépe přemýšlet. Ale hlavně se tato formulace hodí na problémy úplně jiného typu, někdy i praktické.

Nyní vidíte 28 % článku. Co dál:

Jsem předplatitel, mám plný přístup
Jsem návštěvník
Chci si přečíst celé číslo
Předplatným pomůžete zajistit budoucnost Vesmíru. Více o předplatném
OBORY A KLÍČOVÁ SLOVA: Matematika

O autorovi

Robert Šámal

Doc. mgr. Robert Šámal, Ph.D., (*1977) vystudoval Matematickofyzikální fakultu Univerzity Karlovy. V tamním Informatickém ústavu se věnuje zejména barvení grafů a tokům v grafech. Je autorem řady vědeckých článků. S I. Kantorem a J. Matouškem napsali učebnici Mathematics++.
Šámal Robert

Doporučujeme

Závan kance

Závan kance

Oldřich Lapčík  |  5. 11. 2018
Možná jste to už také zažili. Maso máte od osvědčeného řezníka, vypadalo dobře, určitě bylo čerstvé. Tak proč, u všech všudy, přes vložené...
Je psychosomatika obchod s deštěm?

Je psychosomatika obchod s deštěm?

Vladislav Chvála  |  5. 11. 2018
Nedávné kauzy pochybných léčebných praktik, které zveřejnila Česká televize, rozbouřila odbornou i laickou veřejnost. Jsou všechny ty pokusy...
Hlubokomořské pytlíky vody

Hlubokomořské pytlíky vody uzamčeno

Adam Petrusek, Zuzana Musilová  |  5. 11. 2018
Jak jsou některé rostliny, ryby, žraloci a korýši schopni přežít několik kilometrů pod hladinou oceánů – v hloubce, kde je teplota vody velmi...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné