0000038

Droga cykllczno p r o a t a - droga cykliczna, w której wozyotkio wierzchołki tę różne z wyjętkiom

^x‘. ’ V

TWIEKOZEN1E 5.1

Elononty r[^k^ k-tej potęgi aaciorzy R przylogłoóci wierzchołków grafu (hiporgrafu) C ■ <X,U,P>    09 równe

lloóci różnych morezrut w tym grafie (hlporgrafie ), o długoócl k, łęczgcych wierzchołek x^ z wierzchołkiem Xj,

Dowód (indukcyjny)t

Dla k • 0 toza Jeet prawdziwa. Dla k ■ l teZ Jeot prawdziwo na mocy definicji macierzy przylogłoóci. Załóżmy, że teza Jeet prawdziwa dlo k 1 wykażomy, że przy tym założonlu Jeot prawdziwo dlo k ♦ i.

Weźmy pod uwagę wierzchołki ^xi*^xc /    » ■ l*n, x^. wortoóć r_c^

oznacza lloóć gałęzi łęczęcych wiorzchołek x_# z x^. a wortoóć r^) z zołożonla lloóć różnych martzrut o długoócl k łęczęcych x_ł z x_o. Otrzymujemy zatem, że fjr^ r_ft^ równo r[*⁴¹)

okreólo lloóć norezrut o długoócl k ♦ 1 łęczęcych wierzchołek . x_A z wierzchołkiem x^.

TWIERDZENIE 5.2 (KOnlg)

Graf bez pętli Jeot grafem dwupodzielnym wtody 1 tylko wtody, gdy nie zawiera marozrut cyklicznych o nieporzyotej długoócl.

Dowód tego twierdzenia można znaleźć w [53].

TWIERDZENIE 5.3

Elemonty p^ k-toj potęgi macierzy przejóć P grafu (hiporgrafu) C • <X,U,P> oę równe iloócl różnych marozrut akierowonych o długoócl k. łęczęcych wiorzchołek x^ z wierzchołkiem *y

Dowód t

Dla k • O 1    1 toza twierdzenia Jaet prawdziwa na mocy

definicji macierzy przejóć i aarazruty oklorowonej. Przy założeniu prowdziwoócl tezy dla k otrzymujemy, podobnie Jak w do -wodzie twierdzenia 5.1, prowdzlwoóć tozy dla k ♦ 1.

Dędzleay oznaczalit

M(k_a,Xj) - aarazruta łącząca x_i z x^ j Jt.(x₁.Xj) - łańcuch łączący x_i * x^ /

^u(x₁,Xj) - droga o początku m x_i l końcu » Xj,

Użyteczne oą następujące, oczywisto twierdzenie. twierdzenie 5.4

V    h • h^.Kj)    4!(x₁,x_J)

TW1EROZENIE 5.5

V    . H - M(X_AX )<—.

MsMorowuna ¹ J <u ^{(    J}

TWIERDZENIE 5.6

V <«<(X₁.K_J) <=* V /p(*i»^xjł *    ^rfp proity

TWIERDZENIE 5.7

5.2. Spójność grafu 1 hiporgrafu

Graf (hlpergraf) G • <X,U,P> nazywany o p ó J n y a wtody i tylko wtody. gdy dla katdoj pary wierzchołków x,y e X lttniojo marszruto M(x,y), Nlo każdy graf joot spójny.

Dla dowolnogo grafu wprowadźmy relację spójności 5CX»X określoną następująco

<x.y>£S«-» V H - M(x,y)

M

Ł-atwo wykazać, że rolacja ta joot zwrotna, symetryczna i przechodnia. Oost to zatoa relacjo równoważności, dzielące zbiór

75