Základní pojmy

Definice (Graf)

• Grafem (neorientovaným grafem) rozumíme dvojici \(G=(V,E)\), kde \(V\) je neprázdná množina a \(E\) je podmnožina množiny všech dvouprvkových podmnožiny množiny \(G\). Prvky množiny \(V\) nazýváme vrcholy, prvky množiny \(E\) nazýváme hrany.

• Je-li \(e\) hrana grafu, potom její prvky nazýváme krajní body hrany.

• Orientovaný graf definujeme analogicky, pouze navíc ke každé hraně dodáme orientaci -- jeden z vrcholů prohlásíme za počáteční a jeden z vrcholů za koncový.

• Graf může být hranově nebo vrcholově ohodnocený -- každé hraně nebo každému vrcholu může být přiřazeno reálné číslo.

Neorientovaný, hranově ohodnocený graf

Základní pojmy (cesta, ...)

Definice (cestování v grafech)

• Posloupnost hran, které na sebe navazují, se nazývá sled.

• Sled, ve kterém se neopakuje žádná hrana se nazývá tah.

• Tah, ve kterém se naopakuje žádný vrchol se nazývá cesta.

• Délkou sledu (tahu, cesty) rozumíme bud počet hran (v grafech bez hranového ohodnocení), nebo součet hranových ohodnocení všech hran v tomto sledu (tahu, cestě).

• Graf, ve kterém mezi každými dvěma vrcholy existuje cesta, se nazývá souvislý.

Sled (který není tahem) a tah (který není cestou) v souvislém grafu

Nejkratší cesta (shortest path problem )

Vstup: orientovaný a neorientovaný graf s nezápornými ohodnoceními hran, výchozí bod, cílový bod

Výstup: délka nejkratší cesty mezi výchozím a cílovým bodem

Aplikace: nejkratší cesta v dopravním slova smyslu, nejkratší cesta ve smyslu výrobního procesu,

Nejkratší cesta

Algoritmus pro nalezení nejkratší cesty (Dijkstrův)

Výstupem tohoto algoritmu je délka nejkratší cesty z výchozího bodu do všech ostatních bodů grafu.

Mějme graf \(G=(V,E)\), v němž hledáme nejkratší cestu.

Pro každý vrchol vrchol \(v\) z \(V\) si budeme značit hodnotu \(d[v]\) pamatuje délku dosud nalezené nejkratší cesty, která sem vede z výchozího bodu. Na začátku mají všechny vrcholy v hodnotu \(d[v]=\infty\), kromě počátečního vrcholu \(s\), který má \(d[s]=0\). Nekonečno symbolizuje, že neznáme cestu k vrcholu.

Budme uvažovat dvě množiny \(Z\) a \(N\) -- zpracovaných a nezpracovaných vrcholů. V každém kroku

• Vybereme z množiny \(N\) vrchol \(v\) s nejmenší vzdáleností od počátku \(d[v]\).

• Tento vrchol přesuneme do množiny \(Z\) a podíváme se, jestli se vzdálenost jeho nezpracovaných sousedů nedá vylepšit, pokud uvažujeme cestu přes tento vrchol. Vrcholům \(u\), kterým se vzdálenost dá vylepšit cestou přes \(v\) opravíme hodnotu \(d[u]\).

• Opakujeme předchozí dva kroky, dokud množina nezpracovaných vrcholů není prázdná

Příklad

Základní pojmy (nakresli jedním tahem, ...)

Definice

• Sled, který projde právě jednou všechny hrany grafu se nazývá eulerovský.

• Graf, ve kterém existuje uzavřený eulerovský sled se nazývá eulerovský graf.

• Stupněm vrcholu rozumíme počet hran, které do (z) tohoto vrcholu vedou.

Úloha zjistit zda je možno graf "nakreslit jedním uzavřeným tahem" je vlastně tedy úloha na to zjistit, zda graf je nebo není eulerovský. Následující věta řeší možnost kreslení uzavřeným i otevřeným tahem.

Věta (charakterizace grafů, které lze nakreslit jedním tahem): Graf je možno nakreslit jedním tahem právě tehdy když je souvislý a všechny vrcholy jsou sudého stupně, nebo má právě dva vrcholy lichého stupně.

Jsou-li v grafu dva vrcholy lichého stupně, potom tah začíná v jednom z těchto stupňů a končí ve druhém.

Stupně vrcholů v grafu, který je možno nakreslit jedním tahem

Základní pojmy (strom, kostra, ...)

Definice (lesnické pojmy v grafech)

• Tah, ve kterém splývá počáteční a koncový bod se nazývá cyklus (v orientovaných grafech) nebo kružnice (v neorientovaných grafech).

• Graf, který neobsahuje kružnici se nazývá les. Souvislý les (tj. souvislý graf, který neobsahuje križnici) se nazývá strom.

• Je-li \(G=(V,E)\) graf a jsou-li \(V'\) a \(E'\) podmnožiny množin \(V\) a \(E\) takové, že \(G'=(V', E')\) je grafem, nazývá se \(G'\) podgrafem grafu \(G\). Je-li \(V'=V\) (podgraf obsahuje všechny vrcholy), nazývá se \(G'\) faktorem grafu \(G\).

• Faktor, který je stromem se nazývá kostra.

Kostra grafu je tedy podgraf, který obsahuje všechny vrcholy a takové hrany, aby výsledný podgraf byl souvislý a neobsahoval kružnice. Hran tedy nesmí být ani příliš mnoho (objevily by se kružnice) ani málo (graf by nebyl souvislý).

Věta o počtu hran ve stromu: Počet hran stromu v neorientovaném grafu je o jednu nižší než počet vrcholů.

Graf který není stromem, kružnice a kostra v tomto grafu

Minimální kostra (minimum spanning tree)

Vstup: Souvislý graf s hranovými ohodnoceními.

Výstup: minimální kostra (kostra, s nejmenším součtem hranových ohodnocení).

Aplikace: minimalizuje celkové náklady na propojování míst (elektrickou sítí, počítačovou sítí, optimální postup při prohrnování sněhu mezi městy, ...)

Modifikace (Steiner tree problem): minimalizujeme náklady na propojení všech vesnic elektřinou, dráty se mohou sbíhat nebo rozpojovat i mimo vesnice -- velmi komplikovaný problém!

Postup (Kruskal):

• začneme od podgrafu který nemá žádnou hranu a má všechny vrcholy

• hrany uspořádáme podle velikosti do neklesající posloupnosti

• postupně hrany odhazujeme (pokud by se přidáním do grafu uzavřela kružnice) nebo přidáváme do grafu (v opačném případě)

• algoritmus končí v konečném čase, ale pro velké grafy je při zkušebním přidání každé hrany nutné běh doplnit algoritmem, který zjistí, zda v grafu se v grafu objeví cyklus

Příklad

Kritická cesta (CPM, Critical path method)

Projekt z tabulky zakreslený do grafu

Algoritmus CPM

Postup:

• Vrcholy značí fáze projektu, tj. začátek nebo konec určité činnosti.

• Každý vrchol označíme časem \(t_{\min}\) (nejdříve možný termín, tj. čas, kdy se nejdříve může projekt dostat do tohoto stavu) a \(t_{\max}\) (nejpozdějí přípustný termín, tj. čas, kdy nejpozději musí projekt dospět do tohoto stavu, pokud nemá dojít k prodloužení doby trvání celého projektu).

• Algoritmus má dvě části. V první části hledáme \(t_{\min}\) všech vrcholů. Prvnímu vrcholu přiřadíme \(t_{\min}=0\). Pokud do vrcholu \(v\) vedou pouze hrany z vrcholů se známým \(t_{\min}\), určíme \(t_{\min}\) vrcholu \(v\) jako maximum z čísel, která získáme jako součet hranového ohodnocení hrany mířící do \(v\) a \(t_{\min}\) počátečního bodu této hrany. Pokud je projekt smysluplně navržen, jsme takto schopni určit \(t_{\min}\) všech vrcholů.

• Poslednímu vrcholu nastavíme \(t_{\max}=t_{\min}\). Pokud z vrcholu \(v\) vedou pouze hrany do vrcholů se známým \(t_{\max}\), určíme \(t_{\max}\) vrcholu \(v\) jako minimum z čísel, která získáme jako rozdíl \(t_{\max}\) koncového bodu hrany a hranového ohodnocení hrany, přičemž uvažujeme všechny hrany vycházející z \(v\).

• Vrcholy, pro které je \(t_{\min}=t_{\max}\) jsou vrcholy, v nichž nesmí nastat zpoždění. Hrany spojující tyto vrcholy tvoří kritickou cestu. Činnosti odpovídající těmto hranám se nesmí zpozdit.

Příklad