0000133

Dowód t

Zołóżny. że w T(B) istnieje cykl. Każdy wiorzchołek grafu jest lncydentny z parzysto llościę gołęzl togo cyklu. Sumujęc wtzyotklo kolumny noleżęce do S, otrzymujemy zerowy wektor kolumnowy. a więc wektory z S byłyby wtedy liniowo zależna.

Załóżmy teraz, że T(S) nie zawiera cykli. Weźmy dowolny,

nlopuaty podzbiór S¹ C S. któremu odpowlodo graf częóciowy T(5^ł )

bez cykli, zowlerajocy przynajmniej Jeden wierzchołek wlezęcy

x. . ponieważ S'/ f) . W macierzy A^D na przecięciu wlereza x.

K    ,    Q    ^R

z kolumnami ze zbioru S, dokładnie jeden element a^ / O

(Uj jest gałęzie lncydentnę * wierzchołkiem x_k). Zatem suma fco-lumn s' nie Jest woktorem 0 . W ton spoeób żadon nlepuety podzbiór s'cs nie etanowi woktorów liniowo zależnych 1 tym ea -mym S Jeet zbiorem wektorów niezależnych. Kończy to dowód le -matu.

wniosek ls Kolumny w A° # odpowiadajoco gałęziom dowolnego karkaeu oę liniowo nlozależne. Dożęli zatem wybierzemy z A^U , ę(G) kolumn liniowo niezalożnych, to gałęzie odpo -wladajęce tym kolumnom będę tworzyły karkas.

Lemat D.3.2

Podzbiór kolumn o liczności f(G) macierzy A° grofu G zawiera kolumny liniowo niezależne wtedy 1 tylko wtedy, gdy odpowladajocy mu podzbiór gołęzl tworzy karkoo grafu G.

Dowód tego lematu wynika bozpośrodnio z łomotu 0.3.1 1 do-finicjl karkaeu.

Wiadomo, że mekoymolno ilość liniowo niezależnych kolumn macierzy A jeet równo oakoymalnej ilości liniowo niezależnych wlerezy toj macierzy 1 Jeot równa rzędowi tej macierzy rz(A). (patrz np. [36], rozdział V, § 2), a rzęd macierzy A nie zależy od ciała, nad którym jest ona określona.

Lemat 0.3.3

Rzęd macierzy A°(G) jeet równy $>(G).

O o w ó d >

Oodanie do karkaeu dowolnej Jego cięciwy powoduje powoto -nie grafu częściowego, zawierojęcego cykl (patrz twierdzenia 7.13. 7.11 1 7.3). Zotee najliczniejeży zbiór liniowo niezoleż-nych kolumn noclorzy A ma llczność dokłodnle ■ n(C) - <£(G). Kończy to dowód łomotu.

?(C)

V/ n 1 o o o k 21 Makoymalno ilość liniowo nlozależnych wierszy macierzy A° jest równo f(G).

Lornet 0.3.4

Podzbiór wierszy macierzy A° o llczności ^ ■ n - dt jest liniowo niezależny wtedy i tylko wtedy, gdy pozostałe wierszo w ilości X odpowiodoję wierzchołkom grafu wziętym po Jednym z każdoJ okładowej spójności tego grofu.

Dowód i

V/ kożdoj ko.lumnlo macierzy A°(G) grafu G boz pytli ty do-kłodnie dwie Jedynki. Wiersze, w których występuję te jedynki, odpowiadeję wierzchołkom naleźęcym do tej samej składowej spój-ności. Zatem suma (modulo 2) wierszy odpowiadajęcych wszystkim wierzchołkom skłodowej spójności Jest równa woktorowi 0 , a zo tom zbiór tych wiorozy stanowi zbiór wierszy liniowo zależnych.

Zouważmy na podstawie łomotu 0.3.3 i definicji drzewa, że utuwojęc z tokiogo zbioru Jeden, dowolny wiersz dostajemy zbiór pozostałych wierszy liniowo niozoleżnych, ponieważ dla grafu spójnego o n wierzchołkach, moksymalna ilość gałęzi nie two -rzęcych cyklu jeet n-1. Oloręc pod uwagę, żo trzeba uounęć X wierszy, musimy usunęć wiersze odpowledajęce wierzchołkom wziętym dowolnlo po jednym z każdej skłodowej spójności. Kończy to dowód lematu.

Wniosek 3: Ustolojęc zbiór niezależnych liniowo wierszy mocierzy A° o numorach {^.....i^j * " ilości • n - jc . możomy dobrać na wiola sposobów podzbiór ę kolumn, które będę tworzyły wraz z tymi wierszami miner nlozerowy (rzędu ę>) wtedy 1 tylko wtedy, gdy kolumny będę odpowiadały gałę -złom karkasu.'

w n i o o e k 4i Podzbiory liniowe niezależnych kolumn, określajęce karkasy grafu G, nie zależę od podzbioru wybranych, niezależnych liniowo wierszy { ij.....i^} macierzy A^U.

Wniosek 5t Ilość różnych karkasów grafu G jest rów na ilości niozerowych minorów rzędu ę(G) noclorzy A°, tworzonych przy jednym, ustalonym podzbiorze liniowo niezależnych

W.....M •

265