Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
3020Grafycząsteczekchemicznych
7
h
8
g
1
a
2
G(3)
1
4
3
5
2
G(1)
1
2
3
6
4
5
6
f
e
b
5
d
4
c
3
G(2)
Graf(domyślnienieskierowany)G=(V,E)składasięzeskończonego,niepustegozbioru
wierzchołkówVirodzinydwuelementowychpodzbiorówzbioruVzwanychkrawędziami
E;{v,w}:v,wEV,v#w}.LiczbawierzchołkówgrafuGdefiniowanajestwzoremn=|V(G)|,
akrawędzi-m=|E(G)|.Jeżeliwierzchołkomprzypisanesąetykiety(najczęściejliczby),tograf
nazywamygrafemoznaczonym.Zazwyczajwierzchołkinumerowanesąkolejnymiliczbami
naturalnymiV(G)={v1,v2,…,vn}.Krawędźłączącawierzchołkiviivjoznaczanajestjakoeij.
NarysunkuprzedstawionografG(1),któryma6wierzchołkówV(1)={v1,v2,v3,v4,v5,v6}i5
krawędziE(1)={e1,2,e2,3,e3,4,e5,6,e3,6}.Wierzchołkinależącedodanejkrawędzinazywamy
jejkońcami.Dwawierzchołkisąsąsiadami,jeżeliistniejekrawędźpomiędzynimi.Stopień
wierzchołkavi,degitoliczbajegosąsiadów.Graf,któregokażdywierzchołekjestsąsiadem
pozostałychwierzchołków,nazywamypełnymioznaczamyKn.Ścieżką(drogą)długościk
zwierzchołkav
i
dowierzchołkav
j
wgrafienieskierowanymG(V,E)nazywamytakiciągwierz-
chołkówv1,v2,…,vk,żevi=v1,vj=vkoraz(vl–1,vl)EE,l=1,…,k.Wyznaczanyjestwtym
przypadkuszlakprzejściaodwierzchołkav
i
dowierzchołkav
j
połączącychjekrawędziach.
Wierzchołkigrafusąpołączone,jeżeliistniejedrogapomiędzynimi.Drogaprostanieza-
wieradwóchtychsamychkrawędzi,którychliczbawyznaczadługośćdrogi.Ścieżka,któ-
razaczynasięikończywtymsamymwierzchołku(drogazamknięta)odługościk≥2,na-
zywanajestcyklem(k=1topętla).Graf,któryniezawieracyklu,tografacykliczny.Jeżeli
możliwejestprzejściezdowolnegowierzchołkadokażdegoinnegowierzchołkawzdłuż
pewnejścieżki,tografjestspójny.Grafniespójnyskładasięzpewnejliczbyskładowych,
zktórychkażdatomożliwienajwiększyspójnypodgrafgrafuG.Grafspójnybezcykli,gdzie
m=n–1,nazywamydrzewem.
Przykładowo,wG(1)końcamikrawędzie
1,2
sąwierzchołkiv
1
iv
2
,wierzchołekv
3
sąsiadu-
jezwierzchołkamiv2,v3iv6,natomiastdeg3=3.GrafG(1)niejestgrafempełnym.Istnieje
drogaprostaodwierzchołkav1dov6odługości3.GrafG(1)jestgrafemacyklicznym,spój-
nym,tworzącymdrzewo(m=5,n=6).
Niekiedyistniejepotrzebaokreśleniakierunkulubwagipołączeniapomiędzyokreślonymi
wierzchołkami.Wpierwszymprzypadkutworzonyjestgrafskierowany,wdrugimzaś-wa-
żony.Grafemskierowanym(diagrafem)nazywamyuporządkowanąparęG(V,A),gdzieVjest
zbioremwierzchołków,natomiastAjestzbioremkrawędziskierowanych:A;V×V.Skiero-
wanakrawędźe
ij
oznaczapołączeniawychodząceodv
i
dov
j
.Przezpołączeniedwóchwierz-
chołkówwięcejniżjednąkrawędziątworzonyjesttzw.multigraf.Zdefiniowaniefunkcjiod-
wzorowującejzbiórwierzchołkówikrawędzi(grafyskierowaneinieskierowane)wpewien
zbiórRumożliwiaprzypisaniewierzchołkomlubkrawędziometykietsłużącychdoprzecho-
wywaniadodatkowychinformacji.Nadawaneetykietysączęstowartościamiliczbowymize
zbioruliczbrzeczywistychnazywanymiwagami,naprzykład
φ
:E→R,gdziedlakażdejkrawę-
dzieEE
φ
jejwagąjest(e).NarysunkuprzedstawionografważonyG(2)iskierowanyG(3).
27
