Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2
Podstawowewłasnościgrafów
Wierzchołekgrafuniezorientowanegotaki,żed(v)=0,jestwierzchołkiemizolowa-
●
2.1.Własnościliczbowegrafu
nym,awierzchołekod(v)=1-wierzchołkiemwiszącym(incydentnąznimkrawędź
nazywamykrawędziąwiszącą).Symbolemd(G)oznaczamynajmniejszyspośród
stopniwierzchołkówgrafu:
szystopieńwierzchołkagrafu:
.SymbolemD(G)oznaczamynajwięk-
.
Własność2.1.Wgrafieniezorientowanymsumastopniwierzchołkówjestrówna
podwojonejliczbiekrawędzi
.
Dowód
(2.1)
Każdakrawędźzwiększaojedenstopniewierzchołkówincydentnychztąkrawę-
dzią(wprzypadkupętliwłasnejoznaczatozwiększeniestopniawierzchołkaodwa).
Azatem
.
Liczbę
nazywamyśrednimstopniemwierzchołkagrafu.
(2.2)
o
(2.3)
Własność2.2.Wgrafieniezorientowanymliczbawierzchołkównieparzystegostop-
niajestliczbąparzystą.
