Semestrální práce z TI

Zadání 5.4.1

Nechť jsou v grafu G=<H,U> zadány dvě disjunktní podmnožiny hran , pro které je třeba nalézt fator T = <H',U> grafu G s minimální sumou ohodnocení hran takový, že platí:

(a) Navrhněte vhodnou úpravu algoritmů určení min. kostry, pomocí které se získá algoritmus řešení této rozšířené úlohy a určete jeho asymptotickou složitost.

(b) Určete, za jakých podmínek bude nalezený faktor T kostrou grafu G

Návrh řešení

Faktor grafu, který máme nalézt, má dle zadání obsahovat všechny hrany z množiny B, naopak nemá obsahovat hrany z množiny A. Pokud nebudeme uvažovat záporně ohodnocené hrany tak řešením je překvapivě faktor T = <B,U>. Pokud budeme uvažovat záporně ohodnocené hrany pak je do řešení zahrneme také (B+). Nalezený faktor bude kostrou právě tehdy nebude-li obsahovat kružnice a zároveň bude souvislý.

Zdá se, že v zadání mé semestrální práce je něco špatně a tak pokud budeme chtít použít algoritmy pro nalezení min.kostry tak pouze za předpokladu, že v řešení připustíme hrany které nejsou v B a ani v A, ale mají menší váhu než MAX_w(B).

Abychom toto zařídíli přiřadíme nechtěným hranám váhu oo a naopak hranám žádaným váhu 0. Oba algorimy (Jarník-Prim, Borůvka-Kruskal) musíme ještě modifikovat tak aby skončili právě ve chvíli kdy jejich částečné řešení splňuje podmínku zadání. První modifikace algoritmů spočívá v přidání dvou for cyklů na začátek každého z algoritmů. Tyto for cykly modifikují jen ohodnocení těch hran v množině H, které patří do A nebo B dle navrhovaných změn. Dále pro algorimus Borůvka-Kruskal změníme pouze řádek 5 (viz skripta str 100), tak abychom skončili právě tehdy, bude-li splněna zadávající podmínka.

5 for každou hranu [u,v] z H v pořadí neklesajících vah maximálně však do MAX_w(B)

Tím zajistíme že se ve faktoru neobjeví hrany, které by zvyšovali jeho min. ohodnocení.

Pro algoritmus Jarník-Prim bude postup obdobný, ale jelikož tento algorimus postupuje při tvoření min. kostry (faktoru) spojitě může se se stát že budeme muset přejít přes nějakou hranu jejíž ohodnocení bude větší než MAX_w(B), abychom do řešení zahrnuli i hranu z množiny B, ke které bychom se jinudy nedostali. Proto kdykoli do řešení zahrneme hranu z množiny B poznamenáme si to. (např do množiny X) Algoritmu dovolíme přidávat i hrany s větším ohodnocením než je MAX_w(B) pokud se množiny X a B neshodují. Jestli je X = B nebudeme nic přidávat a případně můžeme i skončit.

8 if X!=B then if and (w(u,v)<d[v])

9 then p[v]:=u; d[v]:=w(u,v);

10 if then

Algoritmy

Upravený algoritmus Borůvka - Kruskal:

KB-MST-MOD(G,w,A,B)

0 všem hranám z A změň w na oo, z B změň na 0

1 Z:=

2 for každý uzel

3 do MAKE-SET(u)

4 uspořádej H do neklesající posloupnosti podle váhy w

5 for každou hranu [u,v] z H v pořadí neklesajících vah maximálně však do MAX_w(B)

6 do if FIND-SET(u)!=FIND-SET(v)

7 then Z:=

8 UNION(u,v)

9 return(Z)

Upravený algoritmus Jarník - Prim:

JP-MST-MOD(G,w,r,A,B)

0 všem hranám z A změň w na oo, z B změň na 0

1 Q = U

2 for každý uzel

3 do d[u] = oo

4 d[r] = 0 p[r]=NIL

5 while do

6 u = EXTRACT-MIN(Q)

7 for každý uzel do

8 if X!=B then if and (w(u,v)<d[v])

9 then p[v]:=u; d[v]:=w(u,v);

10 if then

Časové složitosti

Časová složitost algoritmu Borůvka - Kruskal závisí (podle skript) na způsobu implementace řazení a operací s množinovým rozkladem. Protože modifikovaný algoritmus skončí ještě dřív než jeho originál bude mít tedy nejhůře stejnou časovou složitost. Tj V průměrném případě bude složitost algoritmu závistet na mohutnosti množin A a B jež jsou disjunktními podmnožinami H. Pro algoritmus Jarník-Prim je složitost dána vztahem: Protože ani množinovými operacemi s nově přidanou množinou X nezhoršíme tuto složitost tak i řešení této rozšířené úlohy bude mít v nejhorším případě tuto složitost. Průměrná složitost bude patrně záviset na mohutnosti množiny A a B.