Aplikace teorie grafů
Rovinné grafy
Graf G je považován za rovinný, pokud může být znázorněn v rovině takovým způsobem, že vrcholy jsou všechny odlišné body, hrany jsou jednoduché křivky a žádné dvě hrany se nesetkají s výjimkou svých koncovek. Například, K 4, kompletní graf na čtyři vrcholy, je rovinný, jak ukazuje obrázek 4A.
Dva grafy jsou považovány za homeomorfní, pokud lze oba získat ze stejného grafu dělením hran. Například grafy na obr. 4A a obr. 4B jsou homeomorfní.
Graf Km , n je graf, pro který lze sadu vrcholů rozdělit na dvě podmnožiny, jednu s vrcholy m a druhou s vrcholy n. Jakékoli dva vrcholy stejné podmnožiny nejsou sousedící, zatímco jakékoli dva vrcholy různých podmnožin sousedí. Polský matematik Kazimierz Kuratowski v roce 1930 dokázal následující slavnou větu:
Nutnou a postačující podmínkou grafu G do být rovinná je, že neobsahuje subgraph homeomorfní buď K 5 nebo K 3,3 je znázorněno na obrázku 5.
Elementární kontrakce grafu G je transformace G v novém grafu G 1, tak, že dva sousední vrcholy u a υ G je nahrazeno nového vrcholu w G 1 a W je přilehlý v G 1 pro všechny vrcholy k který u nebo υ sousedí v G. Graf G * je považován za kontrakci G, pokud G * lze získat z G sekvencí elementárních kontrakcí. Následuje další charakteristika rovinného grafu kvůli německému matematiku K. Wagnerovi v roce 1937.
Graf je rovinný tehdy a jen tehdy, není-li smluvní s K 5 nebo K 3,3.
Problém čtyřbarevné mapy
Po více než století řešení problému čtyřbarevné mapy uniklo každému analytikovi, který se o to pokusil. Tento problém možná upoutal pozornost Möbia, ale první písemná zmínka o něm se zdá být dopisem jednoho Francise Guthrieho jeho bratrovi, studentovi Augustuse De Morgan, v roce 1852.
Problém se týká planárních map - tj. Dělení letadla na nepřekrývající se oblasti ohraničené jednoduchými uzavřenými křivkami. V geografických mapách bylo empiricky zjištěno, že v tolika zvláštních případech, jak bylo vyzkoušeno, jsou pro zbarvení regionů zapotřebí čtyři barvy, aby dva regiony, které sdílejí společnou hranici, byly vždy obarveny odlišně a v některých případech je nutné použít alespoň čtyři barvy. (Regiony, které se setkávají pouze v určitém bodě, jako jsou například státy Colorado a Arizona ve Spojených státech, se nepovažují za společné hranice). Formalizace tohoto empirického pozorování představuje to, čemu se říká „čtyřbarevná věta“. Problém je prokázat nebo vyvrátit tvrzení, že tomu tak je pro každou planární mapu. To, že tři barvy nebudou stačit, lze snadno prokázat, zatímco dostatečnost pěti barev byla prokázána v roce 1890 britským matematikem PJ Heawoodem.
V roce 1879 Angličan AB Kempe navrhl řešení čtyřbarevného problému. Ačkoli Heawood ukázal, že Kempe argument byl chybný, dva jeho konceptů ukázal se plodný v pozdnějším vyšetřování. Jeden z nich, nazývaný nevyhnutelnost, správně uvádí nemožnost vytvoření mapy, ve které chybí každá ze čtyř konfigurací (tyto konfigurace sestávají z oblasti se dvěma sousedy, jednou se třemi, jednou se čtyřmi a jednou s pěti). Druhý koncept, pojem redukovatelnosti, vychází z platného důkazu společnosti Kempe, že pokud existuje mapa, která vyžaduje nejméně pět barev a která obsahuje oblast se čtyřmi (nebo třemi nebo dvěma) sousedy, pak musí existovat mapa vyžadující pět barvy pro menší počet regionů. Kempeův pokus dokázat redukovatelnost mapy obsahující region s pěti sousedy byl chybný, ale byl napraven důkazem, který v roce 1976 zveřejnili Kenneth Appel a Wolfgang Haken ze Spojených států. Jejich důkaz přitahoval určitou kritiku, protože vyžadoval vyhodnocení 1 936 různých případů, z nichž každý zahrnoval až 500 000 logických operací. Appel, Haken a jejich spolupracovníci vymysleli programy, které umožnily zpracování těchto podrobností velkému digitálnímu počítači. Počítač potřeboval k provedení úkolu více než 1 000 hodin a výsledný formální důkaz je několik set stránek dlouhý.
Eulerovské cykly a problém mostu Königsberg
Multigraf G se skládá z neprázdné sady V (G) vrcholů a podskupiny E (G) sady neuspořádaných párů odlišných prvků V (G) s frekvencí f ≥ 1 připojenou ke každému páru. Pokud pár (x 1, x 2) s frekvencí f patří do E (G), pak vrcholy x 1 a x 2 jsou spojeny hranami f.
Eulerovský cyklus multigrafu G je uzavřený řetězec, ve kterém se každá hrana objevuje přesně jednou. Euler ukázal, že multigraf má eulerovský cyklus pouze tehdy, pokud je spojen (kromě izolovaných bodů) a počet vrcholů lichého stupně je nula nebo dva.
Tento problém vznikl nejprve následujícím způsobem. Řeka Pregel, vytvořená soutokem jejích dvou větví, protéká městem Königsberg a teče po obou stranách ostrova Kneiphof. Bylo vidět sedm můstků, jak je znázorněno na obrázku 6A. Obyvatelé města přemýšleli, zda je možné jít na procházku a překročit každý most jednou a jednou. To je ekvivalent k nalezení eulerovského cyklu pro vícegraf na obrázku 6B. Euler ukázal, že je to nemožné, protože existují čtyři vrcholy lichého řádu.
