0000041 2

Przy tuk określonych etapach i funkcji celu równej długości łaiV-cucho. nietrudno wykazać opołnlenle warunku Oelleana 1 tym ea -ey* uzotednlć tooretycznle nostępujęcy algorytm.

Algoryta wyznaczenia łańcucha najkrótszego £(x^p,x^k)i

1° Wlerzchołok x^P oznaczaay cecho c ■ 0.

2° Dlo kaZdogo wierzchołka x ocechowanego cecho c ■ k, cechu-jeay wezyetkle nieocechowane do tej pory i przyległe do x wierzchołki cecho c ■ k ♦ 1.

DoZoli Jeszcze lstnlejo nieocechowane wierzchołki epójne z x^p, to powtarzany punkt 2°.

3° Poczynajoc od wierzchołka końcowego X*¹, który ma cechę c • 1. wybleromy dla kożdogo wierzchołka x o cesze c • k dowolno. Jedno gałę*. 1oczqcq ten wierzchołek z wierzchoł-klea o ceeze c ■ k - 1.

Clog wybranych w ten epoaób gałęzi 1 lncydontnych z nimi wierzchołków okrośla łańcuch najkrótszy

L

Uługodć tego łońcucha 1 jost równa wartoóci cechy wierzchołka x .

Długość łońcucho najkrótszego •£_(Bi_n(^x^»^xk) ®oZomy traktować Joko odległość wierzchołka x^k od wierzchołka x^p, a saa łańcuch jako nojkrótsze polęczonle między tymi wierzchołkami. Zau-woZay, Ze opisany wyZej algoryta wyznacza wszystkie najkrótsze połęczenla wierzchołka x^P z pozostałymi, spójnymi z wierzchołkiem x^p, wierzchołkami grafu.

Dla wyznaczonla tych połęczoń naleZy procedurę punktu 3° zastosować dla każdego ocochowanego wierzchołka, to znaczy wybrać dla każdego ocechowanego wierzchołka cechę c ■ k jednę gałęZ, łęczęcę ten wierzchołek z wierzchołkiem ocechowanym cechę c »

• k - l. Zbiór wybranych gałęzi określa graf częściowy naj -krótozych połęczeń z wierzchołkiem x^p.

Przykład 5.1

Za pomocę opisanego algorytmu, wyznaczymy najkrótsze po -łęczenla wierzchołków z wierzchołkiem x₇ w grafie przodstewlo-nye na rys.5.1.

Ryt.5.a

Wartości cech oznaczono llczbaai przy wierzchołkach, a wybrane w punkcie 3° olgorytnu gałęzie pogrubiono.

Warto zauważyć, że może istnieć wiele różnych grafów czyścio -wych, określejycych najkrótsze połyczenia z wybranym wierzchołkiem *P.

5.5. Metryka grafu (hipergrafu)

Długości najkrótszych łańcuchów mogy stanowić metrykę zbioru wierzchołków grafu (hipergrafu).

Oznaczymy

¹ [^ain^^x'^yj] gdy x,y spójna °® gdy x,y nie ey spójna

Funkcja f spełnia własności metryki

^ł° ?(*.y) ■ ⁰ <■* * ■ y

2° A?(*.v) ■ p(y.*)

3° A p(*.y) ♦ p(y.*) > ?(*.*)

*>y.*

61