Věta o pěti barvách - Five color theorem
The pět barevná věta je výsledkem od teorie grafů která dala rovinu rozdělenou do oblastí, jako je a politická mapa z krajů státu, regiony mohou být obarveny pomocí ne více než pěti barev takovým způsobem, že žádné dva sousední regiony nedostanou stejnou barvu.
Věta o pěti barvách je implikována silnější čtyřbarevná věta, ale je podstatně snazší to dokázat. Bylo založeno na neúspěšném pokusu o čtyřbarevný nátisk od Alfred Kempe v roce 1879. Percy John Heawood našel chybu o 11 let později a dokázal pětibarevnou větu založenou na Kempeho práci.
Nástin důkazu rozporem
Nejprve si člověk spojí jednoduché rovinné graf k dané mapě, konkrétně jeden dá a vrchol v každé oblasti mapy pak spojí dva vrcholy s okraj právě tehdy, pokud příslušné regiony sdílejí společnou hranici. Úloha je poté převedena do úlohy zbarvení grafu: je třeba malovat vrcholy grafu tak, aby žádná hrana neměla koncové body stejné barvy.
Protože je jednoduchý rovinný, tj. může být vložen do roviny bez protínajících se hran a nemá dva vrcholy sdílející více než jednu hranu a nemá smyčky, pak může být zobrazen (pomocí Eulerova charakteristika roviny), že musí mít vrchol sdílený nejvýše pěti hranami. (Poznámka: Toto je jediné místo, kde je v korektuře použita pětibarevná podmínka. Pokud je tato metoda použita k prokázání čtyřbarevné věty, v tomto kroku selže. Ve skutečnosti icosahedral graf je 5 pravidelný a rovinný, a proto nemá vrchol sdílený nanejvýš čtyřmi hranami.) Najděte takový vrchol a zavolejte jej .
Nyní odeberte z . Graf získaný tímto způsobem má o jeden vrchol méně než , takže můžeme předpokládat, že indukce že lze obarvit pouze pěti barvami. musí být spojeno s pěti dalšími vrcholy, protože pokud to tak není, může být zbarveno dovnitř s barvou, kterou nepoužívají. Takže teď se podívej na těch pět vrcholů , , , , které sousedily s v cyklickém pořadí (což závisí na tom, jak píšeme G). Pokud jsme na nich nepoužili všech pět barev, pak samozřejmě můžeme malovat konzistentním způsobem vykreslit náš graf 5-barevný.
Můžeme to tedy předpokládat , , , , jsou vybarveny barvami 1, 2, 3, 4, 5.
Nyní zvažte podgraf z skládající se z vrcholů, které jsou vybarveny pouze barvami 1 a 3, a hran, které je spojují. Aby bylo jasné, každá hrana spojuje vrchol barvy 1 s vrcholem barvy 3 (toto se nazývá a Řetěz Kempe ). Li a leží v různých připojených součástech , můžeme zaměnit 1 a 3 barvy na komponentě obsahující , čímž uvolníte barvu 1 pro a dokončení úkolu.
Pokud naopak a leží ve stejné připojené složce , můžeme najít cestu dovnitř spojuje je a skládá se pouze z barevných vrcholů 1 a 3.
Nyní se obraťte na podgraf z skládající se z vrcholů, které jsou vybarveny pouze barvami 2 a 4 a hranami, které je spojují, a použijí stejné argumenty jako dříve. Pak jsme buď schopni obrátit 2-4 zbarvení na podgrafu obsahující a malovat barva 2, nebo se můžeme připojit a s cestou, která se skládá pouze z barevných 2 a 4 vrcholů. Druhá možnost je zjevně absurdní, protože taková cesta by protínala 1-3 barevnou cestu, kterou jsme postavili dříve.
Tak může být ve skutečnosti pětibarevný, na rozdíl od počátečního předpokladu.
Algoritmus pětibarevného lineárního času
V roce 1996 popsali Robertson, Sanders, Seymour a Thomas ve svých „Efektivně čtyřbarevných planárních grafech“ kvadratický čtyřbarevný algoritmus.[1] Ve stejné práci stručně popisují algoritmus pětibarevného lineárního času, který je asymptoticky optimální. Algoritmus, jak je zde popsán, pracuje na multigrafech a spoléhá na schopnost mít více kopií hran mezi jednou dvojicí vrcholů. Je to založeno na Wernickova věta, který uvádí následující:
- Wernickova věta: Předpokládejme G je rovinný, neprázdný, nemá žádné plochy ohraničené dvěma hranami a má minimum stupeň 5. Pak G má vrchol stupně 5, který sousedí s vrcholem stupně nejvýše 6.
Použijeme reprezentaci grafu, ve kterém každý vrchol udržuje kruhový propojený seznam sousedních vrcholů ve směru hodinových ručiček.
V koncepci je algoritmus rekurzivní, redukuje graf na menší graf s jedním menším vrcholem, pětibarevný tento graf a poté pomocí tohoto vybarvení určí zbarvení většího grafu v konstantním čase. V praxi namísto zachování explicitní reprezentace grafu pro každý zmenšený graf odstraníme vrcholy z grafu, jak jdeme, přidáme je do zásobníku a poté je zbarvíme, když je na konci vysuneme zpět ze zásobníku. Budeme udržovat tři hromádky:
- S4: Obsahuje všechny zbývající vrcholy s buď stupněm maximálně čtyřmi, nebo stupněm pět a nejvýše čtyřmi odlišnými sousedními vrcholy (kvůli více hranám).
- S5: Obsahuje všechny zbývající vrcholy, které mají stupeň pět, pět odlišných sousedních vrcholů a alespoň jeden sousední vrchol s stupněm maximálně šest.
- Sd: Obsahuje všechny vrcholy odstraněné z grafu v pořadí, v jakém byly odstraněny.
Algoritmus funguje následovně:
- V prvním kroku sbalíme všechny více hran na jednotlivé hrany, aby byl graf jednoduchý. Dále iterujeme přes vrcholy grafu a tlačíme na jakýkoli vrchol odpovídající podmínkám pro S4 nebo S.5 do příslušného stohu.
- Dále, pokud S4 není prázdný, my pop proti od S.4 a smazat proti z grafu, zatlačením na Sd, spolu se seznamem jeho sousedů v tomto okamžiku. Zkontrolujeme každého bývalého souseda proti, zatlačením na S4 nebo S.5 pokud nyní splňuje nezbytné podmínky.
- Když s4 stane se prázdným, víme, že náš graf má minimální stupeň pět. Pokud je graf prázdný, přejdeme k poslednímu kroku 5 níže. Jinak nám Wernickeova věta říká, že S5 je neprázdné. Pop proti mimo S5, odstranit z grafu a nechat proti1, proti2, proti3, proti4, proti5 být bývalými sousedy proti ve směru hodinových ručiček, kde proti1 je sousedem maximálně 6. Zkontrolujeme, zda proti1 sousedí s proti3 (což můžeme dělat v konstantním čase kvůli stupni proti1). Existují dva případy:
- Li proti1 nesousedí s proti3, můžeme spojit tyto dva vrcholy do jediného vrcholu. Za tímto účelem odstraníme proti z obou kruhových seznamů sousedství a poté oba seznamy spojit do jednoho seznamu v místě, kde proti byl dříve nalezen. Pokud proti udržuje odkaz na svou pozici v každém seznamu, to lze provést v konstantním čase. Je možné, že by to mohlo vytvořit plochy ohraničené dvěma hranami ve dvou bodech, kde jsou seznamy spojeny dohromady; odstraníme jednu hranu ze všech takových ploch. Poté to zatlačíme proti3 na Sd, spolu s poznámkou, že proti1 je vrchol, s nímž byl sloučen. Jakékoli vrcholy ovlivněné sloučením jsou podle potřeby přidány nebo odebrány ze zásobníků.
- V opačném případě, proti2 leží uvnitř obličeje ohraničeného proti, proti1, a proti3. Tudíž, proti2 nemůže sousedit s proti4, který leží mimo tento obličej. Sloučíme proti2 a proti4 stejným způsobem jako proti1 a proti3 výše.
- Přejděte na krok 2.
- V tomto bodě S4, S.5a graf jsou prázdné. Vyklopíme vrcholy z S.d. Pokud byl vrchol v kroku 3 sloučen s jiným vrcholem, vrchol, s nímž byl sloučen, již byl zbarven a my mu přiřadíme stejnou barvu. To je platné, protože jsme spojili pouze vrcholy, které v původním grafu nesousedily. Pokud jsme jej v kroku 2 odstranili, protože měl maximálně 4 sousední vrcholy, všichni jeho sousedé v době jeho odstranění již byli vybarveni a můžeme mu jednoduše přiřadit barvu, kterou žádný z jeho sousedů nepoužívá.
Viz také
Reference
- ^ Robertson, Neil; Sanders, Daniel P.; Seymour, Paule; Thomas, Robin (1996), „Efektivně čtyřbarevné planární grafy“ (PDF), Proc. 28. ACM Symposium on Theory of Computing (STOC), New York: ACM Press.
Další čtení
- Heawood, P. J. (1890), "Map-Color Theorems", Quarterly Journal of Mathematics, Oxford, 24, str. 332–338