grafy02.pdf

PODGRAFY

Stronag“ ó wna

Definicja1.15. ParƒG 0 =(V 0 ,E 0 ),gdzie

V 0 V,E 0 {i,j}2E:i,j2V 0

Stronatytu“owa

nazywamypodgrafemgrafuG=(V,E).Je–li

E 0 = {i,j}2E:i,j2V 0 ,

Spistre–ci

JJ II

toG 0 =(V 0 ,E 0 )nazywamypodgrafemindukowanymprzezpodzbi ó rwierz-

cho“k ó wV 0 .

analogiczniedefiniujemypodgrafyipodgrafyindukowanedla digraf ó w

J I

Strona 17 z 42

Powr ó t

Pe“nyekran

Zamknij

grafijegopodgrafindukowanyprzezzbi ó rwierzcho“k ó w{2,4,5}

Koniec

Izomorfizmgraf ó w

Stronag“ ó wna

Definicja1.16. Dwagrafy(digrafy)G 0 =(V 0 ,E 0 )iG 00 =(V 00 ,E 00 )nazywamy

izomorficznymi(ozn.G 0 'G 00 ),oileistniejetakabijekcjaf:V 0 !V 00 ,»e

odpowiednio {i,j}2E 0 ,{f(i),f(j)}2E 00 ,

(i,j)2E 0 ,(f(i),f(j))2E 00 .

Stronatytu“owa

Spistre–ci

JJ II

Przyk“ad1.17. Dwagrafynieizomorficznemog¡mie¢tensamci¡g

grafowy!

J I

dwagrafyregularnestopnia3o8wierzcho“kach

Strona 18 z 42

Powr ó t

Pe“nyekran

Zamknij

Koniec

Macierzowereprezentacjegraf ó w

Macierzeincydencji

Stronag“ ó wna

Stronatytu“owa

Definicje1.18. Macierz¡incydencjigrafuG=(V,E),V={1,...,n},

E={e 1 ,...,e m },nazywamymacierz

I(G)= a ij n×m ,

Spistre–ci

gdziedlai=1,...,n,j=1,...,m

JJ II

a ij =bi2e j e.

J I

wierszeodpowiadaj¡wierzcho“kom,kolumnykrawƒdziom(“ukom)

Strona 19 z 42

Macierz¡incydencjidigrafuD=(V,A),V={1,...,n},E=

{a 1 ,...,a m },nazywamymacierz

I(D)= a ij n×m ,

Powr ó t

gdziedlai=1,...,n,j=1,...,m

Pe“nyekran

( ba j =(i,k)e−ba j =(k,i)eje–lia j 6=(i,i)

a ij =

je–lia j =(i,i)

Zamknij

Koniec

Stronag“ ó wna

Przyk“ady

Stronatytu“owa

11100

10010

00000

01000

00111

00001

6 6 6 6 6 4

7 7 7 7 7 5

Spistre–ci

I(G)=

JJ II

J I

Strona 20 z 42

11−11000

−1000100

0000020

0−100000

001−1−101

000000−1

6 6 6 6 6 4

7 7 7 7 7 5

Powr ó t

I(D)=

Pe“nyekran

Zamknij

Koniec

Definicja1.19. Macierznazywamyca“kowicieunimodularn¡,je–lika»dy

jejpodwyznacznikjestr ó wny−1,0b¡d„1.

Stronag“ ó wna

Twierdzenie1.20. Macierzincydencjika»degodigrafubezpƒtlijestmacierz¡

ca“kowicieunimodularn¡.

Stronatytu“owa

Spistre–ci

Dow ó d indukcjazewzglƒdunawymiarpodwyznacznika|Q|.

SkorodigrafDniemapƒtli,toI(D)sk“adasiƒwy“¡czniezelement ó wr ó wnych

−1,0b¡d„1.Je–lizatem dimQ=1 ,totwierdzeniejest(oczywi–cie)prawdziwe.

JJ II

Za“ ó »my,»e|Q|2{−1,0,1}je–li dimQ=n irozwa»mypodmacierzkwadra-

tow¡Q,

J I

dimQ=n+1.

Strona 21 z 42

Mamytrzymo»liwo–ci:je–li

¬ Qmakolumnƒsk“adaj¡c¡siƒzsamychzer )|Q|=0.

Powr ó t

Qmakolumnƒzawieraj¡c¡dok“adniejedenelementniezerowy ,torozwijaj¡c

|Q|wzglƒdemtejkolumnyikorzystaj¡czza“o»eniaindukcyjnego,otrzymu-

jemytezƒ.

® ka»dakolumnaQmadwaelementyniezerowe ,tosumuj¡cwszystkiewiersze

Qdostajemywierszzerowy)wierszeQs¡liniowozale»ne)|Q|=0.

Pe“nyekran

Zamknij

Koniec

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: