Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
24
2.Podstawowewłasnościgrafów
orazdlakażdejliczbycałkowitej1<k<kn–1zachodzi
(2.8b)
Przykład2.1.Któreznastępującychciągówsągraficzne:
a)5,5,5,4,4,3;
b)5,5,5,5,3,3?
Dlaciągówgraficznychskonstruowaćgrafyrealizującetestopniewierzchołków.
Rozwiązanie
Ciąg(a)man=6wyrazówispełniawarunkikonieczne(2.7).Dosprawdzenia
warunkówdostatecznychiteracyjniezastosujemytwierdzenie2.1.
s=5,5,5,4,4,3;d
1=5
s
1=4,4,3,3,2;d
1=4
Dociągus
1ponowniezastosujemytwierdzenie2.1.
s
2=3,2,2,1;d
1=3
Stosującwdalszymciągutwierdzenie2.1,otrzymujemy
s
3=1,1,0;d
1=1
anastępnieciąg
s
4=0,0.
Jesttociąggraficzny:grafG
4składasięzdwóchwierzchołkówizolowanych(rys.
2.2a).AbyprzejśćdografuG
3odpowiadającegociągowis
3,musimydoG
4dodaćje-
denwierzchołekorazjednąkrawędź(abyspełnićwarunekstopni)-tęsytuacjęzilu-
strowanonarys.2.2b.PrzechodzącodgrafuG
3doG
2(ciągs
2),dodajemyjedenwierz-
chołekstopnia3:wtymceluwierzchołektenłączymyztrzemawierzchołkamigrafu
G
3(rys.2.2c).WkolejnymkrokuprzechodzimydoszukanegografuGosekwencji
stopniwierzchołkówsprzezdodaniewierzchołkaiodpowiedniegozbiorukrawędzi
doG
2(rys.2.2d).
Dociągu(b)zastosujemytwierdzenie2.2.Sumastopniwyrazówciągujestliczbą
parzystą.Sprawdźmyteraz,czynierówności(2.8b)sąspełnionedlak=1,2,3,4,5.
k=1:
,
nierównośćspełniona,
k=2:
,
nierównośćniejestspełniona.
Nierówność(2.8b)niejestspełnionadlak=2,więcciągniejestgraficzny.
