Grafy a grafové algoritmy. Formalizace základních grafových pojmů, reprezentace grafů. Souvislost grafu, barevnost, rovinné grafy. Algoritmy (včetně složitosti a základní myšlenky důkazů korektnosti): prohledávání grafu do šířky a do hloubky, nejkratší vzdálenosti, kostry, toky v sítích.

Upozornění: bez nároku na úplnost a korektnost. Podle hesla „lepší něco než nic“. Ale snaha byla o co nejlepší výsledek.

• graf – uspořádaná dvojice (V, E) množin vrcholů a hran
• vrchol – jeden z prvků množiny určující graf; mohou z něj vést hrany
• hrana – dvouprvková podmnožina množiny vrcholů. (Orientovaný graf: E ⊆ V×V.) Když v ∈ e, tak v je incidentní s e.
• řídký graf – |E| je mnohem menší než |V|^2 (→ preferuje proto seznamy následníků)
• hustý graf – |E| je blízko |V|^2 (→ preferuje proto matici sousednosti)
• smyčka – hrana (a, a)
• cesta v grafu – posloupnost P = (v0, e1, v1, …), kde e_i = { v_i-1, v_i }, navíc v_i != v_j pro i != j
• tah – cesta, v níž se mohou opakovat vrcholy
• sled – cesta, v níž se mohou opakovat vrcholy i hrany
• cyklus/kružnice – uzavřená cesta (netriviální)
• sousední vrchol – spojený hranou

+ váhovaný graf, multigraf

• máme pole o |V| prvcích – pro každý vrchol u ∈ V jeden a je jím seznam prvků v $ (u, v) ∈ E
• paměťová náročnost: Θ(V + E)

• matice velikosti |V| × |V|
• prvek matice a_ij = 1, pokud (i, j) ∈ E, jinak a_ij = 0

• souvislý graf – (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje sled z x do y.
• slabá souvislost – graf je slabě souvislý, pokud jeho symetrizace (= odstranění orientovanosti) je souvislý graf.
• silná souvislost – graf je silně souvislý, pokud pro každé dva vrcholy x, y existuje cesta z x do y i z y do x.

Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled.

• Dvojitý DFS – první mi určí pořadí (na G^R) pro volání druhého (na G) (sestupné finishing časy), který mi vytiskne jednotlivé komponenty.

• vrcholový řez (= separátor) – taková množina U ⊆ V, že graf G = (V\U, E) není souvislý
• hranový řez
• vrcholová (hranová) souvislost – velikost minimálního vrcholového (hranového) řezu
• graf je vrcholově/hranově k-souvislý, pokud jeho vrcholová/hranová je ≥ k

Barvení grafu se zabývá přiřazováním barev nejčastěji vrcholům (příp. hranám či stěnám).

Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení b: V → {1, …, k} nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu {x, y} ∈ E platí b(x) ≠ b(y). Barevnost grafu (také chromatické číslo) G je minimální počet barev potřebný pro obarvení G. Značí se Χ(G) (= velké chí).

• pro rovinný graf existuje takové rovinné nakreslení, kdy se žádné dvě hrany nekříží
• duální graf – (multi)graf, jehož vrcholy tvoří stěny jiného rovinného grafu
• stěna – souvislý kus roviny určený rovinným nakreslením grafu

Věta (Eulerova formule): V rovinném grafu G=(V, E) platí:
1. |V| − |E| + s = |E|+2. (s = počet stěn)
2. |E| ≤ 3|V|−6.

Věta (o 4 barvách): Vrcholy rovinného grafu lze obarvit 4 barvami tak, aby žádná hrana nespojovala dva vrcholy stejné barvy.

• aplikace: návrh jednovrstvých tištěných spojů (= PCB) (VLSI designs)

Včetně složitosti a základní myšlenky důkazů korektnosti!

• Q – fronta z vrcholů
• d[u] – vzdálenost u od s
• π[u] – předchůdce u
• color[u] ∈ {white, gray, black} – pomocné

• inicializace pro všechny mimo počáteční vrchol s: obarvení na bílo, nekonečná vzdálenost, předchůdce nil
• inicilalizace s: šedý, vzdálenost 0, předchůdce nil, zařadí se do Q
• dokud se Q nevyprázdní, vezmu z Q u, projdu všechny jeho bílé sousedy, ošedím je, nastavím vzdálenost (d[u] + 1) a předchůdce (u), zařadím do Q a u přebarvím na černo

• incializace: O(n)
• žádný vrchol se pak již nepřebarví na bílo, takže jde do i z Q nejvýše jednou → operace s frontou tedy stojí O(n)
• seznam sousedů vrcholu se prochází, jen když je vrchol odstraňován z fronty, takže dohromady O(m)
• = O(m + n)

G = (V, E)

• BFS objeví každý z s dosažitelný vrchol, nedosažitelné nebudou objeveny.
• Po zastavení d[v] = δ(s, v) ∀v ∈ V.
• Pro každé v ∈ V dosažitelné z s je lib. nejkratší s-π[v]-cesta následovaná hranou (π[v], v) jednou z nejkratších s-v-cest.

Právě vrcholy zařazené do Q mají d[v] < ∞. Pokud v nedosažitelné z s, tak d[v] >= δ(s, v) = ∞, proto v nebude objeven.

V_k = {v ∈ V | δ(s, v) = k}, k ∈ N_0, → indukcí vzhledem ke k.

IK: Pokud v jde do Q, d[v], π[v] se již nikdy nemění. Jsou-li vrcholy zařazovány do Q v pořadí v_1, …, v_r, pak d[v_1] ≤ … ≤ d[v_r]. Nechť v ∈ V_k (k ≥ 1), tj. je objeven až po objevení všech z V_k-1. Poněvadž δ(s, v) = k, ex. cesta s, …, u (∈ V_k-1), v délky k. Nechť u je první takový objevený. V jistém okamžiku se u objeví na čele Q, v je objeven při prohlídce sousedů u. Tedy pro v ∈ V_k je π[v] ∈ V_k-1, a proto d[v] = d[π[v]] + 1. Nejkratší cestu do v tak získáme tím, že půjdeme po nejkratší cestě do π[v], a pak po hraně (π[v], v).

• incializace vynuluje čas + všechny obarví na bílo a nastaví předchůdce na nil
• hlavní část algoritmu iteruje přes všechny vrcholy grafu a nad bílými spouští podproceduru Visit
• ta: inkrementuje čas, nastaví discovery time, ošedí vrchol; projde všechny sousedy a bílým nastaví předchůdce a spustí nad nimi opět Visit; nakonec uzel očerní, inkrementuje čas a nastaví finishing time

• inicializace O(n), vynulování času O(1), iterace nad vrcholy O(n)
• Visit: nastavení parametrů – pro každý vrchol O(1); procházení sousedů O(m); nastavení parametrů – pro každý vrchol O(1)
• = O(m + n)

• věta o závorkách (discovery a finishing časy dvou uzlů jsou buď zcela disjunktní nebo tak či onak zanořené, pokud v DF-tree jde o následníka)
• věta o bílé cestě (pokud v je v DF-forest následníkem u, tak v čase d[u] vede od u k v cesta po čistě bílých vrcholech)

DF-forest = predecessor subgraph, kde hrany = { (π[v], v) | v ∈ V ∧ π[v] ≠ nil } → forest, protože DFS může být opakováno z více vrcholů

• MA010 Graph Theory
• MA015 Graph Algorithms

• 5-tei