0000057 2

TWIERDZENIE 7.4

Niech .....Hj.....H_x będę składowymi spójności

hlpergrafu H, o liczbach cyklonatycznych A^).

Wtedy

M») • £mV

l»f

Dowód >

A(H.) " ZZ [MO - li ♦ 1 - n(H )

UjCU,^{1, J    J}

Sunujęc po składowych opójnoócl (i <• 1.3C) otrzyaujeay tezę twierdzenie (patrz wyrażenie (7.1)).

7.2. Lasy 1 drzewa

L e s e n nazywany każdy graf C. dla którego A(G) • 0. Odpowiednio hiperleeen nazywany hlpergraf H taki, że A(H) • 0.

D r z e w e a nazywany las, dla którego jf(G) • 1. Od-powiodnio hlperdrzewea    jest hiperlas M, taki

że X(H) - 1.

Zauważmy. że każdy dendryt (antydendryt) jeet drzewen. Każde drzewo o n wierzchołkach aa dokładnie n-1 gałęzi. Oczy -wiście żadna z gałęzi drzewa nie jest pętlę.

TWIERDZENIE 7.5

Dla dowolnych dwóch wierzchołków drzewa (hiperdrzewa)

istnieje dokładnie Jeden łańcuch łęczęcy te wierzchołki 1 jest on łeńcuchen prosty®.

Dowód i

Drzewo (hiperdrzewo) Jest spójne, a więc dla każdych dwóch wierzchołków x.y istnieje «£(x,y). Gdyby nie był on łeńcuchen prostya, to wyotępowałby cykl, co Jest niemożliwe ze względu na A» O l twierdzenie 7.2. Gdyby ilość różnych łańcuchów łęczęcych x i y była większa od jedności, to toż Istniałby cykl, co jest niemożliwe 1 kończy dowód twierdzenia.

Dis każdych dwóch różnych hlporgołęzl Uj.u^ hipor -drzewa ilość wierzchołków lncydentnych Jednocześnie z tymi gałęziami nie przekracza jedności.

Dowód i

Oznaczmy przez Ej zbiór wierzchołków lncydentnych z hl -pergałęzię Uj. Załóżmy, że

Oznacza to, że Istnieję dwa wierzchołki x,y takie, że x€Ej, yCEj, xc E_k, ye E_k. Iotnieje wtedy łańcuch cykliczny. |x, Uj, y, u_k,x J , co jest niemożliwa wobec A* O 1 twierdzenia 7.2. Kończy to dowód twierdzenia.

TWIEROZENIE 7.7

Dla każdej hlpergałęzi u hlperdrzewo H ■ ,<X,U P> wektor X , taki że < % . u> e P ma różne składowe.

Dowód t

Załóżmy przeciwnie, że istnieje <*, u>£P 1 X*

• <x₁»...,y....,y.... ,x_k> . wtedy Jednak istniałby łańcuch cykliczny {y.u.y} , co Jeot niemożliwe ze względu na X(H) • O 1 tezę twierdzenia 7.2.

TWIEROZENIE 7.8

Niech H ■ <X.U,P> będzie hlperdrzewem, |U| ■ a, •

* {£<} t 1 ■ iT» Jest rodzinę podzbiorów wierzchołków lncydentnych z poszczególnymi hlpergełęzlaml. Wtedy szkielet tego hlperdrzews M_o ■ <X,U_§,P_#> ma również m hiperkrawędzl |U_BI ■ m 1 przy zachowaniu odpowiedniej numeracji Ej • E®, gdzie Ej Jest zbiorem wierzchołków lncydentnych z hiperkrawędzlę

“S«v

Oowód tego twierdzenia wynika bezpośrednio z definicji szkieletu 1 hlpergrafu zwykłego, podanych w rozdziale 2.