Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.2.Realizowalnośćgrafuozadanychstopniachwierzchołków
23
wadzićdwaciągi:stopniwychodzącychistopniwchodzących.Naprzykładdlagrafu
niezorientowanegoprzedstawionegonarys.2.1ciągiemstopniwierzchołkówjest
(2,4,4,4,3,3).Innącharakterystykąjestrozkładstopniwierzchołków.Jesttofunkcja
p(d),którejargumentemsąstopniewierzchołków,awartościąjestliczbawierzchoł-
kówstopniad-rys.2.1b(lubprawdopodobieństwowierzchołkastopniad).
Wprowadźmypojęcieszkieletugrafuzorientowanego:jesttografniezorientowa-
nyotrzymanyprzezpominięcieorientacjikrawędzigrafuzorientowanego.
●
2.2.Realizowalnośćgrafuozadanychstopniach
wierzchołków
Określenieciągustopniwierzchołkówdladanegografujestzadaniemelementarnym.
Możnapostawićpytanieodwrotne.Danyjestciągnieujemnychliczbcałkowitych
d
1,d
2,...,d
n.Jakiewarunkimusispełniaćciąg,abyistniałgrafzwyczajnyotychstop-
niachwierzchołków?Ciągliczbowy,któryjestciągiemstopniwierzchołkówpewne-
gografuzwyczajnego,nazywamyciągiemgraficznym.Napodstawieposiadanejjuż
wiedzymożnapodaćprostewarunkikoniecznedotego,abyciągnnieujemnychliczb
całkowitychbyłciągiemgraficznym:
d
i<n-1,
dlai=1,2,...,n,
(2.7a)
jestliczbąparzystą,
liczbawyrazówciąguowartościachnieparzystychjestliczbąparzystą.
(2.7b)
(2.7c)
(2.7d)
Niesątowarunkiwystarczające,ponieważnp.dlaciągu3,3,3,1nieistniejegraf
otakichstopniachwierzchołków.Podamywarunkikonieczneiwystarczającedo
tego,abyciągliczbowybyłgraficzny.
Twierdzenie2.1[2.1].Ciągsliczbcałkowitychd
1;d
2;...
;d
n;0,n>2,d
1;1
jestgraficznywtedyitylkowtedy,gdyciąg
jestgraficzny.
Twierdzenie2.2[2.1].Ciągliczbcałkowitychd
1;d
2;...
;d
n;0jestgraficzny
wtedyitylkowtedy,gdy
jestliczbąparzystą,
(2.8a)
