grafy06, matematyka dyskretna
[ Pobierz całość w formacie PDF ]
Stronag“
ó
wna
Wniosek2.34.
CrispinSt.JohnAlvahNASH-WILLIAMS1969
Je–lidigrafbezpƒtliD=(V,A)on3wierzcho“kachspe“niawarunek
Stronatytu“owa
8v2Vd
−
(v)
n
2
^d
+
(v)
n
2
, (2.8)
Spistre–ci
tojesthamiltonowski.
JJ II
Dow
ó
d.Niechu,v2V,u6=v.Mamy
|V
+
(u)|+|V
−
(v)|n.
J I
V
+
(u)={w:(u,w)2A},V
−
(v)={w:(w,v)2A}
Je–liv2V
+
(u),towDistniejedrogazudovd“ugo–ci1:
(u,v)
.
Je–liv/2V
+
(u),to
Strona
105
z
284
|V
+
(u)[V
−
(v)|n−1,
wiƒcistniejew2V
+
(u)\V
−
(v)iwDistniejedrogazudovd“ugo–ci2:
(u,w,v)
.
Djestsilniesp
ó
jny
.
Powr
ó
t
Pe“nyekran
Namocy(
2.8
)dlau2V
d(u)n,
wiƒcztwierdzenia
2.33
Djesthamiltonowski.
Zamknij
Koniec
Stronag“
ó
wna
Stronatytu“owa
Chapter3
Spistre–ci
Drzewailasy
JJ II
J I
Definicje3.1.
Lasemnazywamygrafniezawieraj¡cycykluprostego.
Drzewemnazywamygrafsp
ó
jnyniezawieraj¡cycykluprostego.
Strona
106
z
284
Wniosek3.2.
Sk“adowymisp
ó
jnymilasus¡drzewa.
Powr
ó
t
Pe“nyekran
czterydrzewawlesie
Zamknij
Koniec
Twierdzenie3.3.
DlagrafuGonwierzcho“kachnastƒpuj¡cestwierdzenias¡
r
ó
wnowa»ne:
Stronag“
ó
wna
¶
Gjestdrzewem;
·
Gniezawieracykluprostegoiman−1krawƒdzi;
Stronatytu“owa
¸
Gjestsp
ó
jnyiman−1krawƒdzi;
¹
Gjestsp
ó
jnyika»dakrawƒd„jestmostem;
º
dowolnedwar
ó
»newierzcho“kipo“¡czones¡dok“adniejedn¡drog¡prost¡;
»
Gniezawieracykluprostego,leczdo“¡czeniejakiejkolwiekkrawƒdzipowoduje
powstaniedok“adniejednegocykluprostego.
Spistre–ci
JJ II
J I
Dow
ó
d.Rozwa»my
n2
.
Strona
107
z
284
(1))(2)
Za“
ó
»my,»eimplikacjazachodzidladrzew
omniejni»nwierzcho“kach
.
Rozwa»mydrzewoG=(V,E)o
n
wierzcho“kach.Niech
e2E
.
Gjestdrzewem)las
G−e
ma2drzewaokilwierzcho“kach,k+l=n.
Powr
ó
t
Namocyza“o»enia,G−ema
Pe“nyekran
k−1+l−1=n−2
krawƒdzi,wiƒc
Gman−1krawƒdzi
.
Zamknij
Koniec
(2))(3)
NiechG=(V,E)niezawieracykluprostego(
las
),man−1krawƒdzi
i
k>1
sk“adowych(V
i
,E
i
),i=1,...,k.Z
(1))(2)
dla(V
i
,E
i
)
Stronag“
ó
wna
|E|
=|E
1
|+...+|E
k
|=(|V
1
|−1)+...+(|V
k
|−1)=n−k<
n−1
,
Stronatytu“owa
sprzeczno–¢.
(3))(4)
NiechG=(V,E)bƒdziesp
ó
jnyiman−1krawƒdzi.Dlaka»deje2E,
G−eman−2krawƒdzi,wiƒc(twierdzenie
1.36
)niejestsp
ó
jny,tzn.
ejest
mostem
.
Spistre–ci
JJ II
(4))(5)
Je–lidwawierzcho“kipo“¡czones¡dwiemar
ó
»nymidrogami,towgrafie
istniejecyklprosty.
›
adnazkrawƒdzitegocykluniejestmostem.
J I
(5))(6)
Je–ligrafzawieracyklprosty,toka»d¡parƒwierzcho“k
ó
wtegocyklu
mo»napo“¡czy¢dwiemadrogami.
NiechwG=(V,E)istniejedroga
P
miƒdzyuivoraz
e={u,v}/2E
.W
G+e
mamydwiedrogimiƒdzyuiv:Pi(u,v)orazjedencyklprosty
P,(u,v)
.
Strona
108
z
284
Powr
ó
t
Pe“nyekran
(6))(1)
Gniezawieracykluprostego)jestlasem.Za“
ó
»my,»eG=(V,E)
jestniesp
ó
jny.Je–liu,v2Vnale»¡dor
ó
»nychsk“adowychG,to
G+{u,v}nie
zawieracykluprostego
.
Zamknij
Koniec
Stronag“
ó
wna
Wniosek3.4.
Lasonwierzcho“kachikdrzewachman−kkrawƒdzi.
Stronatytu“owa
Dow
ó
d.Czƒ–¢(2))(3)dowodutwierdzenia
3.3
.
Spistre–ci
JJ II
Wniosek3.5.
Drzewoon>1wierzcho“kachmaprzynajmniejdwali–cie.
J I
Dow
ó
d.Namocytwierdzenia
3.3
sumastopniwierzcho“k
ó
wto2n−2.Gdyby
ka»dywierzcho“ek,zawyj¡tkiemjednego,mia“stopie«2,tosumastopni
by“abywiƒkszani»
Strona
109
z
284
(n−1)·2+1=2n−1,
sprzeczno–¢.
Powr
ó
t
Pe“nyekran
Zamknij
Koniec
[ Pobierz całość w formacie PDF ]