DSC00299 (9)

Drogi ekstremalne w sieciach

Problem wyznaczania drogi prostej ekstremalnej jn(xf, j£), łączącej zadany wierzchołek początkowy z zadanym wierzchołkiem końcowym , w sieci skierowanej S ^m < G, {$,}, mjjji} >.

Siecią standardową dla dróg ekstremalnych jest S^m<G, 0, (l }>, gdzie G jest digrafem, / jest funkcją rzeczywistą określoną na zbiorze jego łuków. '

Dla ustalonych wierzchołków M, x* drogą ekstremalną    , X*), spośród

wszystkich dróg prostych łączących te wierzchołki, będzie droga dla której:

F( M*xtr) "    extr F(fl)

**,«*)

przy czym

F(m)- £ t(u)

gdzie:    U(p) - zbiór gałęzi drogi ju,

l(u) - długość luku,

M(, xrj - zbiór dróg prostych fi( 1/,r?) łączących wierzchołek sf Z X*

Ekstremum może byó określone jako minimum ( droga najkrótsza) tub maksimum (droga najdlutsza)

Drogi proste, ekstremalne w sieciach acyklicznych.

Metodologia postępowania:

•    stwierdzenie acykliczności sieci ( np. stosując algorytm Letfmana)

•    przedstawienie digratu w postaci warstwowej

•    metodą programowania dynamicznego wyznaczenie wartości zmiennych decyzyjnych optymalizujących długość dróg

•    zgodnie z zabadąBellmana wyznaczenie dróg ekstremalnych

B Korzon - Algorytm wyznaczania dendrytu dróg najdlutszych (najkrótszych)

Drogi proste, ekstremalne w sieciach cyklicznych.

Algorytm wyznaczania maksymalnego dendrytu dróg najkrótszych.

Procedura algorytmu ma charakter iteracyjny. Polega na przyjęciu dowolnego dendrytu I kolejnej wymianie luków tego dendrytu do momentu otrzymania dendrytu dróg najkrótszych.

Metoda dekompozycji - modyfikacja sieci polegająca na zastąptenlu każdej składowej silnej spójnoict odpowiednim digrafem acyklicznym.