DSC00303 (8)
ip.ł. DROPI PROSTR. BK3TKBMAŁNB W SIECIACH ACYKLICZNYCH
10.2.1. Algorytm wyznaczania maksymalnego dendryta dróg najdłuższych Dant
Sieć skierowana bez dróg cyklicznych o postaci:
$*<(?. 0,{/}>, C7-<»',r>; r:W-2W\ ŃŚ*R;
Um{<x,y):(x, y*W)A(y*rx)}; xp— wierzchołek początkowy (korzeń dendrytu).
Proceduro
1. Wyznaczamy warstwy digrafu G: JV0, Wit, Wt. Oznaczamy przez i numer warstwy, do której należy wierzchołek x’\ x*e Wt. K — oznacza numer ostatniej warstwy.
2. Będziemy cechowali wierzchołki xefV cechami podwójnymi (F(x), g(x)).' W tym celu przez C oznaczymy zbiór wierzchołków, które są aktualnie ocechowane. Zadanemu wierzchołkowi xp nadajemy cechę (0, 0), to znaczy F(xf) -»0/g(xO «■ 0. W tej chwili C— {xp). Podstawiamy i««i +1.
3. Pytamy: czy i>Kl
NIE: Bierzemy pod uwagę warstwę Wt (następną w kolejności) oraz takie wierzchołki xeW,, dla których zbiór ocechowanych poprzedników nie jest pusty, /'J1 r\C # 0. Dla każdego wierzchołka xe Wlt którego zbiór ocechowanych poprzedników nie jest pusty, obliczamy wartość lewej cechy
/■(*)« max [l(y, x)+F(y)]
Jako wartość prawej cechy g(x) wierzchołka * przyjmujemy ten wierzchołek y, przy którym powyższe wyrażenie przyjęło wartość ekstremalną.
C«Cu{x}
Po rozpatrzeniu wszystkich wierzchołków xe Wx podstawiamy ii-ł + 1 i przechodzimy do punktu 3.
;TAK: Przechodzimy do punktu 4 (rozpatrzone zostały wszystkie warstwy).
4. Zbiór ocechowanych wierzchołków C jest zbiorem wierzchołków osiągalnych z wierzchołka x*, to znaczy stanowi zbiór wierzchołków maksymalnego dendrytu najdłuższych dróg, wychodzących z wierzchołka xp, w sieci S. Długość najdłuższej drogi z xp do dowolnego wierzchołka xeC określona jest wartością lewej cechy F(x) tego wierzchołka. Drogę tę wyznaczają prawe cechy wierzchołków, poczynając od wierzchołka x i przesuwając się do wierzchołka x’t przeciwnie do zwrotu łuków (od końca). Znajdując w ten sposób antydrogi do wierzchołka x* dla każdego wierzchołka x«C, wyznaczamy cały dendryt maksymalny najdłuższych dróg w sieci S, od zadanego wierzchołka xp, Praktycznie należy do każdego wierzchołka x doprowadzić jeden łuk od wierzchołka określonego wartością prawej cechy g(x).
Wyszukiwarka
Podobne podstrony:
DSC00304 (9) 10,3. OROOl PROSTE, ■KmUlMAt.Nt W SIECIACH CYKLICZNYCH 10.3.1. Algorytm wyznaczania mak
DSC00319 (7) 11.1.1. Algorytm wyznaczania maksymalnego przepływu Dane SieiS-<<M«},{h)>; g
SOISK81 Adresowanie IP Adres sieci dla komputera o adresie 10.20.30.140 obliczamy, jak na rys.
DSC00328 czynnik rozszerzalności termicznej B jest mniejszy niż A. 10. Moduł Younga dla polimerów am
DSC00370 ip PyfiljS tjStiJKSuKArftŁe. L tłLcfcujiJLA
1i 62 S 8 (9.17)10. OGRANICZANIEPRĄDÓW ZWARCIOWYCH W SIECIACH PRZEMYSŁOWYCH 10.1. MOCE ZWARCIOWE W
DSC00322 Imię i Mitobta: .............Cili {wie* Zadani 1 (ma* 10 p.) J Żądanie 2 (ma*, 10 p.) I Zad
skrypt081 (2) 160 Laboratorium Podstaw Elektrotechniki l n także: Ia* + C + 1c* = 0 &nbs
kscan97 Rys. 10.21. Wyznaczanie PK miareczkowania Rys. 10.22. Wyznaczanie PK miareczkowa-potencjome
^12V ^ 10 Q Przykład. Wyznaczyć punkt pracy diody 1N941 w podanym układzie oraz moc traconą przez b
10 (84) 2. Wyznaczam całkowity moment obrotowy Ma M^-100% Mj. - 60% 100% 100% 60% 60% M. = M.--= 13/
202 203 202 X V 5.11.5. Mnożenie binarna Jak pamiętam? (patrz p. 1.2.10), algorytm
więcej podobnych podstron