0000086

Funkcję l(u) przedstawia tablico 10.4.

Tablica 10.4

u	^U1	°2	^U3	^U4	^U5	^U6	^u7	^ut)	^u9	c w* O	^U11	^U12	^U13	^U14	^U15	°16	^U17
Mu)	1	1	4	1	2	19	2	1	10	5	27	19	3	6	2	5	13

•Yyznaczyay toroz drogę najdłuższa ₍U_|||0X(x₈.x₄). W tyn celu wyznaczymy kolejno dla 1 ■ 4,3,2.1.0

^fi<^x> ■ _ujb« J^l<^u>^{4 F}I.i<vf^x-^u>0

dop

oraz odpowiadające tonu luki u"(x). ttynlkl przedctawie tablica 10.5.

Tablica 10.5

X	^X4	^X2	^X5	*6	*7	^X9	^X8
i - nr etapu	5	4	4	3	2	1	0
Fj(x)	0	2	1	11	27	30	38
u*(x)	9	^U5	^UG	^U9	^U11	^U13	^U14
y(x.u*(x))	9	^X4	^X4	^X5	^X4	^x7	^X9

Zatea najdłuższa droga    ^XB'^X4^ J^esl droga

{^x8* ^u14* ^xg* ^U13* ^x7' ^UX1* ^X4) o długości F(^_b0X(x_b,x₄)) - F* (Xg) - 30.

wyznoczycy teraz drogę najkrótsza ^^u»in^^xG^,X4^ W tyn celu wyznaczyay kolejno dla 1 • 4,3,2,1,0

^Fi^(,) ’utOⁿJ^^{U) *    ^......^.

<*V

oraz odpowiodajace tanu łukowi u^k(x).

Tablic* 10.6

X	^X4	^x2	*3	^X6	^X7	^X9	^xe
1-nr etapu	5	4	4	3	2	1	0.
^(x)	0	2	1	4	17	9	17
u*(x|	9	^U5	^ue	^u7	^U17	^U16	^U14
y (x. u* (x))	9	^X4	^X4		^X6	^X6	^X9

Zotea nejkrótszę dróg#    ^x8^,x4) ^{J#łt dr}°⁹®

(x₀. u₁₄. x₉, u_l6. x₆. u_?. x₂. u₅, x₄J

o długości F^_Bln(x_e.x₄)) • x₀) • 17.

Koniec przykładu.

W zoetosowoniech praktycznych bardzo często wymagana Jest wyznaczani* nla jednaj drogi ekstromalnej łęczęcaj dwa zadana wierzchołki, lecz całego zbioru dróg ekstremalnych, od pewnego wierzchołko x^p do wszystkich wierzchołków osiągalnych z wierzchołka x^P.

Odmianę tago zadania jast zadanie wyznaczenia dróg eketremal -nych do uatalonago wierzchołka x^k ze wszyatkich wierzchołków, z których ten wierzchołek jest oolęgalny. Z zadaniami tago typu spotykamy olę na przykład w metodach sieciowych PERT 1 CPM,Algorytmy służęee do rozwtęzywania takich zadań dla sieci acyklicznych sę opracowane przy wykorzystaniu nastfpujęcago twierdzenia.

TWIERDZENIE 10.1

Każdy odcinek drogi ekstremalnej w sieci acyklicznej jest drogę eketremolnę.

Dowód

Załóżmy, że istnieje droga akstreaalne (^u#xtr(*^P.x^k) akło-dajęca się z trzech odcinków A. B, C 1 odcinek B •(^u(^xr*^xB)

171