Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
2.Podstawowewłasnościgrafów
Dowód
Dokonamypodziałuzbioruwierzchołkówgrafunadwapodzbiory:V
p-zbiórwierz-
chołkówstopniaparzystego,V
n-zbiórwierzchołkówstopnianieparzystego.Możemy
napisać
Sumastopniwierzchołkówgrafuniezorientowanegojestliczbąparzystą.
Pierwszyskładnikprawejstronypowyższegowyrażeniajestliczbąparzystą,ponie-
ważjestsumąliczbparzystych.Abysumastopniwierzchołkówbyłaliczbaparzystą,
drugiskładnikprawejstronytakżemusibyćliczbąparzystą.Jesttosumaliczbniepa-
rzystych,więcliczbaskładnikówtejsumymusibyćliczbąparzystą.
o
Wierzchołekgrafuzorientowanegonazywamyizolowanym,jeżelijegostopnie:
wejściowyiwyjściowysąrównezeru.Wierzchołekvtaki,że
(2.4)
d+(v)+d
-(v)=1
nazywasięwiszącym.
(2.5)
Własność2.3.Wgrafiezorientowanymsumawejściowychstopniwierzchołków
jestrównasumiestopniwyjściowychirównasięliczbiekrawędzigrafu.
Dowód
Łukskierowanyodwierzchołkaudovzwiększaojedenstopieńwyjściowywierz-
chołkauistopieńwejściowywierzchołkav.Azatem
(2.6)
o
Zbióruporządkowany
nazywamyciągiemstopniwierzchołków
grafuniezorientowanego.Odpowiedniodlagrafówzorientowanychmożemywpro-
Rys.2.1.a)Grafniezorientowany;b)rozkładstopniwierzchołków
