Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1
Definicjagrafuiprzykładyzastosowań
Pojęciegrafujestdośćintuicyjneibyćmożeztegopowoduwróżnychpodręcznikach
●
1.1.Podstawowepojęciagrafów
spotykamyniecoróżniącesiędefinicje,wzależnościodtego,jakąklasęproblemów
autorchcemodelować.
Pojęciamipierwotnymisą:zbiórwierzchołków,którybędziemyoznaczalijakoV
orazrodzinakrawędzioznaczanasymbolemE(rodzina,wodróżnieniuodzbioru,
możezawieraćelementypowtarzającesię).Grafemnazywamyparęuporządkowaną
G=(V,E).Grafmusimiećconajmniejjedenwierzchołek,
,oraz
.
Liczbęwierzchołkówgrafubędziemyoznaczalisymbolemn,aliczbękrawędzisym-
bolemq.Ograniczymysiędoklasygrafówskończonych,tzn.takich,żeniqsąlicz-
bamiskończonymi.
KrawędziągrafueÎEjestuporządkowanaparawierzchołkówe=(v
1,v
2),v
1ÎV,
v
2ÎV.JeżelirodzinaEzawierapowtarzającesięelementy,totakiekrawędzienazy-
wamyrównoległymilubwielokrotnymi.Jeżeli(v
1,v
2)ÎEi(v
2,v
1)ÎE,totakapara
jestnazywanakrawędziąniezorientowaną(nieskierowaną)lubwprostkrawędzią
ioznaczanasymboleme={v
1,v
2}.Jeśli(v
1,v
2)ÎE,(v
2,v
1)ÏE,tokrawędźnazywa-
myłukiemalbokrawędziązorientowaną(skierowaną).Jeżeliłukłączywierzchołekv
zw,tovjestpoprzednikiemwierzchołkaw,awjestnastępnikiemv.
Napodstawiewprowadzonejterminologiimożemydokonaćwstępnejklasyfika-
cjigrafów.
Grafniezorientowany(nieskierowany)-grafniezawierającyłuków.
Grafzorientowany(skierowany)-grafniezawierającykrawędziniezorientowanych.
Multigraf-grafzkrawędziamirównoległymi.
Grafzwyczajny(prosty)-grafniezorientowanybezpętliikrawędzirównole-
głych(tzn.rodzinakrawędzijestpoprostuzbiorem).
Powyższaklasyfikacjaniejestwyczerpująca,ponieważnp.istniejągrafyza-
wierającezarównokrawędzie,jakiłuki(czasamisąonenazywanegrafamiczę-
ściowozorientowanymi).Przykłademtakiegografumożebyćsiećulicmiasta,
