Teorie grafů

Graf

Teorie grafů zkoumá vlastnosti struktur, zvaných grafy. Ty jsou tvořeny vrcholy, které jsou vzájemně spojené hranami. Znázorňuje se obvykle jako množina bodů spojených čarami. Formálně je graf uspořádanou dvojicí množiny vrcholů V a množiny hran E:

Pomocí grafů lze reprezentovat struktury a úlohy z nejrůznějších oborů. Taktéž mnoho problémů praktického života může být formulováno jako úloha teorie grafů - kupříkladu struktura vzájemného propojení článků Wikipedie. Jednotlivé články jsou vrcholy grafu a odkaz z článku A na článek B je orientovanou hranou mezi vrcholy A a B.

Struktura grafu může být rozšířena o ohodnocení hran (také označováno jako váha; může reprezentovat délku, náklady na přesun, průchodnost apod.) nebo vrcholu. Výsledkem je model reálné sítě. Takové modely se používají pro analýzu dopravy nebo počítačových sítí (jako např. internetu).

[editovat] Historie

Tradičně se za zakladatele teorie grafů považuje Leonhard Euler, který roku 1736 řešil úlohu, jak projít přes sedm mostů v Königsbergu (každý z nich právě jednou) a vrátit se do výchozího místa. To v moderní teorii odpovídá pojmu eulerovský graf.

V roce 1845 publikoval Gustav Kirchhoff zákony, které platí v elektrických obvodech a slouží k výpočtu napětí a proudu v jednotlivých větvích obvodu. V teorii grafů našly své uplatnění při studiu tzv. toků v sítích.

V roce 1852 předložil Francis Guthrie takzvaný problém čtyř barev - tedy otázku, zda je možné obarvit libovolnou mapu pomocí nejvýše čtyř barev tak, aby každé dvě sousední země (které mají společnou hranici delší než jediný bod) měly odlišnou barvu. Byl vyřešen až o více než sto let později, přičemž pro jeho řešení bylo zavedeno mnoho zásadních konceptů teorie grafů (viz rovinný graf).

[editovat] Úlohy

Velké množství úloh z teorie grafů je NP-úplných, mezi nimi např.:

• hledání největšího úplného podgrafu – tzv. problém kliky,
• hledání největší nezávislé množiny,
• problém obchodního cestujícího

Z dalších je to například

• problém čtyř barev,
• hledání minimální kostry grafu.

[editovat] Externí odkazy

• Java applety demonstrující některé algoritmy z teorie grafů
• Teorie grafů - Bc. práce z MFF UK zabývající se historií teorie grafů a úvodem, obsahuje základní definice, vybrané problémy a algoritmy včetně animací a kódů v Pascalu

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.