44 (485)

z e er. i } cmi ki em ^

procedurę ZNAJDŹ (v, u);    {„v" - wierzchołek aktualny, „u" - po

boęin

i : =i-i numerowanie odwiedzanych wierzchołków zgodnie z

for weadj(v) do

if num[w) = 0 do

ł::-Jc+l; szos(k):“w;

ZNAJDŹ(w_y v); k:=k-l;

eise

if nuci (w]    < nuci (v] cand w o u then

{licznik cykli}

(s* jesz cyklem {w, stosfk], stos(k-l), SCOS ( l]-W. A 5 CC S i V, ] = V } end if; end if; end for;

enc {procedurę).

i

. S t O S { t ] ) ,

gezie

Należy soois zadać pytanie - czym właściwie jest cykl fundamentalny ?

• y'j

Cnoz jeśli do drzewa rozpinającego utworzonego na danym grafie G dodamy dowolną cięciwę ce E\7 łączącą dowolne wierzchołki' drzewa rozpinającego w- grane to zauważyć można, że powstały pod graf zawiera dokładnie jeden cykl, który oznaczyć można przez CJ Zbiór C, = {C_c : es E\T} nazywam v fundamentalnym zbiorem cykli grafu G, właśnie, „fundamentalny" - znaczy, że każdy cykJ grafu można w pewien sposób naturalny otrzymać z cykli zbioru £.

Znajdowanie cykli fundamentalnych ma duże znaczenie przy analizie obwodów' elektrycznych, gdyż każdemu cyklowi fundamenta i nem u w grafie możemy przyporządkować równanie wyrażające prawe Kirchoffa aia napięć; suma napięć wzdłuż cyklu równa jest zeru.

Powyższy' algorytm oparty jest na przeszukiwaniu w głąb i ma strukturę podobna do rekureocyjoegc algorytmu znajdowania drzewa rozpinającego. Każdy nowo napotkany wierzchołek umieszczony zostaj: na stosie i zdejmowany jest z tego stosu po wykorzystaniu. Oczywiste jest więc to, ze stos zawiera zawsze ciąg wierzchołków od aktualnego do korzenia.

Omawiając złożoność obliczeniową warto zauważyć, ze całkowita liczba kroków jest taka jak prr-wszystkich algorytmach przeszukujących w głąb, czyi i: O(n^m). Do tego należy dodać sumaryczna długość wszystkich cykii, która nie przekracza (m.-n±J)_t co daje»całkowitą złożoność algorytmu rzędu O(nm^n).

; Ujoe Ud oOttYUsa? .

(A

58. Potrać i omówić algorytm Kruskala znajdowania minimalnego drzewa rozpinającego. Jaka jest jego złożoność ?

i Dany jest graf G. Pełny, spójny, fajny, niezorientowany, z kosztami na krawędziach, trzeźwy i wesoły, pełen optymizmu i .... oczywiście nazywa się... JAREK !!!

Algorytm Kruskala (aU ludny::; FUJJJ) :

beęin

7:-0: { Zbiór krawędzi ainiaclneęo drzewa rozpinajacego )

V3: = C; { Rccz ma z o z ż ą c z n. y c n morów wiezz.chc.ikcv }

{Skonstruuj kolejką priorytetową Q zawierającą wszystkie krawędzie ze for v > V qq

dodaj {v} do o;

zbierz I •

end for;

vhiie I VS I > i do

{wybierz z kolejki {usuń krawędź {v, if (v) i (w) r.aiei

{zastąp W1 i dodaj (v, w)

Q	krawędź
w)	z Qi ;
a	do różn
W 2	w V5 p
do	i. /

ych r zez

(v,

w) c naj zaniejszyiz koszcie};

zbiorów ri 1 i h'2 należących do r»'l O W2} i

then