grafy04.pdf

(1050 KB) Pobierz
36212052 UNPDF
Stronag“ ó wna
Grubo–¢grafu
Stronatytu“owa
maln¡liczbƒn,tak¡»edlapewnychzbior ó wkrawƒdziE 1 ,...,E n , S n i=1 E i =E,
ka»dyzpodgraf ó w
Spistre–ci
(V,E i )
JJ II
i=1,...,n,jestplanarny.
J I
Wniosek1.72. t(G)=1wtedyitylkowtedy,gdygrafGjestplanarny.Ponadto
t(K 5 )=t(K 3,3 )=2.
Strona 66 z 88
Powr ó t
Pe“nyekran
t(K 6 )=2
Zamknij
Koniec
Definicja1.71. Grubo–ci¡grafuG=(V,E)(ozn.t(G))nazywamymini-
36212052.032.png 36212052.033.png 36212052.034.png 36212052.035.png 36212052.001.png 36212052.002.png 36212052.003.png
Stronag“ ó wna
Chapter2
Stronatytu“owa
Drogiicykle
Spistre–ci
JJ II
DROGIICYKLEEULERA
J I
Definicje2.1. Drog¡Eulerawgrafie(digrafie)G=(V,E)nazywamydrogƒ
prost¡przechodz¡c¡przezwszystkiekrawƒdzie(odp.“uki)tegografu(digrafu).
Strona 67 z 88
CyklemEulerawGnazywamycykl,kt ó ryjestdrog¡EulerawG.
Powr ó t
Graf(digraf),wkt ó rymistniejecyklEuleranazywamyeulerowskim.
Pe“nyekran
Wniosek2.2. Je–ligraf(digraf)bezwierzcho“k ó wizolowanychma
drogƒEulera,tojestsp ó jny.Je–lidigrafbezwierzcho“k ó wizolowanych
macyklEulera(jesteulerowski),tojestsilniesp ó jny.
Zamknij
Koniec
36212052.004.png 36212052.005.png 36212052.006.png 36212052.007.png 36212052.008.png 36212052.009.png
Problemmost ó wkr ó lewieckich
Stronag“ ó wna
Stronatytu“owa
Spistre–ci
Czymo»naodby¢spacer
powszystkich
XVIII-wiecznychmostach
naPregolewKr ó lewcu,
przechodz¡cprzez
ka»dyznichdok“adnie
jedenraziwr ó ci¢
dopunktuwyj–cia?
JJ II
J I
Strona 68 z 88
Powr ó t
Czygrafobokjestgrafemeulerowskim?
Pe“nyekran
Zamknij
Odpowied„: NIE .
Koniec
36212052.010.png 36212052.011.png 36212052.012.png 36212052.013.png 36212052.014.png 36212052.015.png 36212052.016.png 36212052.017.png
Stronag“ ó wna
Twierdzenie2.3. LeonhardEULER1736
Grafsp ó jnymacyklEulerawtedyitylkowtedy,gdystopie«ka»degojegowierz-
cho“kajestparzysty.
Stronatytu“owa
Spistre–ci
Dow ó d.()) Oczywiste ,skorowcykluEuleraprzechodz¡czaka»dymrazem
przezwierzcho“ek,przechodzimyprzezdwieincydentneznimkrawƒdzie.
JJ II
(()Za“ ó »my,»eka»dywierzcho“ekgrafuGmastopie«parzysty.Niech
P= v 0 ,e 0 ,v 1 ,...,v l−1 ,e l−1 ,v l
J I
bƒdzie najd“u»sz¡drog¡prost¡ wG.
Strona 69 z 88
Wszystkiekrawƒdzieincydentnezv 0 nale»¡doE(P) .Skorostopie«v 0 jest
parzysty,to v 0 =v l ,awiƒc Pjestcyklem .
Powr ó t
GdybyPnieby“acyklemEulera,namocy sp ó jno–ci Gistnia“abykrawƒd„ e=
{u,v i }2E\E(P) .W ó wczasjednakdrogaprosta
u,e,v i ,e i ,v i+1 ,...,v l−1 ,e l−1 ,v l =v 0 ,e 0 ,v 1 ,...,v i−1 ,e i−1 ,v i
Pe“nyekran
by“abyd“u»szaodP.
Zamknij
Koniec
36212052.018.png 36212052.019.png 36212052.020.png 36212052.021.png 36212052.022.png 36212052.023.png 36212052.024.png
Twierdzenie2.4. Grafsp ó jnymadrogƒEulerawtedyitylkowtedy,gdyma
dok“adniedwawierzcho“kistopnianieparzystegolubniemaichwcale.
Stronag“ ó wna
Dow ó d.()) Oczywiste .(()Je–liwszystkiestopnies¡parzyste,toztw. 2.3 ist-
niejecykl(azatemidroga)Eulera.Za“ ó »mywiƒc,»edok“adniedwawierzcho“ki:
uiv ,maj¡stopie«nieparzysty.
Stronatytu“owa
Spistre–ci
Dodajmyjedenwierzcho“ek x
ipo“¡czmygokrawƒdziamizuiv:
JJ II
J I
Strona 70 z 88
Powr ó t
Namocytwierdzenia 2.3 rozszerzonygrafma cykl Eulera
x,v,v 1 ,v 2 ,...,v l ,u,x .
Pe“nyekran
Drogaprosta v,v 1 ,v 2 ,...,v l ,u .
jestzatem drog¡ Eulerawwyj–ciowymgrafie.
Zamknij
Koniec
36212052.025.png 36212052.026.png 36212052.027.png 36212052.028.png 36212052.029.png 36212052.030.png 36212052.031.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin