10 - Orientované grafy

Question 1

Orientovaný a obecný orientovaný graf

Answer 1

orientovaný graf = uspořádané dvojice (místo množin) = pevně daná orientace (Mezi dvěma uzly mohou být dvě hrany v opačných směrech.)

Graf je dvojice G = (U, H), kde:
• U je konečná množina uzlů (vrcholů)
• H je konečná množina orientovaných hran (dvojic), H ⊆ {(u,v) │ u, v ∈ U}
○ U NEorientovaného grafu to není dvojice (u,v), ale množina {u, v}.

Obecný orientovaný graf
Může mít více hran mezi stejnými uzly.
Je to trojice G=(U,H,ϵ), kde
	• U je konečná množina uzlů (vrcholů)
	• H je konečná množina hran
	• ϵ:H→{(u,v)|u,v∈U} je zobrazení přiřazující každé hraně dvojici uzlů (U={1,2,3,4}, H={a,b,c,d}, ε(a)=(1,3), ε(b)=(1,3), ...)

Question 2

Počet hran, ohodnocený graf a turnaj

Answer 2

neorientovaný graf -> maximálně (u(u-1))/2, orientovaný u(u-1)

Ohodnocený graf
Graf ve kterém je každé hraně přiřazena její cena (číslo)

Turnaj (každý hrál s každým)
Je orientovaný graf, kde mezi každými dvěma různými uzly existuje právě jedna orientovaná hrana.

Question 3

Stupně uzlů a Eulerovský graf

Answer 3

Eulerovský graf -> uzavřený orientovaný tah (domeček)
(pro každý uzel je stupeň vstupu = stupeň výstupu)

Je orientovaný graf, kde existuje uzavřený orientovaný tah, který obsahuje všechny jeho orientované hrany. (dá se nakreslit jedním tahem a skončíme tam kde je začali (uzavřený tah))
• Souvislý orientovaný graf je Eulerovský právě tehdy, když platí: ∀u∈U:〖deg〗+⁡〖(u)=〖deg〗−⁡〖(u)〗 〗

Výstupní stupeň uzlu
• Je počet hran, které z uzlu vystupují, 〖deg〗−⁡〖(u)〗.
Vstupní stupeň uzlu
• je počet hran, které do uzlu vstupují, 〖deg〗+ (u).
Koncový uzel
• Pokud 〖deg〗−⁡〖(u)〗 = 0, jedná se o koncový uzel.
Počáteční uzel
• Pokud 〖deg〗+=0 jedná se o počáteční uzel.

Question 4

Souvislost a silná souvislost

Answer 4

Souvislost - mezi každými uzly je hrana
• Orientovaný graf je souvislý, pokud symetrizací vznikne souvislý obyčejný graf.

Silná souvislost - mezi každými uzly jsou dvě hrany (oba dva směry)
• 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.

Question 5

Dijkstrův algritmus

Answer 5

Vždy přidáme uzel, zkontrolujeme nové cesty pro do všech ostatních úzlů a jdeme dál

Na Dijkstrův - pouze nezáporně ohodnocení hrany! - 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.

vzalenost_zpracovavany + delkaHrany_zpeacovavanyPotomek < vzdalenost_potomek

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 O(|U|^2), při použití binární haldy O(|H| 〖log〗_2⁡|U|).

Question 6

Floyd-Warshallův algoritmus

Answer 6

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 O(N^3), ale najde všechny nejkratší vzdálenost mezi všemi páry vrcholů.

Vytvoříme matice hodnot a uzlů v cestě, postupně procházím cesty ze všech uzlů do všech ostatních uzlů a zkoušíme cesty přes různé vrcholy