Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2
1.Defnicjagrafuiprzykładyzastosowań
wktórejskrzyżowaniasąreprezentowaneprzezwierzchołki,auliceprzezkrawę-
dzie.Niektórezulicmogąbyćdwukierunkowe,ainnejednokierunkowe.Napod-
stawietegoprzykładumożnarównieżzaobserwowaćwzględnośćmodelu:niektóre
zulicmiastasąwielopasmoweitylkoodanalizowanegoproblemuzależy,czybę-
dziemytakieulicereprezentowaćzapomocąkrawędzipojedynczych,czyrówno-
ległych.
Odrębnąklasągrafówsątzw.grafyważone.G=(V,E)nazywamygrafemważo-
nym,jeżeliistniejefunkcjaw:E®R+przyporządkowującakażdejkrawędzidodatnią
liczbęrzeczywistą.Wzależnościodkontekstujestonanazywanawagąlubkosztem
krawędzi.
Mówimy,żedwawierzchołkiv,usąsiadujązesobą,jeżeliistniejekrawędźgrafu
łączącatewierzchołki.JeżelikrawędźeÏEłączywierzchołkiv,u,tokrawędźjest
incydentnaztymiwierzchołkami(cozapisujemyveu).
JeżeliG=(V,E)jestgrafemniezorientowanym,tostopniemd(v)wierzchołka
vÎVnazywamyliczbękrawędziincydentnychzwierzchołkiemv.Przyjmujemy,że
pętlesąliczonepodwójnie.JeżeliGjestgrafemzorientowanym,tozkażdymwierz-
chołkiemjestzwiązanystopieńwyjściowyistopieńwejściowy.Stopieńwyjściowy
d+(v)jestrównyliczbiełukówincydentnychzvizorientowanychodtegowierzchoł-
ka.Stopieńwejściowyd
-(v)jestliczbąłukówincydentnychzvizorientowanychdo
wierzchołka.
Chociażgrafjestpojęciemabstrakcyjnym,toczęstoreprezentujemygowpostaci
rysunkunapłaszczyźnie.Wierzchołkigrafuprzedstawiamyjakopunktypłaszczy-
zny,akrawędziejakoliniełącząceparywierzchołków.Przyjmujesięsymbolegra-
ficznekrawędzipokazanenarys.1.1.
Rys.1.1.Reprezentacjakrawędzigrafu:a)krawędźniezorientowana;b)łuk;c)pętla
Wprowadzoneprzeznasgrafysągrafaminieetykietowanymi,tzn.krawędzienie
mająetykietisąidentyfikowaneprzezpodaniewierzchołkówkońcowych.Jednymze
skutkówtakiejdefinicjijestbrakmożliwościjednoznacznejidentyfikacjikrawędzi
równoległych.Wprowadzasięrównieżpojęciegrafuetykietowanego,wktórymkaż-
dazkrawędzimanadanąunikalnąetykietę.Narysunku1.2asąpokazanedwiesieci
elektryczne,anarys.1.2b-strukturapołączeńkrawędzitychsiecireprezentowanych
zapomocązorientowanegografunieetykietowanego(orientacjałukówjestzgodna
zkierunkiemprzepływającegoprądu).Grafyetykietowaneodpowiadającetymsie-
