Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.Podstawowepojęciagrafów
3
ciomsąpokazanenarys.1.2c.Dlatych,którzytrochęznająteorięobwodówelek-
trycznych,jestoczywiste,żegrafnieetykietowanywystarczadonapisaniarównań
Kirchhoffa(identycznychdlaobuobwodów),natomiastdoobliczeniaprądówinapięć
musimysięposłużyćgrafemetykietowanym.
Rys.1.2.Siecielektryczne:a)schematyelektryczne;b)modeljakografnieetykietowany;
c)modeljakografetykietowany
Wpodręcznikachteoriigrafówzazwyczajpodajesiępewnerodzajegrafówjako
grafyprzykładowe.Poniżejprzedstawimyniektóreznich.
Ścieżka(lubłańcuch)n-wierzchołkowaP
njestgrafem:
-niezorientowanym,wktórymsądwawierzchołkistopniapierwszegoin-2
wierzchołkówstopniadrugiego.PrzykładścieżkiP
5jestpokazanynarys.1.3a;
-zorientowanym,wktórymistniejąwierzchołkiv,wnazywanewierzchołkiem
początkowymikońcowymścieżkitakie,żed+(v)=d
-(w)=1orazd-(v)=d+(w)=0
(rys.1.3b).
Cyklemn-wierzchołkowymC
njestgraf:
-niezorientowany,wktórymstopniewszystkichwierzchołkówsąrówne2ido-
wolnąparęwierzchołkówmożnapołączyćścieżką(rys.1.3c);
-zorientowany,wktórymstopieńwejściowyiwyjściowykażdegozwierzchoł-
kówjestrówny1idowolnąparęwierzchołkówmożnapołączyćścieżkązorientowaną
(rys.1.3d).
GwiazdaK
l,mmajedenwierzchołekstopniamimwierzchołkówstopniapierw-
szego.Gwiazdaosześciuwierzchołkachjestpokazananarys.1.3e.
