Teorie grafů

Teorie grafů (méně často také graf teorie ) je odvětví diskrétní matematiky a teoretické informatiky . Předmětem posouzení v teorii grafů jsou grafy ( sad z uzlů a hran ), jejich vlastnosti a jejich vztah k sobě navzájem.

Grafy jsou matematické modely síťových struktur v přírodě a technologii (jako jsou sociální struktury , silniční sítě , počítačové sítě , elektrické obvody , napájecí sítě nebo chemické molekuly ). V teorii grafů se zkoumá pouze samotná abstraktní struktura sítě. Typ, poloha a povaha uzlů a hran nejsou brány v úvahu. Zůstává však mnoho obecně použitelných vlastností grafů, které již lze zkoumat na této úrovni abstrakce a které lze nalézt v obecně platných výrokech ( teorémách teorie grafů ). Příkladem toho je lema handshake , podle které je součet uzlových stupňů v grafu vždy sudý (na sousedním obrázku čtrnáct).

Protože na jedné straně lze mnoho algoritmických problémů vysledovat zpět do grafů a na druhé straně řešení grafově-teoretických problémů je často založeno na algoritmech , má teorie grafů velký význam také v informatice , zejména v teorii složitosti . Součástí teorie sítí je také studium grafů . Grafy jsou reprezentovány zejména v datové struktury matice sousednosti , incidenční matice nebo seznamu přilehlosti .

Dějiny

Předchůdcem starověku, který byl nezávislý na teorii grafů, byla metoda Dihairesis , která byla použita k hierarchizaci zoologických, muzikologických a dalších termínů (pouze částečně graficky). To dalo vzniknout rané systematice v různých oblastech znalostí.

Počátky teorie grafů sahají do roku 1736. V té době Leonhard Euler publikoval řešení problému mostu Königsberg . Otázkou bylo, zda existuje prohlídka města Königsberg (Prusko), které využívá každý ze sedmi mostů přes řeku Pregel přesně jednou. Euler dokázal specifikovat nezbytnou podmínku, kterou nebylo možné pro tento problém splnit, a tak popřít existenci takové prohlídky.

V roce 1852 si matematik a botanik Francis Gutherie všiml, že k vybarvení mapy stačí čtyři barvy, takže dvě země, které sousedí, jsou vždy zbarveny odlišně. Mnoho matematiků se tímto problémem zabarvení zabývalo . Avšak teprve v roce 1976 bylo možné čtyřbarevnou větu dokázat pomocí počítače. Teprve v roce 1997 představili Neil Robertson , Daniel Sanders, Paul Seymour a Robin Thomas nové důkazy.

Termín graf poprvé použil v roce 1878 matematik James Joseph Sylvester na základě grafických zápisů chemických struktur . Dalším zakladatelem rané teorie grafů je Arthur Cayley . Jednou z prvních aplikací byly vzorce chemické konstituce . (Viz také chemická teorie grafů a literatura : Bonchev / Rouvray, 1990). První učebnici teorie grafů vydal Dénes Kőnig v roce 1936 .

Ve druhé polovině 20. století William Thomas Tutte významně pracoval na dalším vývoji teorie grafů a silně formoval toto odvětví matematiky.

Podsekce teorie grafů

Podoblasti teorie grafů jsou:

• Algoritmická teorie grafů : Tato podoblast se zabývá algoritmy použitelnými pro grafy (seznam grafových algoritmů ) .
• Chemická teorie grafů : Chemická teorie grafů byla jednou z prvních aplikací strukturálních znalostí a aplikuje je na chemické molekulární struktury.
• Extrémní teorie grafů : Extrémní teorie grafů zkoumá, které grafy dané třídy maximalizují nebo minimalizují konkrétní parametr grafu.
• Teorie geometrických grafů a teorie topologických grafů : Tyto podoblasti vkládají grafy do rovin a dalších geometrických objektů.
• Výzkum sítě : Při výzkumu sítě jsou empiricky zkoumány složité sítě . Najde uplatnění v oborech, jako je biologie , ekonomie a sociologie .
• Pravděpodobnostní teorie grafů : Pomocí náhodného grafu lze prokázat vlastnosti grafů jakékoli velikosti.
• Teorie spektrálních grafů (také algebraická teorie grafů): Teorie spektrálních grafů zkoumá grafy na základě jejich matic sousednosti a Laplaceových matic prostřednictvím analýzy vlastních čísel , vlastních vektorů a charakteristických polynomů . Neusměrněné grafy mají symetrické matice sousednosti, a proto skutečná vlastní čísla . Všechna vlastní čísla společně se nazývají spektrum grafu . Zatímco matice sousedství závisí na třídění uzlů, spektrum je na ní nezávislé.

Zobrazený objekt

V teorii grafů označuje graf množinu uzlů (nazývaných také vrcholy nebo body) společně se sadou hran. Okraj je sada přesně dvou uzlů. Označuje, zda dva uzly spolu souvisejí, nebo zda jsou spojeny v grafickém znázornění grafu. Dva uzly, které jsou spojeny hranou, se nazývají sousední nebo sousední . Pokud jsou hrany dány uspořádanými páry uzlů místo množin , hovoří se o orientovaných grafech . V tomto případě se rozlišuje mezi hranou ( a , b ) - jako hranou z uzlu a do uzlu b - a hranou ( b , a ) - jako hranou z uzlu b do uzlu a . Uzly a hrany mohou mít také barvy (formálně s přirozenými čísly ) nebo váhy (tj. Racionální nebo reálná čísla ). Jeden pak mluví o grafech uzlových nebo okrajových barev nebo vážených .

Složitější typy grafů jsou:

• Multigraf ve kterém je sada okraj multiset je
• Hypergrafy , ve kterých hrana představuje libovolně velkou sadu uzlů (jeden také mluví v tomto případě hyper-hran )
• Petriho sítě se dvěma typy uzlů

Pokud je množina uzlů konečná, hovoří se o konečných grafech , jinak o nekonečných grafech .

Vlastnosti grafu

Grafy mohou mít různé vlastnosti. Stejně tak graf

• připojeno (obecně připojeno k ),
• bipartitní (obvykle k-partit ),
• rovinný ,
• být Eulerian nebo Hamiltonian .

Může existence zvláštních podgrafy nebo mladistvých jsou požádáni, nebo jsou zkoumány určité parametry, jako je počet uzlů , počet hran , minimální stupeň , v maximální míře , šířka pasu , o průměru , uzel rychlost připojení , hrany počet připojení , oblouku číslo spojení , chromatické číslo , číslo vrcholového krytu ( faktor ), číslo nezávislosti ( číslo stability ) nebo číslo kliky . Dva grafy mohou být navzájem izomorfní (strukturálně stejné) nebo automorfní .

Různé vlastnosti mohou navzájem souviset. Zkoumání vztahů je úkolem teorie grafů. Například číslo připojení uzlu nikdy není větší než číslo připojení hrany, což zase nikdy není větší než minimální stupeň uvažovaného grafu. V plochých grafech je počet barev vždy menší než pět. Toto tvrzení je také známé jako čtyřbarevná věta .

Některé z uvedených vlastností grafu lze určit algoritmicky relativně rychle, například pokud se úsilí zvýší maximálně s druhou mocninou velikosti grafu. Další vlastnosti prakticky aplikovaných grafů nelze během životnosti dnešních počítačů přesně určit. V těchto případech však může použití heuristických metod vést k rozumnému přibližnému řešení.

Třídy grafů

V zásadě jsou grafy rozděleny na směrované a neorientované .

Vzhledem k kontextu se rozlišuje:

• acyklické grafy: cesta (nebo cesta) , les , strom , DAG (směrovaný acyklický graf)
• cyklické grafy, například: cyklus , kruh , úplný graf .

Vzhledem k přítomnosti určitých vlastností lze rozlišit další třídy grafů, například

• Bipartitní grafy ,
• Rovinné grafy ,
• Pravidelné grafy ,
• Akordové grafy ,
• Perfektní grafy ,
• Magický graf .

Pokud je uzel zvláště rozlišován, nazývá se kořenový nebo kořenový graf . Zakořeněné stromy mají mimo jiné zvláštní význam jako stromová struktura .

Problémy

Níže jsou uvedeny hlavní problémy a výsledky teorie grafů:

zbarvení

Známý problém se ptá, kolik barev je třeba k vybarvení zemí na mapě, aby žádné dvě sousední země neměly stejnou barvu. Sousední vztah zemí lze vyjádřit jako rovinný graf. Problém lze nyní modelovat jako problém zabarvení uzlu. Podle sady čtyř barev potřebujete maximálně čtyři různé barvy. Podle současného stavu znalostí není možné efektivně rozhodnout, zda lze graf obecně obarvit méně barvami. Problém je považován za jeden z nejobtížnějších problémů ve třídě NP- úplných problémů. Za předpokladu, že P ≠ NP , není efektivně možné ani řešení, které se blíží konstantnímu faktoru.

Problémy s vyhledáváním

Důležitou aplikací algoritmické teorie grafů je hledání nejkratší trasy mezi dvěma místy v silniční síti. Tento problém lze modelovat jako grafový problém. K tomu je silniční síť abstrahována zahrnutím všech míst jako uzlů a přidáním okraje, pokud existuje spojení mezi těmito místy. Okraje tohoto grafu jsou váženy v závislosti na aplikaci , například s délkou přidruženého připojení. S pomocí algoritmu pro hledání nejkratších cest (například pomocí Dijkstrova algoritmu ) lze efektivně najít nejkratší spojení. (viz také: Kategorie: Algoritmy pro vyhledávání grafů )

Pochůznost grafu

Z hlediska algoritmů je mnohem obtížnější určit nejkratší zpáteční cestu (viz problém obchodního cestujícího ), ve které musí být všechna místa v silniční síti navštívena přesně jednou. Vzhledem k tomu, že počet možných zpátečních letů se faktoriálně zvyšuje s počtem míst, je naivní algoritmus zkoušení všech zpátečních cest a výběru nejkratší možné pouze pro praktické aplikace pro velmi malé sítě. Pro tento problém existuje řada aproximačních algoritmů , které naleznou dobrý, ale ne optimální zpáteční let. Christofidova heuristika přináší zpáteční cestu, která je maximálně 1,5krát delší než ta nejlepší možná. Za předpokladu, že P ≠ NP ( viz problém P-NP ), neexistuje efektivní algoritmus pro stanovení optimálního řešení, protože tento problém je NP -hard .

Problém Königsbergova mostu se ptá na existenci Eulerova kruhu . Zatímco problém Eulerovy kružnice lze vyřešit v lineárním čase pomocí Hierholzerovy metody , najít Hamiltonovu kružnici (uzavřená cesta v grafu, který obsahuje každý uzel právě jednou) je NP-obtížné. Problém pošťáka žádá o nejkratší cyklus, který prochází všemi hranami alespoň jednou.

kontext

V souvislosti s připojením je dotázáno, zda nebo přes kolik cest lze dosáhnout dvou uzlů od sebe navzájem . To hraje roli například při hodnocení napájecích sítí s ohledem na kritické (části ohrožené selháním).

Clique problém

Otázka existence (možná maximálních) klik hledá ty části grafu, které jsou navzájem zcela spojeny hranami.

Překrytí uzlu

Problém pokrytí uzlů hledá podmnožinu uzlů v grafu, který obsahuje alespoň jeden koncový uzel z každé hrany.

Řeky a škrty v sítích

S otázkou maximálního průtoku lze hodnotit napájecí sítě z hlediska jejich kapacity.

Vhodný

Problémy se shodováním, které lze vysledovat zpět k problémům s tokem, se ptají na optimální výběr hran, aby na uzel nenarazily žádné dvě hrany. To lze použít k řešení problémů s přidělováním , například použití zdrojů, jako je obsazenost místnosti nebo stroje.

Další problémy s grafy

Mezi další problémy s grafy patří

• nalezení stabilní sady ,
• graf výkres (to existuje software pro vizualizaci grafů: yEd , Graphviz ) a
• transformace grafů pomocí pravidel nahrazujících systémy založené na pravidlech . Systémy nahrazování grafů, které se používají k výčtu všech grafů v jazyce grafu, se také nazývají gramatiky grafů

Viz také

literatura

• Martin Aigner: Teorie grafů: vývoj od čtyřbarevného problému. 1984 (269 stran).
• Daniel Bonchev, DH Rouvray: Teorie chemického grafu: Úvod a základy. Abacus, New York NY 1990/1991, ISBN 0-85626-454-7 .
• J. Sedláček: Úvod do teorie grafů. BG Teubner, Lipsko 1968, 1972.
• M. Nitzsche: Grafy pro začátečníky (Kolem domu svatého Mikuláše). Vieweg, Wiesbaden 2004, ISBN 3-528-03215-4 .
• R. Diestel: Teorie grafů. 3. Vydání. Springer, Heidelberg 2005, ISBN 3-540-67656-2 ( online stažení ).
• Peter Gritzmann, René Brandenberg: Tajemství nejkratší trasy. Matematické dobrodružství . 2. vydání. Springer, Berlin / Heidelberg 2003, ISBN 3-540-00045-3 .
• Peter Tittmann: Teorie grafů. Úvod orientovaný na aplikaci. 3. Vydání. Hanser, Mnichov 2019, ISBN 978-3-446-46052-2 .

webové odkazy

• Katalog odkazů na teorii grafů na curlie.org (dříve DMOZ )

Individuální důkazy

1. ^ Peter Tittmann: Teorie grafů. Úvod orientovaný na aplikaci . 3. aktualizované vydání. Mnichov, ISBN 978-3-446-46052-2 , str. 1 . 
2. ^ Peter Tittmann: Teorie grafů. Úvod orientovaný na aplikaci . 3. aktualizované vydání. Mnichov, ISBN 978-3-446-46052-2 , str. 76 . 
3. ^ Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas: The Four-Color Theorem . In: Journal of Combinatorial teorie, Series B . páska 70 , č. 1 , 1997, ISSN  0095-8956 , str. 2-44 . 
4. ^ James Joseph Sylvester: Chemie a algebra. In: Příroda. Svazek 17, 1878, s. 284.
5. ^ Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson: Teorie grafů 1736-1936 . Oxford University Press, 1999, ISBN 0-19-853916-9 . 
6. ^ Arthur Cayley: Chemické grafy . In: Filozofický časopis . Svazek 47, 1874, str. 444-446.
7. ↑ Dénes Kőnig: Teorie konečných a nekonečných grafů: Kombinatorická topologie liniových komplexů. Academic Publishing Company, Leipzig 1936.