Zadání

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

Vypracování

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.

Pojmy, problémy, algoritmy

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

Zložitosti

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)

NP-uplne grafove problemy

- 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

Předměty

Související otázky

Vypracoval

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

Zdroje

mgr-szz/in-tei/5-tei.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0