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 S1 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 AD 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 xk). 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 AU , ę(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 AU.
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
Wyszukiwarka
Podobne podstrony:
18 Część I - Zadania Dowód. Przypuśćmy, że istnieją tylko następujące liczby pierwsze: pi , P2 , ...
Poznaj C++ w$ godziny0023 Zaczynamy 7 C++ to nie tylko lepsze C Prawdą jest, że C++ to rozbudowane C
7. Udowodnić, że istnieje liczba postaci 333333833338n, gdzie n jest liczbą
CCF20090831 149 274 Rozum nienie, że istnieje określona liczba gatunków kategorii, jest już nowym za
Dowód ontologiczny na istnienie Boga Dowody istnienia Boga miały ze wszystkich pomysłów Anzelma najw
14 Wielościany Dowód. Niech p G dW Istnieje zatem ciąg punktów pi,p2, ■■■ $ W taki że g(pi,p) < -
Scan1 2 Sbv>4 H(JPV6 czofź roionnu ć ROZDZIAŁU O pochodzeniu idei Każdy z łatwością przyzna, że i
Dowód: Pokażemy najpierw istnienie stosownej pary. Załóżmy, że b > 0 i zdefiniujmy q — [
Każdy podzbiór zbioru niesprzecznego jest niesprzeczny. DOWÓD Załóżmy, że X Q Y, Y e NSP oraz X e NP
z wyjątkiem argumentu, który wykazuje, że dowod nie istnieje; bowiem tylko on sam jest dowodem. A je
Foto 0084 7. Klucz publiczny RS A to (n,e) = (65,7). Znajdź klucz prywatny. S. Wiadomo, że istnieje
KANCELARIA PREZESA RADY MINISTRÓW Przyjmuje się, że istnieją trzy niezbędne warunki procesu
więcej podobnych podstron