0000080

k : U — &

wartość k(u) można Interpretować jako koszt lub "długość* ga -łęzi u.

Sformułowanie problemu Jeot następujęcei

W zbiorze T wszystkich karkaoów T grafu C należy wyznoczyć taki karkas T* - <X,U>*> .aby

2Z Mu)

uCU

min XI M«)

TCT ucu^T

gdzie U^T jest zbioraa gałęzi karkasu T.

Efektywne algorytmy wyznaczanie karkoou T* zostały opro-cowane przez Kruekala (1956) [25] 1 Prima (1957) [38], Sę one szeroko wykorzystywane w praktyce przez projektantów takich obiektów, jak na przykład eioci energetyczna, wodociągowe, czy sieci dróg.

Należy zaznaczyć, że algorytm Prima Jest opracowany przy założeniu spójności grafu C i z tego względu przy wyznaczaniu T* należy go stosować oddzielnie dla każdej składowej spójności grafu G.

Algorytm Kruskala

O a n e: S - <G,p. (k)> , C - <X,U,P>. k i U- 31 .

Oznaczymy przez T zbiór karkasów T grafu C,

T - <X,U^T,P^T> . U^TC U. P^TC P.

wyznaczomy T* £ T . taki *•

ŁM")

u£U^r

■ in Z2 k(u)

TcT u«u^T

Procedurat ® U' i - P t C' i - <X.U.P'> ;

(2) Oeżell G* Jest karkasem grafu C (patrz worunki określajęce karkos), to skok do (4j.

(5) wybieramy gałęż u^t u\u', tekę że

^k,v • :łS\v^[u) •

^UJ ■ ^msfc$^ui ’ °J ■ * ^<X'W

Jośli A(Cj) > O, to U : - U\{Uj) i akok do ® ; U* i - iy Ci- <X,U’,P’> ;

Skok do ® •

®    T*: - C’ t

Algorytm P r i ■ o

Algorytm tan jest stosowany oddzielnie dla każdej składowej spójności.

O a n a t S ■ <C.JJ. {k)> , C - <X,U,P)    - graf spójny,

X. ki; . u. t«₃}-.

k i    ^"[“ljjn** " binarna aaelerz incydancji C.

Oznaczymy przaz T zbiór karkasów T grafu C

T - < X,U^T,P⁷> , U^TC U, P^TC P.

wyzna czyny T**£ T . taki Za

Ck(u) - min H k(u) uCl>^T*    T£ T u€U^t

Proceduro i

® Wybieramy dowolny x_Ać X; X* i •    ; U* i ■ P ;

Jeśli X¹- X, to skok do (3);

U_Ł • {u^CU i e_1: ■ Iau, nis jest Pftls}.

wybieramy u^i U^, tok| Ze

k(u_k) - min k(u) ;

^K u i Uj

X¹ i • X'u {x_r\ , gdzie x_r € X\X*Aa_rk • 1 ;

X"i - X\X'; U' i - (u_k\; C i - <x'. u| p'> . Jeśli X*• X, to skok do ® .

® A s • {utu I _hV_txx£ X'Ay£x" A<x.u.y> € p} ; Wybierany u_k< A. tak# Ze

k(u. ) - min k(u) UCA

159