Grafy - cesty, nej kratší cesty
► Jaký je rozdíl mezi cestou a jednoduchou cestou v grafu?
► Je pojem „nejkratší cesta z vrcholu s do vrcholu ŕ" totožný s pojmem „nejkratší jednoduchá cesta z vrcholu s do vrcholu ŕ"?
Grafy - cesty, nej kratší cesty
► Jaký je rozdíl mezi cestou a jednoduchou cestou v grafu?
► Je pojem „nejkratší cesta z vrcholu s do vrcholu ŕ" totožný s pojmem „nejkratší jednoduchá cesta z vrcholu s do vrcholu ŕ"?
► Co kdyby nás místo nejkratší zajímala nejdelší (jednoduchá) cesta?
rafy - nej kratší cesty
Bludiště
r4
► Jak najít (nejkratší) cestu bludištěm?
Grafy - nej kratší cesty
Bludiště
r±r-r-
Jak najít (nejkratší) cestu bludištěm?
► Jak najít cestu bludištěm, máme-li povoleno bourat zdi, ale chceme jich zbourat co nejméně?
Grafy - nejkratší cesty
Strom s vracením je graf, který vznikne z kořenového stromu přidáním hran z listů přímo do kořene. Mějme nezáporně ohodnocený strom s vracením a s dvěma vybranými vrcholy s a t. Vymyslete co nejrychlejší algoritmus, který najde nejkratší cestu z s do t.
rafy - nejspolehlivější cesty
Nejspolehlivější cesta
Máme síť komunikačních uzlů reprezentovanou jako orientovaný graf. Každá hrana má přiřazenu spolehlivost, tj. racionální číslo mezi 0 a 1, které reprezentuje pravděpodobnost, že se zpráva poslaná po dané hraně neztratí. Máme vybraný vrchol s a chceme zjistit, jaká je nejspolehlivější cesta z s do všech ostatních uzlů.
Grafy - minimální kostra
Mějme následující algoritmus pro řešení problému minimální kostry: l function MST(G = (V, E))
2
3
4
5
6
7
8
7^0
for e G E do
T ^ T U {e} if 7 obsahuje cyklus then
ŕ     největší hrana na cyklu v T
T^T\{f}
return T
► Je tento algoritmus korektní?
► Pokud ano, najděte invariant cyklu for a dokažte jej
► Pokud ne, najděte protipříklad.
fy - záporné cykly
K zamyšlení
► Jak detekovat existenci záporného cyklu v grafu?
► Jak vypsat nějaký záporný cyklus v grafu?
► Jak vypsat všechny vrcholy, které se nacházejí na záporných cyklech grafu?