5. Základní grafové algoritmické problémy a jejich složitost

Ako sa učiť?
1) Prečítať [CERNA], kapitola 4, prípadne ešte kapitola 2.
2) Tento text je len zhrnutím základných pojmov a myšlienok odtiaľ, môže slúžiť na a) spravenie prehľadu b) rekapituláciu.

Grafy: Neorientovaný. Orientovaný. S loopmi.

Reprezentácie grafov:
Matica susednosti: Tabuľka. Pre každú dvojicu vrcholov 0 alebo 1 podľa toho, či je medzi nimi hrana (v prípade neorientovanych grafov je symetrická)
Zoznam nasledovníkov: Ku každému vrcholu zoznam jeho nasledovníkov

Základné algoritmy (A) a problémy (P):

(A1) Prehľadávanie do hĺbky
(A2) Prehľadávanie do šírky

(P1) Topologické usporiadanie acyklických orientovaných grafov. Pomocou A1.
(P2) Silne súvislé komponenty. Pomocou A1. Využije sa viac, než raz. Takisto možné pomocou A2.
(P3) Bipartitné grafy. Pomocou A2.

(P4) Minimálna kostra.
Algoritmy pre P4: budovanie min. kostry z prázdnej množiny pridávaním bezpečných hrán
(A3) Kruskal. Les. Datová štruktúra UNION-FIND.
(A4) Prim. Strom. Fibonacciho halda.

(P5) Najkratšie cesty. 3 varianty.
- Z jedného vrcholu do všetkých ostatných – P5.1
- Medzi dvojicou vrcholov (Nevieme žiaden asymptoticky než pre P5.1)
- Medzi všetkými dvojicami vrcholov – P5.2
PODPROBLEMY
- Má graf záporne ohodnotené cykly?
ALGORITMY pre P5.1
- Bellman-Ford. Dynamické programovanie. Relaxácia. n krat, vzdy vsetky vrcholy v tom istom poradi.
- Alg. pre orientované acyklické grafy. Bellman-Ford s tým, že vieme v akom poradí relaxovať, takže každú hranu stačí relaxovať raz.
- Dijkstra pre grafy s nezápornými dĺžkami
ALGORITMY pre P5.2
- Násobenie matíc. ???
- Floyd-Warshall. Dynamické programovanie. Najkratšie cesty z i do j, ktoré používajú len vrcholy 1, …, k-1. Z toho sa rýchlo spočíta najkratšia cesta, ktorá môže používať ešte vrchol k.
d_ij^k = w_{ij} … ak k=0
d_ij^k = min (d_ij^k-1, d_ik^k-1 + d_kj^k-1) … ak k>0
- Johnson.
Zistiť, či obsahuje záporný cyklus. Ak nie, modifikovať váhy hrán, aby najkratšie cesty v pôvodnom ohodnotení boli najkratšie v novom ohodnotení a váha každej hrany v novom ohodnotení bola nezáporná. Potom Dijkstra pre každý vrchol.
Vybrať vrchol s. Spočítať Bellman-Ford. h(v)=delta(s,v) z BF. w*(u,v):=w(u,v)+h(u)-h(v).

(P6) Maximálny tok v sieti.
METÓDY
- A) Ford-Fulkerson
ALGORITMY
Edmonds-Karp: cesta najkratsej dlzky.
Najširších ciest: cesta s maximalnou rezidualnou kapacitou.
Zjemňovania stupnice.
- B) Push-Relabel

FF: Nulový tok. Zvyšovanie hodnoty. Zlepšujúca cesta. Reziduálna sieť. Rezy(pri dôkaze korektnosti).

PR: Pseudotoky. Môže vstupovať viac ako vystupuje. Výška vrcholu. Zvyšovanie výšky vrcholov. Tlači (PUSH) sa z vrcholov z vyššou výškou do vrcholov s nižšou výškou.

Úlohy, ktoré sa dajú previesť na P6.
- Problém maximálneho párovania v bipartitných grafoch
- Problém prieskumu
- Rozvrhovanie letov

n - počet vrcholov
m - počet hrán

DFS, BFS: O(n + m)

Kruskal: O(m*log m)
Prim: Fibonaciho halda: O(n*log n + m); inak O(n^2), pripadne O(m*log n)

Bellman-Ford: O(m*n)
Dijkstra: Fibonaciho halda: O(n*log n + m); binarny strom, binarna halda: O(m*log n), pole: O(n^2)

Nasobenie matic: O(n^3 *log n)
Floyd-Warshall: O(n^3). Pozn: n krat pre kazdu dvojicu vrcholov
Johnson: O(n^2*log n + nm)

Ford-Fulkerson: - predpoklady: celociselne kapacity hran, f - hodnota maximalneho toku… O(m*f)
- korektnost nie je zarucena, ak kapacity nie su racionalne.
- Edmonds-Karp: O(nm^2)
- Najsirsie cesty: O(n^2 * m*log f)

Push-Relabel:
- Jednoducha implementacia: O(mn^2)
- Zlozitejsia implementacia: O(n^3)

- Vertex cover: Dá sa nájsť k vrcholov v grafe, tž každá hrana má aspoň 1 vrchol medzi týmito k vrcholmi?
- Dominating set: Dá sa nájsť k vrcholov v grafe, tž každý vrchol je adjacent k niektorému z týchto k vrcholov?
- Chromatic number: Dajú sa vrcholy ofarbiť k farbami, tž každá hrana je medzi dvoma vrcholmi odlišnej farby?
- Clique: Existuje subgraph isomofný s K_k?
- Independent set: Existuje k vrcholov v grafe, tž medzi žiadnymi dvomi z nich neexistuje hrana?
- Hamiltonian path/cycle: Existuje?
- Subgraph isomorphism: Dva grafy G, H. Má G subgraph, ktorý je izomorfný H?

A ďalšie: http://en.wikipedia.org/wiki/List_of_NP-complete_problems

• MA010 Graph Theory
• MA015 Grafové algoritmy

• 1-psk

Michal Abaffy
Moja spokojnosť s vypracovaním: 90%. Nie ako učebný text, ale ako spravenie prehľadu / rekapitulácia.

• [CERNA] https://is.muni.cz/auth/el/1433/jaro2010/IB108/um/slajdy_IB108_jaro2010_komplet.pdf