grafy04(1), matematyka dyskretna
[ Pobierz całość w formacie PDF ]
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-
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
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
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
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
[ Pobierz całość w formacie PDF ]