90979

Definicja 5

Ścieżką nazywamy ciąg różnych krawędzi takich, że dwie kolejne krawędzie w ciągu są incydcntnc względem tego samego wierzchołka.

Definicja 6

Cyklem nazywamy ścieżkę, której początkowy wierzchołek zbiega się z końcowym wierzchołkiem pierwszej i ostatniej krawędzi.

W grafie spójnym skierowanym mającym N wierzchołków i M krawędzi, każdemu cyklowi C_y przyporządkowano m - wymiarowy wektor

C, [c,,,... C_w ]'. gdzie:

a* - a~ jeśli krawędź u* jest „przechodzona" a* razy w kierunku Cjj =    zgodnym z jej orientacją oraz CC] w przeciwnym

0    jeśli Uj nie jest częścią cyklu

Dla grafu z rys. 2 wektor Cj odpowiadający cyklowi C_f - [ui, U2, U3, U4, U2, Uń]¹ jest równy

Ć, = fl. -2, -1, 1,0,1,0]^T.

Definicja 7

Macierz T [tij] wymiaru NxM nazywamy macierzą incydencji wtedy, gdy:

-1 gdy Uj „wychodzi" do wierzchołka Vj, tij= +1 gdy Uj „wychodzi" z wierzchołka Vi,

0 gdy Uj nie ma końca w wierzchołku Vj.