Teorie grafů

Teorie grafů , odvětví matematiky zaměřené na sítě bodů spojených čarami. Předmět teorie grafů měl své počátky v rekreačních matematických problémech ( viz číselná hra), ale rozrostl se do významné oblasti matematického výzkumu s aplikacemi v chemii, operačním výzkumu, sociálních vědách a informatice.

Obrázek 1: Schéma rozdělení Ferrers pro 14. Přečtěte si více o tomto tématu Kombinatorika: Teorie grafů Graf G se skládá z neprázdné sady prvků V (G) a podmnožiny E (G) ...

Historie teorie grafů může být konkrétně stopována do roku 1735, kdy švýcarský matematik Leonhard Euler vyřešil problém mostu Königsberg. Problém mostu Königsberg byl starou hádankou, která se týkala možnosti najít cestu přes každý jeden ze sedmi mostů, které se rozprostírají po rozvětvené řece protékající kolem ostrova - ale bez překročení jakéhokoli mostu dvakrát. Euler tvrdil, že taková cesta neexistuje. Jeho důkaz zahrnoval pouze odkazy na fyzické uspořádání mostů, ale v podstatě prokázal první teorém v teorii grafů.

V 18. století byl švýcarský matematik Leonhard Euler fascinován otázkou, zda existuje cesta, která by procházela každým ze sedmi mostů přesně jednou.  Jako důkaz, že odpověď zní ne, položil základy teorie grafů.

Jak je používáno v teorii grafů, pojem graf neodkazuje na datové grafy, jako jsou liniové grafy nebo sloupcové grafy. Místo toho se odkazuje na sadu vrcholů (tj. Bodů nebo uzlů) a hran (nebo čar), které spojují vrcholy. Když jsou jakékoli dva vrcholy spojeny více než jednou hranou, graf se nazývá multigraf. Graf bez smyček a s maximálně jedním okrajem mezi libovolnými dvěma vrcholy se nazývá jednoduchý graf. Není-li uvedeno jinak, graf předpokládá se odkazovat na jednoduchém grafu. Když je každý vrchol spojen hranou s každým dalším vrcholem, graf se nazývá úplný graf. Je-li to vhodné, může být ke každé hraně přiřazen směr pro vytvoření toho, co je známé jako směrovaný graf nebo digraf.

Základní typy grafů.

Důležitým číslem spojeným s každým vrcholem je jeho stupeň, který je definován jako počet hran, které z něj vstupují nebo vystupují. Smyčka tak přispívá 2 ke stupni jejího vrcholu. Například vrcholy jednoduchého grafu znázorněné v diagramu mají stupeň 2, zatímco vrcholy úplného zobrazeného grafu jsou všechny stupně 3. Znalost počtu vrcholů v úplném grafu charakterizuje jeho podstatnou povahu. Z tohoto důvodu jsou úplné grafy běžně označeny K n , kde n se vztahuje k počtu vrcholů a všechny vrcholy K n mají stupeň n- 1. (Přeloženo do terminologie moderní teorie grafů, Eulerova věta o problému mostu Königsberg by mohla být zopakována následovně: Pokud existuje cesta podél okrajů multigrafu, která projde každou hranou jednou a pouze jednou, pak existuje nejvýše dva vrcholy lichého stupně; dále, pokud cesta začíná a končí ve stejném vrcholu, žádné vrcholy nebudou mít lichý stupeň.)

Dalším důležitým konceptem v teorii grafů je cesta, což je jakákoli cesta podél okrajů grafu. Cesta může sledovat jednu hranu přímo mezi dvěma vrcholy, nebo může sledovat více hran přes několik vrcholů. Pokud existuje cesta spojující jakékoli dva vrcholy v grafu, říká se, že graf je spojen. Cesta, která začíná a končí ve stejném vrcholu, aniž by překročila jakoukoli hranu více než jednou, se nazývá obvod nebo uzavřená cesta. Okruh, který sleduje každou hranu přesně jednou při návštěvě každého vrcholu, se nazývá euleriánský obvod a graf se nazývá eulerovský graf. Eulerovský graf je spojen a navíc všechny jeho vrcholy mají rovnoměrný stupeň.

Graf je kolekce vrcholů nebo uzlů a hran mezi některými nebo všemi vrcholy.  Pokud existuje cesta, která prochází každou hranou přesně jednou tak, že cesta začíná a končí ve stejném vrcholu, je cesta známá jako eulerovský obvod a graf je znám jako eulerovský graf.  Eulerian odkazuje na švýcarského matematika Leonharda Eulera, který vynalezl teorii grafů v 18. století.

V roce 1857 vynalezl irský matematik William Rowan Hamilton puzzle (Icosian Game), které později prodal výrobci her za 25 liber. Hádanka zahrnovala nalezení zvláštního typu cesty, později známé jako hamiltonovský obvod, podél okrajů dodekandedronu (platonické těleso skládající se z 12 pětiúhelníkových obličejů), které začíná a končí ve stejném rohu, zatímco prochází každým rohem přesně jednou. Rytířova prohlídka ( viz hra čísel: Problémy šachovnice) je dalším příkladem rekreačního problému, který zahrnuje hamiltonovský okruh. Charakteristiky hamiltonovských grafů byly náročnější než eulerovské grafy, protože potřebné a dostatečné podmínky pro existenci hamiltonovského obvodu v připojeném grafu stále nejsou známy.

Hamiltonovský obvod Graf zaměřený na směr, ve kterém cesta začíná a končí ve stejném vrcholu (uzavřená smyčka) tak, že každý vrchol je navštíven přesně jednou, je znám jako hamiltonovský obvod.  Irský matematik 19. století William Rowan Hamilton zahájil systematické matematické studium takových grafů.

Historie teorie grafů a topologie spolu úzce souvisejí a obě oblasti sdílejí mnoho běžných problémů a technik. Euler odkazoval na svou práci na problému mostu Königsberg jako na příklad geometria situs - „geometrie pozice“ - zatímco vývoj topologických myšlenek v druhé polovině 19. století se stal známým jako analýza situs - „analýza polohy“. “ V roce 1750 objevil Euler polyhedrální formule V - E + F = 2 vztahující se k počtu vrcholů ( V ), hran ( E ) a ploch ( F)) polyhedronu (pevná látka, jako výše uvedený dodekahedron, jehož tváře jsou polygony). Vrcholy a hrany polyhedronu tvoří graf na jeho povrchu, a tento pojem vedl k úvahám o grafech na jiných povrchech, jako je torus (povrch pevného koblihy) a jak rozdělují povrch na diskovité plochy. Eulerova formule byla brzy zobecněna na povrchy jako V - E + F = 2 - 2 g , kde g označuje rod nebo počet „donutových otvorů“ povrchu ( viz vizEulerova charakteristika). Po zvážení plochy rozdělené na polygony vloženým grafem začali matematici studovat způsoby konstrukce povrchů a později obecnějších prostorů tím, že do sebe vložili polygony. To byl začátek oboru kombinatorické topologie, která se později díky práci francouzského matematika Henri Poincaré a dalších rozrostla na tzv. Algebraickou topologii.

Spojení mezi teorií grafů a topologií vedlo k podpole zvanému topologická teorie grafů. Důležitým problémem v této oblasti jsou rovinné grafy. Jedná se o grafy, které lze nakreslit jako tečkové a liniové diagramy v rovině (nebo rovnocenně na kouli) bez překročení hran s výjimkou vrcholů, kde se setkávají. Kompletní grafy se čtyřmi nebo méně vrcholy jsou rovinné, ale kompletní grafy s pěti vrcholy ( K 5) nebo více nejsou. Neplanární grafy nelze kreslit na rovině nebo na povrchu koule, aniž by se hrany protínaly mezi vrcholy. Používání diagramů teček a čar k znázornění grafů skutečně vyrostlo z chemie 19. století, kde vrcholy se znaménkem označovaly jednotlivé atomy a spojovací linie označovaly chemické vazby (se stupněm odpovídajícím valenci), ve kterých měla planarita důležité chemické důsledky. První použití, v tomto kontextu, slovního grafu je přičítáno Angličanovi 19. století Jamesovi Sylvesterovi, jednomu z několika matematiků, kteří mají zájem počítat speciální typy diagramů představujících molekuly.

  • K5 není rovinný graf, protože neexistuje žádný způsob, jak spojit každý vrchol s každým dalším vrcholem s hranami v rovině tak, aby se žádné hrany neprotínaly.
  • rovinný graf;  neplanární graf

Další třída grafů je sbírka kompletní bipartitní grafy K m , n , které se skládají z jednoduchých grafů, které mohou být rozděleny do dvou samostatných sad m a n vrcholy tak, že zde nejsou žádné hrany mezi vrcholy v každé sadě a každý vrchol v jedné sadě je hranou spojena s každým vrcholem ve druhé sadě. Stejně jako K 5 není bipartitní graf K 3, 3 rovinný, což vyvrací tvrzení anglického rekreačního problémisty Henryho Dudeneyho v roce 1913 k řešení problému „plyn-voda-elektřina“. V roce 1930 polský matematik Kazimierz Kuratowski prokázal, že jakýkoli neplanární graf musí obsahovat určitý typ kopieK 5 nebo K 3, 3 . Zatímco K 5 a K 3, 3 nemohou být zabudovány do koule, mohou být zabudovány do torusu. Problém vložení grafu se týká určení povrchů, do kterých může být graf vložen, a tím zobecňuje problém rovinnosti. Teprve na konci šedesátých let byl problém vkládání pro kompletní grafy K n vyřešen pro všechny n .

  • Bipartitní mapa, jako je K3, 3, sestává ze dvou sad bodů v dvourozměrné rovině, takže každý vrchol v jedné sadě (sada červených vrcholů) může být spojen s každým vrcholem v druhé sadě (množina modré vrcholy), aniž by se protínaly žádné cesty.
  • Dudeney puzzle Anglický rekreační problém Henry Dudeney prohlašoval, že má řešení problému, který on představoval v 1913 to vyžadovalo každý ze tří domů být spojen se třemi oddělenými pomůckami tak že žádné průchody inženýrských sítí se protínaly. Dudeneyovo řešení zahrnovalo vedení potrubí jedním z domů, což by se v teorii grafů nepovažovalo za platné řešení. V dvourozměrné rovině je kolekce šesti vrcholů (zde znázorněných jako vrcholy v domech a utilitách), které lze rozdělit na dvě zcela oddělené sady tří vrcholů (tj. Vrcholů ve třech domovech a vrcholů v tři obslužné programy) se označuje bipartitní graf K3, 3. Obě části těchto grafů nemohou být vzájemně propojeny v dvourozměrné rovině, aniž by protínaly některé cesty.

Dalším problémem topologické teorie grafů je problém barvení map. Tento problém je výsledkem známého problému čtyřbarevné mapy, který se ptá, zda země na každé mapě mohou být obarveny pouhými čtyřmi barvami tak, aby země, které sdílejí hranu, měly odlišné barvy. Na otázku, kterou původně požádal v 50. letech 20. století Francis Guthrie, tehdy student na University College London, má tento problém bohatou historii plnou nesprávných pokusů o jeho řešení. V ekvivalentní teoretické formě grafu lze tento problém překládat a ptát se, zda vrcholy rovinného grafu lze vždy obarvit pouhými čtyřmi barvami tak, že vrcholy spojené hranou mají různé barvy. Výsledek byl nakonec prokázán v roce 1976 pomocí počítačové kontroly téměř 2 000 speciálních konfigurací. Zajímavě,odpovídající barevný problém týkající se počtu barev požadovaných pro barevné mapy na plochách vyššího rodu byl úplně vyřešen před několika lety; například mapy na torusu mohou vyžadovat až sedm barev. Tato práce potvrdila, že vzorec anglického matematika Percy Heawood z roku 1890 správně uvádí tato čísla zbarvení pro všechny povrchy s výjimkou jednostranného povrchu známého jako Kleinova láhev, pro které bylo v roce 1934 stanoveno správné číslo zbarvení.Tato práce potvrdila, že vzorec anglického matematika Percy Heawood z roku 1890 správně uvádí tato čísla zbarvení pro všechny povrchy s výjimkou jednostranného povrchu známého jako Kleinova láhev, pro které bylo v roce 1934 stanoveno správné číslo zbarvení.Tato práce potvrdila, že vzorec anglického matematika Percy Heawood z roku 1890 správně uvádí tato čísla zbarvení pro všechny povrchy s výjimkou jednostranného povrchu známého jako Kleinova láhev, pro které bylo v roce 1934 stanoveno správné číslo zbarvení.

Mezi současné zájmy v teorii grafů patří problémy týkající se efektivních algoritmů pro nalezení optimálních cest (v závislosti na různých kritériích) v grafech. Dva dobře známé příklady jsou problém čínského pošťáka (nejkratší cesta, která navštíví každou hranu alespoň jednou), která byla vyřešena v 60. letech, a problém cestujícího prodavače (nejkratší cesta, která začíná a končí ve stejném vrcholu a navštěvuje každý přesně jednou), což stále přitahuje pozornost mnoha vědců díky jeho aplikacím ve směrování dat, produktů a lidí. Práce na těchto problémech souvisí s oblastí lineárního programování, které založil v polovině 20. století americký matematik George Dantzig.