0000029

Zatem hlporgrof ma trzy bazy minimalna, określono podzbiorami wierzchołków {l.3} , {2.3.5)    1    (3,4.5)

M^ł •<X^ł.U¹.P¹> ; X¹ - (ł.s) l U¹ • (c) i P¹ ■ {<3.3.c>] H² . <X²,U².P²> i X² - {2.3,5) ; U² - {b.c.e}

P² - {<3.2.b> . <3,3.c> . <2.3.5,a>)

H³ - <X³.U³.P³> ; X³ - {3.4.5) i U³-{c)|    P³-{<3.3.C>)

Najmniej liczno bożo tego hlpargrafu jeat H¹, o liczba bazowa tf(H) • 2. Oazo to joat graf zdogenarowany o dwóch wierzchoł -koch i jodnej pętli. Grafom joot równloż H³.

Przykład 3.6

Wyznaczymy wazyatkia bazy minimalna grafu z rya.2.3. Binarna macierz lncydancjl togo grafu jaat naatępujoca

abcda fghljklmnop

-u

^f(*⁹) ■ (*₁)(*₁)(*₁*^₃)(*₁^<*3)(X2^4X3H^^<^)(*2^4X4⁾

(>v*5)(< ^x5*^xe) *    (^x>**6) *    (^x4*^x0)

t^X6^4X8 K ^xg) -

■    (^xi)(^x2*^x3)(^x2*^x4 H^x4*^x5*5**6)(^X4*^X0 ^ ^X6*^X8^^x9^

• (*₁)(*2*^X3^%X4)(^X5^4X4^X6^^X8^4X4^X6^)<X9⁾ *

■    (X₁)(*₂tx₃x₄)(*₄x₆4*₅x₈)(x₉) -

^X1^X2^X4^X6^X9

^Xi^X2^X5^X0^X9

♦ x_łx₃x₄x₆x_ę

♦ X₁X₃X₄X₅X₀Xę

Zatem graf z rys.2.3 ma cztery bazy minimalne, okreólone pod -zbiorami wierzchołków {1,2 .4,6,9} , {i,2.5,8,9} , {l.3.4,6,9} i {l,3.4,5,8,9} . Trzy z nich eg bozanl najmniej licznymi, zo-wlerajgcymi po pigć wierzchołków. Oznocza to, że liczbo bozowo grofu (f(G) ■ 5.

Wyznaczone bazy minimalne sq przedstawione na rysunkach 3.4-3.7.

©CD

Rys. 3.4

Rys.3.5

57