0000089

Utworzony na podstawie tych cach maksymalny dondryt najdłuższych dróg w taj elecl od wierzchołka x_Q przedstawiony Jeet na rysun-ku 10.5.

10.2.2. Algoryte wyznaczanie dendrytu dróg najkrótszych

Algorytm ten jest identyczny z algorytmem pkt.10.2.1 dla dendrytu najdłuższych dróg, z tye że w ppkt 3° tego algorytmu należy obliczać wartość lewej cechy z wyrażenia

F(x) - min [l(y,x) ♦ F(y)]

9«fV)nC

Przykład 10.3

Blortć dane identyczne jak w przykładzie 10.2 z tym, że jako łuk    przyjmujemy łuk u_ł2. otrzymujemy po zssto -

sowanlu algorytmu z pkt.10.2.2 zbiór ocechowanych wierzchołków C • {^x2**5^,x4'*5’^xg'^x7'*0**g) ^{oroz cech}v przedstawione w tob-e llcy 10.8.

Tablica 10.8

Wyznaczony na podstawie tych coch aakeyaelny dondryt najkrót » •zych dróg, od wierzchołka x₀ w rozpatrywanej elecl. Jeet przedstawiony na rye.10.6.

Algorytmy wyznoczonle makeyaolnych antydendrytów eę lden -tyczne z algorytmoal z pkt.10.2.1 1 10.2.2 Z ty*. Ze należy zmionić zwroty weZyetklch łuków ileal na przeciwne, a wierzchołek x^k traktować jako wierzchołek x^. Po wyznaczeniu odpowied -nich dendrytów należy powrócić dó pierwotnych zwrotów łuków.

W ten epoeób otrzyea sio Zgdane antydendryty.

Na przykład: na ryo.10.7 jeet przedstawiony aekeynalny an-tydendryt dróg najdłuZezych do wierzchołka x^k • x_Ą w elecl Z przykładu 10.1, a na rye.10.6 * dróg najkrótszych.

f

177