Grafy (obsah)

Bellman-Fordův algoritmus slouží k nalezení nejkratších cest ze zadaného uzlu do všech ostatních uzlů grafu, který neobsahuje cyklus záporné délky. V případě, že jej graf obsahuje, je algorimus schopen jeho detekce. Algoritmus byl vymyšlen americkými matematiky Richardem Bellmanem a Lesterem Fordem. Princip Základem Bellman-Fordova algoritmu je operace relaxace. Do této operace vstupují dva uzly a hrana, která mezi nimi vede. Pokud je vzdálen...

Borůvkův algoritmus Borůvkův algoritmus slouží k nalezení minimální kostry grafu (kostry takové, že je součet vah jejích hran minimální). Byl vymyšlen českým matematikem Otakarem Borůvkou za účelem nalezení efektivního trasování elektrické sítě na Moravě. Algoritmus byl později několikrát znovuobjeven (mezi jinými M. Sollinem), proto se o něm lze dočíst také jako o Sollinově algoritmu. Princip Borův...

Eulerův graf Cycle finding je algoritmus s asymptotickou složitostí , jenž slouží k nalezení Eulerovského tahu v zadaném grafu. Eulerovský tah je tah, který projde každou hranu právě jednou. Aby mohl graf obsahovat Eulerovský tah, tak musí být souvislý a zároveň musí mít buď všechny vrcholy sudého stupně (algoritmus nalezne uzavřený tah) nebo právě 2 vrcholy lichého stupně (algoritmus nalezne otev...

Dijkstrův algoritmus je nejrychlejší známý algoritmus pro nalezení všech nejkratších cest ze zadaného uzlu do ostatních uzlů grafu, který neobsahuje hrany záporné délky. Algoritmus byl vymyšlen nizozemským informatikem Edsgerem Dijkstrou v roce 1959. Dijkstrův algoritmus po zpracování dvou uzlů Princip Na Dijkstrův algoritmus lze pohlížet jako na zobecněné prohledávání grafu do šířky, při kterém se...

Chu-Liu-Edmondsův algoritmus (Chu-Liu-Edmond's algorithm), byl nezávisle objeven v roce 1965 (Chu a Liu), 1967 (Edmonds) a 1971 (Bock). Tento algoritmus slouží k nalezení minimální (maximální) kostry orientovaného grafu, což je výrazně složitější problém, než je hledání kostry neorientovaného grafu, pro které existuje řada jednoduchých a efektivních algoritmů - například Borůvkův, Jarník-Primův nebo Kruskalův algoritmus. Princip Chu-Liu-Edmonds...

Floyd-Warshallův algoritmus (Floydův algoritmus) slouží k nalezení nejkratších cest mezi všemi dvojicemi uzlů grafu, který neobsahuje cykly záporné délky. Jeho hlavní výhodou je jeho implementační jednoduchost. Princip Floyd-Warshallův algoritmus má na vstupu matici délek, říkejme jí . Pokud mezi dvěma uzly vede hrana délky l, tak tato matice obsahuje na indexu právě tuto hodnotu. Na diagonále má tato matice samé nuly a na ostatních indexech, k...

Graf K5 Grafem nazýváme uspořádanou trojici uzlů, hran a incidencí. Zobrazení incidence přiřazuje dvojici uzlů právě jednu hranu. Neorientovaný graf V případě, kdy incidence přiřazuje hraně neuspořádanou dvojici uzlů, nazýváme graf neorientovaným grafem. Neorientovaný graf, který neobsahuje rovnoběžné hrany, nazýváme prostým grafem, v opačném případě multigrafem. V případě neexistence smyček (hra...

Jarník-Primův algoritmus Jarník-Primův algoritmus (Jarníkův algoritmus, Primův algorimus, Prim-Jarníkův algorimus, DJP algorithm) slouží k určení minimální kostry grafu (kostra taková, že součet vah jejíchž hran je minimální). Tento algoritmus byl vynalezen v roce 1930 českým matematikem Vojtěchem Jarníkem a v roce 1957 znovu nezávisle objeven americkým matematikem Robertem Primem. Algorimus byl opět ...

Kruskalův algoritmus Kruskalův algoritmus slouží k nalezení minimální kostry grafu (kostry takové, že součet vah jejích hran je minimální). Algoritmus byl poprvé publikován v roce 1956 Josephem Kruskalem. Princip Kruskalův algoritmus nejprve setřídí hrany dle jejich váhy (od nejmenší) a následně přidává hrany do grafu takovým způsobem, aby nevznikl žádný cyklus (tj. procedura terminuje po přidán...

Nepostradatelný most mezi uzly 3 a 4 Hledání nepostradatelných mostů je častou úlohou teorie grafů, jejímž cílem je nalézt takové hrany, po jejichž odebrání by se daný neorientovaný graf rozpadl na více částí. Pokud tuto úlohu přeformulujeme, tak hledáme takové hrany, které nejsou součástí žádného cyklu (ke všem uzlům uvnitř cyklu vede přinejmenším jedna další alternativní cesta). Řešení Řešením této úloh...

Graf obsahující 3 komponenty souvislosti Komponenta souvislosti grafu je taková maximální podmnožina uzlů grafu, pro kterou platí, že mezi každými dvěma uzly vede sled. Princip Algoritmus pro zjištění počtu komponent je jednoduchou modifikací prohledávání do hloubky (DFS). Algoritmus nejprve označí veškeré uzly jako nenavštívené (FRESH) a uloží je do fronty. Poté pustí prohledávání do hloubky z prvního uz...

Otevírání a uzavírání uzlů při procházení grafu do hloubky Prohledávání do hloubky (Depth-first search, DFS) je algoritmus určený k procházení grafu, který má široké uplatnění - jeho principů se využívá při zjišťování počtu komponent, topologického uspořádání nebo detekci cyklů daného grafu. Princip Algoritmus zvolí libovolný uzel a označí jej jako otevřený, zpracuje jej a zavolá sám sebe na všechny do...

Prohledávání do šířky - čísla označují vlnu, ve které je uzel zpracován Prohledávání do šířky (Breadth-first search, BFS) je jedním ze základních grafových algoritmů, který slouží k průchodu daného grafu. Jeho principy jsou základem pro další algoritmy, jako je například Jarník-Primův algoritmus nebo Dijkstrův algoritmus. Princip Při prohledávání do šířky začneme procházet graf z libovolného uzlu. Tento ...

Tarjanův algoritmus (Tarjan's algorithm) je grafový algoritmus sloužící k vyhledávání silných komponent orientovaného grafu. Silná komponenta je maximální množina uzlů orientovaného grafu taková, že mezi každými dvěma uzly existuje sled. Princip Tarjanův algoritmus vychází z prohledávání do hloubky. Vrcholy se při prohledávání indexují dle pořadí svého nalezení. Při návratu z rekurze se každému vrcholu přiřadí uzel s nejnižším indexem na jaký l...

Topologické uspořádání Topologické uspořádání uzlů grafu je taková posloupnost uzlů ui, uj, že pro každou hranu mezi těmito uzly platí, že i . Pokud si to představíme graficky, tak to znamená, že máme graf nakreslený takovým způsobem, že všechny orientované hrany směřují jedním směrem. Podmínkou z tohoto vycházející je acykličnost daného grafu. Topologické uspořádání se používá často pro plánování na sobě...