,
pro které je tøeba nalézt fator T = <H',U>
grafu G s minimální sumou ohodnocení hran
takový, ¾e platí:
(C) Rudolf Marek
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
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 B nebo B+ obsahovat kru¾nice.
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¾ MAXw(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 MAXw(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¾ MAXw(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 MAXw(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
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 MAXw(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¾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.