Úvod

Hoci je teória grafov pomerne mladou vednou disciplínou, sú grafy veľmi dôležitou časťou informatiky. Mnoho problémov sa dá formálne vyjadriť a riešiť práve pomocou nich. Grafy sa hodia na reprezentáciu rôznych typov sietí, napríklad cestnej siete, počítačovej siete, sústavy vodovodov a podobne. Jednou z prvých prác z teórie grafov bola práca Leonharda Eulera o siedmych mostoch v Kráľovci (dnešný Kaliningrad). Zaoberal sa otázkou, či existuje taká trasa, ktorá prechádza cez každý z vtedajších siedmych mostov mesta práve raz a vracia sa do začiatočného bodu. Euler sformuloval problém ako graf a dokázal, že takáto trasa existuje iba ak každý vrchol grafu má párny počet hrán (čo nebol prípad daného mesta).

^ TOP

Spracované algoritmy

Zo všetkých problémov a algoritmov teórie grafov tvoria reprezentatívnu vzorku nasledujúce algoritmy.

• Prehľadávanie do hĺbky
• Topologické triedenie
• Najlacnejšia kostra
• Najkratšia cesta

^ TOP

Rôzne iné algoritmy a problémy

Enumeration

Enumeration (vymenovanie) je obor teórie grafov, ktorý sa zaoberá nasledovnou otázkou: „Koľko neizomorfných grafov má danú vlastnosť?“

Podgrafy a indukované podgrafy

Často sa dá zistiť niektorá vlastnosť grafu len tak, že sa skontroluje, či danú vlastnosť majú všetku jeho podgrafy. Zisťovať však maximálne podgrafy pre určitý problém je zväčša NP-úplný problém.
 Nájsť kliku – najväčší kompletný podgraf.
 Zisťovanie planarity grafu.

Farbenie grafu

Rôzne problémy týkajúce sa farbenia grafov.
 Problém štyroch farieb
 Úplné farbenie(unsolved)
 The list coloring conjecture (unsolved)

Problémy hľadania cesty

 Hamiltonovská cesta
 Najlacnejšia kostra grafu
 Problém čínskeho poštára
 Sedem mostov mesta Kráľovec
 Problém najkratšej cesty
 Problém obchodného cestujúceho

Toky v sieťach

 Úloha o maximálnom toku

Problémy pokrytia

 Vrcholové pokrytie grafu

^ TOP