DSC00285 (5)

ŁAŃCUCHY, DROGI W GRAFACH

Marszruto - dowolny ciąg przemienny wierzchołków i gałęzi.

Długością marszruty nazywamy liczę gałęzi (/) występujących w ciągu określającym marszrutę.

Marszrutą skierowaną nazywamy marszrutę, w której posuwając się po gałęziach grafu, będących kolejnymi gałęziami marszruty skierowanej, przechodzimy przez każdy łuk zgodnie z kierunkiem . strzałki przedstawiającej ten łuk w interpretacji graficznej.

Marszrutą cykliczną nazywamy każdą taką marszrutę o długości l> 0 dla której wierzchołek początkowy jest jednocześnie wierzchołkiem końcowym.

Łańcuch Łfsf,zł) - marszruta łącząca wierzchołek początkowy jf z wierzchołkiem końcowym x, w której wszystkie gałęzie są różne Łańcuchem prostym nazywamy łańcuch o różnych wierzchołkach.

Łańcuchem cyklicznym (cyklem) nazywamy każdy taki łańcuch o długości l>0 dla którego wierzchołek początkowy jest jednocześnie wierzchołkiem końcowym.

Cyklem prostym nazywamy taki cykl, w którym jedynie x a poza tym wszystkie wierzchołki i gałęzie są różne.

Droga p - łańcuch skierowany, tzn. marszruta skierowana o różnych gałęziach.

Analogicznie - droga cykliczna (kontur), droga prosta, droga cykliczna prosta

Łańcuch najkrótszy (xf, x* ) - łańcuch zawierający najmniejszą liczbę gałęzi spośród wszystkich łańcuchów łączących x^f z Akp.ryfini

1.    Wierzchołek y oznaczamy cechą zero.

2.    Dla wszystkich wierzchołków ocechowanych cechą k, cechujemy wszystkie nieocechowane, przyległe do nich wierzchołki cechą k+1. Jeżeli pozostały jeszcze nieocechowane wierzchołki, to powtórnie realizujemy punkt 2, dla zwiększonej o jedność wartość aktualnej cechy k.

3.    Tworzymy łańcuch najkrótszy Ł^, (ć,jł) poczynając od wierzchołki końcowego x*, który ma cechę równą /. Jako gałąź u, bierzemy dowolną gałąź wiążącą wierzchołek x* z wierzchołkiem o wartości cechy równej Ul. Proces wybierania kolejnych (od końca do początku) gałęzi kontynuujemy analogicznie, aż dojdziemy do wierzchołka tł oznaczanego cechą równą zero. Długość tego łańcucha / jest równa wartości cechy wierzchołka x*.