Aplikácia teórie grafov
Rovinné grafy
Graf G je považovaný za rovinný, ak môže byť znázornený v rovine takým spôsobom, že vrcholy sú všetky zreteľné body, hrany sú jednoduché krivky a žiadne dva hrany sa navzájom nestretávajú, s výnimkou ich koncoviek. Napríklad, K 4, kompletné graf na štyri vrcholy, je rovinný, ako ukazuje obrázok 4A.
Dva grafy sa označujú ako homeomorfné, ak je možné ich získať z toho istého grafu rozdelením hrán. Napríklad grafy na obrázkoch 4A a 4B sú homeomorfné.
Graf Km , n je graf, pre ktorý je možné vrchol rozdeliť na dve podmnožiny, jednu s vrcholmi m a druhú s vrcholmi n. Akékoľvek dva vrcholy tej istej podmnožiny nie sú susediace, zatiaľ čo akékoľvek dva vrcholy rôznych podmnožín susedia. Poľský matematik Kazimierz Kuratowski v roku 1930 preukázal nasledujúcu slávnu vetu:
Nutnou a postačujúcou podmienkou grafu G do byť rovná je, že neobsahuje subgraph homeomorfní buď K 5 alebo K 3,3 je znázornené na obrázku 5.
Elementárne kontrakcie grafu G je transformácia G v novom grafe G 1, tak, že dva susedné vrcholy u a υ G je nahradené nový vrchol w G 1 a W je priľahlý v G 1 pre všetky vrcholy k ktorý u alebo υ susedí v G. Graf G * je považovaný za kontrakciu G, ak G * možno získať z G pomocou sledu elementárnych kontrakcií. Nasleduje ďalšia charakteristika rovinného grafu kvôli nemeckému matematikovi K. Wagnerovi v roku 1937.
Graf je rovinný vtedy a len vtedy, ak nie je kontrahovateľný s K 5 alebo K 3,3.
Problém so štyrmi farebnými mapami
Riešenie problému farebnej mapy už viac ako jedno storočie uniklo každému analytikovi, ktorý sa o to pokúsil. Tento problém mohol upútať pozornosť Möbia, ale prvá písomná zmienka o ňom sa zdá byť listom jedného Francis Francis Guthrie jeho bratovi, študentovi Augusta De Morgana, z roku 1852.
Tento problém sa týka rovinných máp - rozdelenie roviny na neprekrývajúce sa oblasti ohraničené jednoduchými uzavretými krivkami. V geografických mapách sa empiricky zistilo, že v mnohých osobitných prípadoch, ako sa vyskúšalo, sú nanajvýš potrebné štyri farby, aby sa zafarbili regióny tak, aby dva regióny, ktoré zdieľajú spoločnú hranicu, boli vždy zafarbené odlišne a v niektorých prípadoch sú potrebné najmenej štyri farby. (Regióny, ktoré sa stretávajú iba v určitom bode, napríklad v štátoch Colorado a Arizona v Spojených štátoch, sa nepovažujú za spoločné hranice). Formalizácia tohto empirického pozorovania predstavuje to, čo sa nazýva „štvorfarebná veta“. Problémom je dokázať alebo vyvrátiť tvrdenie, že to tak je pre každú planárnu mapu. To, že tri farby nebudú stačiť, sa ľahko preukáže, zatiaľ čo dostatok piatich farieb preukázal v roku 1890 britský matematik PJ Heawood.
V roku 1879 Angličan AB Kempe navrhol riešenie problému štyroch farieb. Hoci Heawood ukázal, že argument Kempe bol chybný, dva z jeho konceptov sa v neskoršom vyšetrovaní ukázali ako plodné. Jedna z nich, nazývaná nevyhnutnosť, správne uvádza nemožnosť vytvorenia mapy, v ktorej chýba každá zo štyroch konfigurácií (tieto konfigurácie pozostávajú z oblasti s dvoma susedmi, jednou s tromi, jednou so štyrmi a jednou s piatimi). Druhý koncept, pojem redukovateľnosti, vychádza z platného dôkazu spoločnosti Kempe, že ak existuje mapa, ktorá vyžaduje najmenej päť farieb a ktorá obsahuje oblasť so štyrmi (alebo tromi alebo dvoma) susedmi, musí existovať mapa vyžadujúca päť farby pre menší počet regiónov. Kempeov pokus dokázať redukovateľnosť mapy obsahujúcej región s piatimi susedmi bol chybný, ale napravil sa to dôkazom, ktorý v roku 1976 uverejnili Kenneth Appel a Wolfgang Haken zo Spojených štátov. Ich dôkaz priťahoval určitú kritiku, pretože si vyžadovalo vyhodnotenie 1 936 rôznych prípadov, z ktorých každý obsahoval až 500 000 logických operácií. Appel, Haken a ich spolupracovníci vymysleli programy, ktoré umožnili veľkému digitálnemu počítaču spracovať tieto podrobnosti. Počítač vyžadoval na vykonanie úlohy viac ako 1 000 hodín a výsledný formálny dôkaz má niekoľko sto strán.
Eulerovské cykly a problém mosta Königsberg
Multigraf G pozostáva z neprázdnej sady V (G) vrcholov a podskupiny E (G) sady neusporiadaných párov rôznych prvkov V (G) s frekvenciou f ≥ 1 pripojenou ku každému páru. Ak pár (x 1, x 2) s frekvenciou f patrí do E (G), potom vrcholy x 1 a x 2 sú spojené hranami f.
Euleriánsky cyklus multigrafu G je uzavretá reťaz, v ktorej sa každá hrana objaví presne jedenkrát. Euler ukázal, že multigraf má Eulerov cyklus, iba ak je pripojený (okrem izolovaných bodov) a počet vrcholov nepárneho stupňa je buď nula alebo dva.
Tento problém vznikol najskôr nasledujúcim spôsobom. Rieka Pregel, ktorá vznikla sútokom jej dvoch vetiev, preteká mestom Königsberg a tečie po oboch stranách ostrova Kneiphof. Ako je znázornené na obrázku 6A, bolo sedem mostov. Obyvatelia mesta sa pýtali, či je možné ísť na prechádzku a prechádzať cez každý most len raz. Toto je ekvivalentné nájdeniu eulerovského cyklu pre viacgraf na obrázku 6B. Euler ukázal, že je to nemožné, pretože existujú štyri vrcholy nepárneho poriadku.
