grafy03.pdf

(989 KB) Pobierz

36202310 UNPDF

Stronag“ ó wna

KLASYGRAF Ó WIDIGRAF Ó W Grafyregularne

Stronatytu“owa

Definicja1.42. GrafG=(V,E)nazywamygrafemregularnymstop-

niar,oile 8v2V:d(v)=r.

Spistre–ci

Wniosek1.43. Grafpe“nyK n jestgrafemregularnymstopnian−1.

JJ II

Definicja1.44. Kostk¡r-wymiarow¡nazywamygrafQ r =(V,E),gdzie

J I

V={0,1} r ,

X

Strona 43 z 66

{(a 1 ,...,a r ),(b 1 ,...,b r )}2E df ()

|a i −b i |=1.

i=1

Powr ó t

Wniosek1.45. Kostkar-wymiarowajestgrafemregularnymstopniar.

Pe“nyekran

(0,0,1)

y (0,1,1)

y

(1,0,1) y

(1,1,1)

! ! ! ! ! !

y y

y

@

@

yy

Zamknij

( 0,0,0)

y (0,1,0)

yy

y

@

! ! !

y

y (1,1,0)

y y

@

(1,0,0)

Koniec

Kostkatr ó jwymiarowa

r

36202310.034.png

36202310.035.png

36202310.036.png

36202310.037.png

36202310.001.png

36202310.002.png

36202310.003.png

36202310.004.png

36202310.005.png

Definicje1.46. Grafemwielo–cianuW R 3 nazywamygraf,kt ó rego

wierzcho“kamis¡wierzcho“kiW,za–krawƒdzieodpowiadaj¡krawƒdziomW.

Stronag“ ó wna

Grafemplato«skimnazywamygrafwielo–cianuforemnego(bry“ypla-

to«skiej).

Stronatytu“owa

Spistre–ci

JJ II

J I

Graf4-–cianuforemnego:regularnystopnia3 Graf8-–cianuforemnego:regularnystopnia4

Strona 44 z 66

Powr ó t

Pe“nyekran

Zamknij

Koniec

Graf20-–cianuforemnego:regularnystopnia5 Graf12-–cianuforemnego:regularnystopnia3

36202310.006.png

36202310.007.png

36202310.008.png

36202310.009.png

36202310.010.png

36202310.011.png

36202310.012.png

Stronag“ ó wna

Turnieje

Stronatytu“owa

Definicja1.47. TurniejemnazywamydigrafbezpƒtliD=(V,A),taki»e

Spistre–ci

8u,v2V,u6=v:(u,v)2Aalbo(v,u)2A.

JJ II

(u,v)2Ainterpretujemy: wpojedynkumiƒdzyuavzwyciƒ»y“u

J I

Strona 45 z 66

Tabelaturnieju

1234Pkt.Msc.

1X000 0 IV

21X00 1 III

311X1 3 I

4110X 2 II

Powr ó t

Pe“nyekran

Zamknij

Koniec

36202310.013.png

36202310.014.png

36202310.015.png

36202310.016.png

36202310.017.png

36202310.018.png

36202310.019.png

36202310.020.png

Grafydwudzielne

Stronag“ ó wna

Definicja1.48. GrafG=(V,E)nazywamygrafemdwudzielnym,je–li

istniej¡zbioryniepusteV 1 ,V 2 takie,»eV 1 \V 2 =;,V 1 [V 2 =Voraz

Stronatytu“owa

8u,v2V:u,v2V 1 _u,v2V 2 ){u,v}/2E.

Spistre–ci

ZbioryV 1 iV 2 nazywasiƒpartycjamigrafuG.

JJ II

J I

Strona 46 z 66

Powr ó t

Pe“nyekran

Grafdwudzielnyzpartycjami{1,4}i{2,3}

Zamknij

Koniec

36202310.021.png

36202310.022.png

36202310.023.png

36202310.024.png

36202310.025.png

36202310.026.png

36202310.027.png

Stronag“ ó wna

Problemistnieniaskojarzeniawgrafiedwudzielnym

Stronatytu“owa

Problem1.49. Danyjestgrafdwudzielny(V,E)zpartycjamiV 1 iV 2 ,|V 1 |=

|V 2 |.Czyistniejebijekcja

Spistre–ci

f:V 1 !V 2

spe“niaj¡cawarunek 8v2V 1 :{v,f(v)}2E?

(tak¡funkcjƒfnazywamyskojarzeniem).

JJ II

J I

Mo»liweinterpretacje:

Strona 47 z 66

¶ V 1 zbi ó rpracownik ó w,V 2 zbi ó rpracdowykonania;{v 1 ,v 2 }2Eje–li

pracownikv 1 mo»ewykona¢pracƒv 2 .

· V 1 zbi ó rdziewcz¡t,V 2 zbi ó rch“opc ó w;{v 1 ,v 2 }2Eje–lidziewczynav 1

znach“opcav 2 (tzw. problemkojarzeniama“»e«stw ).

.................................

Powr ó t

Pe“nyekran

Zamknij

Kiedyistniejeskojarzenie?−! twierdzenieHalla

Koniec

36202310.028.png

36202310.029.png

36202310.030.png

36202310.031.png

36202310.032.png

36202310.033.png

Plik z chomika:

Inne pliki z tego folderu:

md07fizA.pdf (561 KB)
md0405fiz.pdf (685 KB)
md0607fizA.pdf (795 KB)
grafy05.pdf (687 KB)
grafy06.pdf (1120 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin