0000081

X* I • X^,v/{x_fJ . gdzie x_r« X^ha e_fk • 1 X"i • x\x' i w « e u'o(u_k} ;

Dciii X^ł • X. to okok do ®.

Skok do (i) .

® T*i - <X.U'.P'> .

Rozdział 10

DROGI PROSTE EKSTREMALNE W SIECIACH SKIEROWANYCH 10.1. Drogi akatraaalna

Będziemy zajmowali olę metodami wyznaczania odpowiedniej drogi proataj łgczycej zadany wiarzchołak początkowy x^p z zadanym wlarzchołklaa końcowym x* w alecl aklarowantj    ^

^s ’<⁶- {?il •

warto przypoaniac. że w aiacl aklarowanaj graf G jaat dlgrafaa, a droga proata aa z definicji wszystkie wierzchołki różne.

Określimy obecnie pojęcia drogi akatraaalnaj. Każdej drodze możemy przypisać liczbę określony jako wartość odpowiedniej funkcji wartości ^ oraz    ^dł* wierzchołków 1 gałęzi two-

rzęcych tę drogę, w najproatazym przypadku, jebali w alecl sklarowanej S ■<G,p,{l\) funkcja l(u) określa długość łuku u, to takę liczbę charakteryzujęcę drogę może być jej długość określona jako suaa długości jej gałęzi.

Oetell dla ustalonych wierzchołków x^p 1 x^k weźmiemy pod uwagę wezyetkie drogi proste    ) łęczyce te wierzchołki,

te wśród nich motamy wybrać drogę najkrótszy lub najdiutazę, to znaczy skatremalnę.Na przykład.w tak zwanych metodach sieciowych planowania przedsięwzięć, znanych pod nazwami PERT 1 CPM wyko -rzyetuje się aparat dotyczęcy wyznaczania dróg prostych najdłuższych w takiej prostej sieci, której dlgraf G nie zawiera dróg cyklicznych.

Ogólnie, drogę prosty ekstremalny <^axtr (***«* ) określimy następujycot Niech na zbiorze M dróg prostych <u. w sieci S • <G.    . (Vj}> będzie określono

161