10 - Orientované grafy
pátek 13. května 2016
9:57
Orientované grafy (orientované cesty a kružnice, souvislost a silná souvislost, turnaj, eulerovské a hamiltonovské grafy, Dijkstrův a Floyd-Warshallův algoritmus pro hledání cesty minimální délky).
[link]
Orientovaný graf
Pojmem orientovaný graf se v teorii grafů označuje takový graf, jehož hrany jsou uspořádané dvojice. Naproti tomu hrany neorientovaného grafu jsou (dvouprvkové) množiny. Hrany orientovaného grafu mají tedy pevně danou orientaci. Tudíž výrazy (x, y) a (y, x) označují různé hrany. Hrana (x, x) se nazývásmyčka.
V informatice se orientované grafy často používají například pro znázornění konečného automatu. Vrcholy odpovídají stavům automatu, hrany pak přechodům mezi nimi.
Obyčejný orientovaný graf
Definice
Graf je dvojice 𝐺 = (𝑈, 𝐻), kde:
U je konečná množina uzlů (vrcholů)
H je konečná množina orientovaných hran (dvojic), 𝑯 ⊆ (𝒖,𝒗)  𝒖, 𝒗 ∈ 𝑼
U NEorientovaného grafu to není dvojice 𝒖,𝒗, ale množina 𝑢, 𝑣.
Mezi dvěma uzly mohou být dvě hrany v opačných směrech.
Obecný orientovaný graf
Může mít více hran mezi stejnými uzly.
Je to trojice 𝐺=(𝑈,𝐻,𝜖), kde
𝑈 je konečná množina uzlů (vrcholů)
𝐻 je konečná množina hran
Pojmy
Počet hran
Označme si písmenem 𝑢 počet uzlů v grafu. Obyčejný neorientovaný graf může obsahovat maximálně 𝒖∗(𝒖−𝟏)𝟐 hran. Orientovaná verze obyčejného grafu může obsahovat maximálně 𝒖∗(𝒖−𝟏) hran.
Ohodnocený graf
Graf ve kterém je každé hraně přiřazena její cena (číslo)
Turnaj
Je orientovaný graf, kde mezi každými dvěma různými uzly existuje právě jedna orientovaná hrana.
Výstupní stupeň uzlu
Je počet hran, které z uzlu vystupují, 𝑑𝑒𝑔−(𝑢).
Vstupní stupeň uzlu
je počet hran, které do uzlu vstupují, 𝑑𝑒𝑔+(𝑢).
Koncový uzel
Pokud 𝑑𝑒𝑔−(𝑢) = 0, jedná se o koncový uzel.
Počáteční uzel
Pokud 𝑑𝑒𝑔+=0 jedná se o počáteční uzel.
Eulerovský graf
Je orientovaný graf, kde existuje uzavřený orientovaný tah, který obsahuje všechny jeho orientované hrany. (dá se nakreslit jedním tahem)
Souvislý orientovaný graf je Eulerovský právě tehdy, když platí: ∀𝒖∈𝑼:𝐝𝐞𝐠+𝒖=𝐝𝐞𝐠−(𝒖)
Hamiltonovský graf
Hamiltonovský graf je graf, který lze projít takovou cestou, že každý jeho uzel je navštíven právě jednou s výjimkou uzlu výchozího, který je zároveň uzlem cílovým. Neboli - graf je hamiltonovský, právě když obsahuje kružnici, která prochází všemi jeho uzly (tzv. hamiltonovská kružnice)
Souvislost
Orientovaný sled, tah, cesta a kružnice jsou definovány analogicky k obyčejným.
Symetrizace
Je-li G = (V, E) orientovaný graf, lze sestrojit neorientovaný graf G’ = (V, E’), který je k němu v jistém smyslu ekvivalentní: 
Z grafu G tedy jakoby odstraníme informaci o směru hran.
Souvislost
Orientovaný graf je souvislý, pokud symetrizací vznikne souvislý obyčejný graf.
Silná souvislost
Orientovaný graf je silně souvislý, pokud pro libovolné dva uzly existuje orientovaná cesta.
graf je silně souvislý, pokud pro každé dva vrcholy x, y existuje cesta z x do y i z y do x.
Algoritmy pro nalezení minimální cesty
Dijkstrův algoritmus 
Na Dijkstrův algoritmus lze pohlížet jako na zobecněné prohledávání grafu do šířky, při kterém se vlna nešíří na základě počtu hran od zdroje, ale vzdálenosti od zdroje (ve smyslu váhy hran). Tato vlna proto zpracovává jen ty uzly, k nimž již byla nalezena nejkratší cesta.
Dijkstrův algoritmus si uchovává všechny uzly v prioritní frontě řazené dle vzdálenosti od zdroje - v první iteraci má pouze zdroj vzdálenost 0, všechny ostatní uzly nekonečno. Algoritmus v každém svém kroku vybere z fronty uzel s nejvyšší prioritou (nejnižší vzdáleností od již zpracované části) a zařadí jej mezi zpracované uzly. Poté projde všechny jeho dosud nezpracované potomky, přidá je do fronty, nejsou-li tam již obsaženi, a ověří, zda-li nejsou blíže zdroji, než byli před zařazením právě vybraného uzlu mezi zpracované. To znamená, že pro všechny potomky ověřuje:
Pokud nerovnost platí, tak danému potomkovi nastaví novou vzdálenost a označí za jeho předka zpracovávaný uzel. Po průchodu přes všechny potomky algoritmus vybere z fronty uzel s nejvyšší prioritou a celý krok opakuje.
Algorimus terminuje v okamžiku, kdy jsou zpracovány všechny uzly (prioritní fronta je prázdná).
Dijkstrův algoritmus je použitelný jen tehdy, obsahuje-li graf pouze nezáporně ohodnocené hrany - v opačném případě není schopen garantovat, že při zpracování uzlu byla již nalezena nejkratší možná cesta.
[link]
Složitost
Složitost Dijkstrova algoritmu závisí na implementaci prioritní fronty. V případě její implementace pomocí sekvenčního vyhledávání je složitost algoritmu 𝑶(𝑼𝟐), při použití binární haldy 𝑶(𝑯𝐥𝐨𝐠𝟐𝑼).
Floyd-Warshallův algoritmus
Tento algoritmus funguje i se zápornými hranami. Při nalezení kružnice záporné délky tuto odhalí (diagonální prvek matice bude záporný).
Sice má složitost 𝑂(𝑁3), ale najde všechny nejkratší vzdálenost mezi všemi páry vrcholů.
[link]
Floyd-Warshallův algoritmus má na vstupu matici délek, říkejme jí 𝐷0. Pokud mezi dvěma uzly (𝑖,𝑗) vede hrana délky 𝑙, tak tato matice obsahuje na indexu (𝑖,𝑗) právě tuto hodnotu. Na diagonále má tato matice samé nuly a na ostatních indexech, které neodpovídají hraně nekonečno. Jinými slovy tato matice obsahuje vzálenosti uzlů, které nevedou skrze žádného prostředníka.
V každé iteraci Floyd-Washallova algoritmu se tato matice přepočítá tak, aby vyjadřovala vzdálenost všech dvojic uzlů skrze postupně se zvětšující množinu přípustných prostředníků. Jednoduše řečeno matice 𝐷1 bude vyjadřovat vzdálenost všech uzlů s možností využití jednoho (daného) prostředníka, 𝐷2 vzdálenost při možném využití dvou (daných) mezilehlých uzlů, 𝐷𝑚 při možnosti využití m mezilehlých uzlů.
Tato transformace se dá vyjádřit pro 𝑘≥1 následujícím rekurentním vztahem:
Složitost
Asymptotická časová složitost algoritmu je 𝑶(𝑵𝟑) a paměťová je 𝑶(𝑵𝟐).
Algoritmus
Vstup (délky hran) je zadán maticí A (řádek a sloupec označuje počáteční/koncový uzel hrany).
Dále máme matici posloupností P, na počátku obsahuje každý prvek pouze číslo svého sloupce.
Postupnými iteracemi (n iterací, kde n = | U | ) se vypočítávají další kroky matic až se dojde do koncového tvaru a matice vzdáleností obsahuje minimální vzdálenosti.
V každé iteraci se prvky matic Ai přepočítají:
Pokud 𝑎𝑖𝑘𝑗−1≤𝑎𝑖𝑗𝑗−1+𝑎𝑗𝑘𝑗−1 pak 𝑎𝑖𝑘𝑗=𝑎𝑖𝑘𝑗−1, 𝑎𝑖𝑘𝑗=𝑎𝑖𝑘𝑗−1
Pokud 𝑎𝑖𝑘𝑗−1>𝑎𝑖𝑗𝑗−1+𝑎𝑗𝑘𝑗−1 pak 𝑎𝑖𝑘𝑗=𝑎𝑖𝑗𝑗−1+𝑎𝑗𝑘𝑗−1,  𝑎𝑖𝑘𝑗=𝑎𝑖𝑗𝑗−1
Jinak 1
Pro iteraci j sledujeme matici Aj − 1 a to pouze její j-tý řádek a j-tý sloupec (tedy takový kříž). Pro všechny prvky z Aj − 1 porovnáváme jejich hodnotu s průmětem na tento kříž (tedy se součtem s odpovídajícími prvky na stejném řádku a sloupci v kříži). Pokud je součet větší než hodnota prvku, opíšeme hodnoty obou matic. Pokud je součet menší, v matici Aj zapíšeme součet a v matici Pj zapíšeme hodnotu j − 1.
Jinak 2
Máme matici A (řádky a sloupce popsané uzly) určující nejkratší existující cestu mezi příslušnými uzly. Na začátku ji inicializujeme tak, aby na příslušných místech byly zapsány délky hran mezi danými uzly. Pak matici aktualizujeme tolikrát kolik je uzlů grafu. Každá aktualizace probíhá tak, že jedeme postupně po jednotlivých uzlech v pořadí v jakém je jimi popsána matice. Pro všechny dvojice uzlů i, j pak zkontrolujeme zda cesta přes k-tý uzel není kratší než aktuálně zapsaná hodnota. Tj. porovnáme současnou hodnotu a součet cest i do k a k do j a zapíšeme minimum.
Jinak 3
 1 // Předpokládáme funkci cenaHrany(i, j) vracející cenu hrany z i do j
 2 // (pokud hrana neexistuje, cenaHrany = nekonečno)
 3 // Dále, N je počet vrcholů a cenaHrany(i, i) = 0 
 4 
 5 int cesta[][]; // Dvourozměrné pole. V každém kroku algoritmu je cesta[i][j] 
 6                // nejkratší cesta z i do j použitím 1. až k-té hrany.
 7                // Všechny hrany cesta[i][j] jsou inicializovány funkcí 
 8                // cenaHrany(i,j);            
 9
10 procedure FloydWarshall ()
11    for k: = 1 to N
12    begin
13       foreach (i,j) in (1..N)
14       begin
15          cesta[i][j] = min(cesta[i][j], cesta[i][k] + cesta[k][j]);
16       end
17    end
18 endproc
Nalezení cesty
Pokud už máme vypočítáno tak cestu mezi uzly a a b hledáme tak, že se podíváme na a-tý řádek a b-tý sloupec. Tam vidíme přes jaký uzel musíme jít nejkratší cestou. Pokud tam je b tak jdeme přímo. Pokud tam je jiný uzel c tak si stejným způsobem najdeme jak se nejkratšeji dostat z a->c a c->b.
YT video
[link]
--- 0. iterace (podíváme se, kam se z vrcholů dostaneme napřímo)
Tedy z A se dostaneme s cenou 3 do C a s cenou 0 do D
Z B se dostaneme s -2 do A a s 1 do D
Atd. atd… je to prostě nultá iterace a nejdeme tu zatím "přes žádný vrchol"
--- 1. iterace (začínáme se zastávkou ve vrcholu A)
Jak drahé bude se z vrcholu B dostat do C se zastávkou v A?
Z B do A to je -2 a z A do C to je 3, tedy celkově -2+3=1.
Podobně to je pro cestu do D.
--- 2. iterace (teď pro vrchol B)
--- 3. iterace (tady se podíváme jestli můžeme cesty vylepšit pokud půjdeme přes vrchol C… a ne nemůžeme)
--- 4. iterace (poslední iterace, zastavujeme se ve vrcholu D)
Tady to ještě trošku dovysvětlím:
Průsečík (C|A s hodnotou 7), tedy za kolik se dostaneme z C do A
V této iteraci jdeme přes vrchol D. Tedy podíváme se, kolik stojí dostat se z vrcholu C do D. To je 5 (průsečík C|D). A teď se podíváme, za jak dlouho se dostaneme z vrcholu D do A (průsečík D|A), to je 2. A teď sečteme cestu z C do D (5) a z D do A (2) a dostaneme 7.
Obdobně to spočítáme pro cestu z C do B.
Notes
1. Otazka (predmet) (okruh): 9. Obyčejné grafy.- MAT
Kdo me primarne zkousel: Holík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
9ka otázka, ale chcel orientované grafy, takže prakticky 9+10 
. Začal som orientovanými grafmi - defíníciou - je to trojica G = (H, U, epsilon), kde ma Holik prerusil, ze nech poviem co je co. 
To som zvladol, potom sa pytal priamo na algoritmy: Povedal som Dijkstrov, pytal sa ma este na Floyd-Warshalov-vravim, ze vobec neviem. Holik skusal, ze ci aspon nieco, vravim, ze vobec 
Dalej na algoritmy pre hladanie minimalnej kostry grafu - Popisal som Kruskalov, ale pri odpovedi som ho uviedol ako Primov. 
Vysledna D. 
From <[link]> 
1. Otazka (předmět) (okruh): Orientované grafy (10)
Kdo me primarne zkousel: Navrat
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal jsem co je orientovany graf. Potom jsem rekl co je to orientovana cesta a kruznice. To me zastavil a zeptal se na ohodnoceni hran. Pak ze mam prejit na Dijkstra. Popsal jsem minimalni cestu, horni odhad, predchudce. Pak chtel vedet vystup algoritmu. Rekl jsem ze minimalni cesta mezi uzly, ale chtel upresneni. Jiny vystup jsem si nevzpomel a zbytek zkouseni se to ze me snazil dostat. Nakonec rekl ze vystup jsou vsechny cesty mezi temi uzly. Pak se me rychle zeptal, jak inicializujem Dijkstra. To jsem rekl a to mu stacilo. Znamka D.
From <[link]> 
1. Otazka (předmět) (okruh): 10 (Orientované grafy)
Kdo me primarne zkousel: doc. RNDr. Smrž
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Toto bola jedna z otázok, ktoré som fakt chcel... tak som ju vzal ako prvú. A potom to prišlo. Žiadne definície, poďme na Floyd-Warshalla. Ako, princíp som zhruba vedel, ale mýlil som sa. Dosť. Tak potom ešte teda že nech definujem, ako si predstavujem taký orientovaný graf. Tak som s trochou pomoci konečne napísal definíciu, ale už som bol taký na seba nahnevaný, že aj tam boli chyby. Hnevám sa na seba, dobrý okruh to bol, ale začať poslednou podotázkou z grafov mi neurobilo dobre.
From <[link]> 
1. Otazka (předmět) (okruh): MAT - Orientované grafy.
Kdo me primarne zkousel: Horák Aleš
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem popisem definice orientovaného grafu. Pak jsem si nebyl moc jistý jesti pokračovat dál definicema jako je orientovaný sled atp., tak to mě potom Horák navedl ať přejdu k popisům těch dvou algoritmů, tak jsem je více méně slovně popsal chtěl slyšet teda hlavně to v čem se lyší vstupní grafy v těchto algoritmech (že Dijkstrův alg. nesmí obsahovat graf záporně ohodnocenou kružnici) a následně chtěl napsat ten vzorec z pro ůpravu hodnoty v matici pro Floyd-Warshalla. Sotva jsem to odvykládal tak už mě Janoušek chtěl poslat za dveře.
From <[link]> 
1. Otazka (předmět) (okruh): 10 Orientované grafy (MAT)
Kdo me primarne zkousel: Rychlý Marek, RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Otázka relativně lehká. Řekl jsem nějaké základy - popsal graf, cestu. Celkem pomáhal, vždy když jsem něco neřekl, tak se zeptal, snažil mě na to navést. Pak jsme se přesunuli na algoritmy pro hledání cesty minimální délky. Měl jsem říct i časovou složitost a jak by se ty algoritmy implementovaly. A od té doby bych řekl, že se to nějak zvrhlo 
 . Když jsem si ty algoritmy předem procházel, tak si říkám: "pohoda, to chápu". Jiná věc je ale to někomu dalšímu vysvětlit. Motal jsem to tam úplně všechno dohromady. Nejhorší na tom bylo, že bych si nad tím chvíli popřemýšlel, nakreslil si nějaký příklad (ale řekněte komisi: "já si na 15 min odskočím, promyslím to, vymyslím nějaký příklad a přinesu řešení"). Vždy, když jsem začal přemýšlet, potřeboval jsem přestat mluvit. Nastalo tím pádem úplné ticho, což neznělo dobře. Tak jsem raději mlel a povídal vše, co mě napadlo. Komise hodně v pohodě. Snažili se mi tam všichni maximálně radit. Rychlý už pak přišel i kreslit na tabuli. Ani bych se nedivil tomu, kdyby ztratil nervy a jednu mi tam natáhnul 
Rada pro další generace: Nacvičte si na tyto algoritmy při učení nějaký příklad, na kterém to pak ukážete.
From <[link]> 
2. Otazka (předmět) (okruh): Orientované grafy
Kdo me primarne zkousel: Křivka (myslim) a ještě mu někdo přisluhoval
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Opět chtěli nejdřív nějakej obecnej základ. Začal jsem dost nervozně po předchozím výstupu, ale naštěstí tuhle otázku jsem měl naučenou. Vlastnosti grafů jsme přeskočili a hned se šlo na algoritmy hledání nejkratší cesty. Ty dva, co jsou uvedeny v otázkách, jsem samozřejmě zaměnil, protože jsem se je učil podle pořadí na papíru a ne podle názvu. 
 Naštěstí jsem si to brzo uvědomil a pak už jsem ten princip popsal správně. Chtěli hlavně Floyd-Warshallův algoritmus. Padla otázka na složitost, ale tu jsem věděl. Pak ještě jak je to se záporným ohodnocením. Tam jsem věděl, že to Dajkstr nezvládne, ale u FW jsem musel trochu vařit z vody, protože se začali ptát na to, co by tam mohlo vzniknout za problém s těma zápornýma cestama (snad že se to může dokonce zacyklit, ale už si to přesně nepamatuju). Nakonec jsme se k tomu nějak dobrali a propustili mě z pekla ven 
From <[link]> 
2. Otazka (předmět) (okruh): MAT - Orientované grafy (orientované cesty, Dijkstrův a Floyd-Warshallův algoritmus) 
Kdo me primarne zkousel: Rychlý
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Pohoda. Zadefinoval sem graf, sled, tah, cestu. Pak chtěl vědět jak funguje Floyd-Warshallův algoritmus a v čem se liší od Dijkstry, toť vše. Nakonec B.
From <[link]> 
. Otazka (předmět) (okruh): Orientované grafy (MAT)
Kdo me primarne zkousel: Smrž Pavel, doc. RNDr., Ph.D.
Co jsem k tomu řekl(a)/na co se ptali/co mně vytkli:
Než jsem se nadechl, chtěl po mě zadefinovat graf nějakým zápisem na tabuli. Ještě než jsem stihl přiložit fix k tabuli, vypadlo z něj, že vlastně radši jen jak definujeme množinu hran. Tu jsem tam v pohodě napsal. Pak se ptal, co ty hrany musí mít, abychom mohli hledat minimální cesty. Odpověděl jsem, že samozřejmě nějakou cenu přechodu - ale Smrž se divně zatvářil, že to jako není zrovna přesné. To už jsem si začal řikat trochu "WTF".
Pak překvapil, že rovnou od množiny hran přeskočil kdesi na konec a najednou chtěl Floyd-Warshallův algoritmus. To mě nechalo klidným, protože jsem si ho zkoušel a uměl ho. Začal jsem víceméně neformálně popisovat algoritmus, kde využívám dvě matice.. a pak to začlo. Neustále rýpal, že se mu něco nezdá, že ať to nakreslím, pak dělal že nechápe (jakoby Floyd-Warshalla v životě neviděl), pak že prý jsem něco předtím řekl špatně (WTF, tak proč to neřekl hned, já už samožřejmě prd věděl, co jsem předtím přesně říkal), prostě se mi zdálo, že mě chce pěkně vydusit, ale já byl v klidu a neustále mluvil a vysvětloval. Bohužel jsem si díky stresu nenavrhl zrovna ideálně systém značení v matici posloupností a trochu se do toho zamotal, ale lidsky jsem ten princip vysvětlil správně. Smrž to ovšem proložil dotazy na složitost jako: "Co myslíte, že má větší složitost - nalezení cesty z konkrétního uzlu do jiného konkrétního nebo mezi všemi?" a "Jakou byste řekl, že má tento algoritmus složitost?" To jsem bohužel nevěděl z hlavy (moje chyba), ale snažil jsem se to odhadnout.. Na nic z toho mi neodpověděl (ani jestli je to špatně), jen se vždycky tvářil, že se mu to nelíbí. Ostatní nic neřikali. Smrž se mě celou dobu vlastně snažil přesvědčit, že tomu nerozumím, ale já jsem byl neoblomný. Celkově jsem z toho měl dobrý pocit, že orientované grafy jsem zvládl dobře, krom těch jeho dotazů na složitost, které jsem zkonil - věřil jsem si tak na B-C.
From <[link]> 
1. Otazka (okruh):Orientované grafy
Kdo me primarne zkousel: Smrz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zadefinoval jsem tam orientovany graf, a hned ze jake znam algoritmy na hledani nejkratsi cesty a co je to nejkratsi cesta. Rikam Dijkstruv a Floyd-Warshalluv, a pry neco o FW. Tak jsem nakreslil ty 2 matice, rekl jsem ze je to iterativni, chtel jsem prejit k algoritmu kdyz Smrz vypalil pry jakou to ma slozitost. Ja byl nachystany na to popsat ten algoritmus a tohle me naprosto vykolejilo, okno, mozek vypnul. Byl jsem schopny si vzpomenout akorat na linearni slozitost, cumeli na me jak na debila (nedivim se). Tezce jsem zpanikaril, koukam na ty matice, rikam si ty pyco, matice musi byt kvadraticke, jsou 2 ale tak to by nemel byt zas takovy rozdil, z toho snad kubicka nebude. Tak jsem rekl kvadraticka, zas na me cumeli, pak neco s Dijkstrovym. Byl jsem uplne v koncich, mozek vyply, tak jsem placl zas linearni. Drtil me takhle docela dlouho, pak to nastesti milosrdne utnuli.
From <[link]> 
Komise 61: Ceska, Peringr, Janousek, Misovic (externi), Bartik, Bidlo
1 otázka: Mišovič (externi ucitel) - Orientovane Grafy
Prvni pocit - jo to musi byt v pohode. Pocit po polozeni otazky ... naprosto sem nechapal co chce 
Postupne ze me vypacili co chteli.
From <[link]> 