Teoria grafów ma zastosowanie w licznych dziedzinach, mi¦dzy innymi:
• w
informatyce reprezentacja struktur do
przechowywania danych (np.:
drzewa binarne),
reprezentacja algorytmów,
opis topologi sieci
komputerowych, kryptograa
• w transporcie reprezentacja sieci dróg, poª¡cze«
lotniczych, systemy GPS
• w robotyce wyszukiwanie optymalnych tras
dla poruszaj¡cego si¦ robota, reprezentacja drzew decyzyjnych
• w zarz¡dzaniu reprezentacja struktury organizacyjnej przedsi¦biorstwa, optymalizacja zada«
• inne biologia, socjologia, psychologia, . . .
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 1
Def. Graf G skªada si¦ z dwóch zbiorów:
• zbioru V = V (G), którego elementami s¡ tzw.
wierzchoªki grafu,
• zbioru E = E(V ), którego elementami s¡ zbiory
zawieraj¡ce dwa ró»ne wierzchoªki, czyli tzw. kraw¦dzie grafu.
Wierzchoªki u, v ∈ V s¡siaduj¡ ze sob¡, je»eli istnieje taka kraw¦d¹ grafu e ∈ E, »e e = {u, v}. W takim przypadku u i v nazywamy ko«cami kraw¦dzi e, lub mówimy, »e e ª¡czy wierzchoªki u i v.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 2
Przykªadowy graf, skªadaj¡cy si¦ ze zbiorów:
V = {A, B, C, D, E, F, G}
E = {{A, B} , {B, C} , {C, D} , {D, E} , {E, F } ,
{F, A} , {A, G} , {B, D} , {D, F }}
przedstawiono na poni»szym rysunku
G
A
B
F
C
E
D
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 3
Czy poni»szy rysunek przedstawia graf (zgodnie z podan¡
wcze±niej denicj¡)?
e3
e1
A
B
e4
e2
e5
C
D
e6
Odp.: Nie. Powy»szy diagram posiada kraw¦dzie wielo
krotne e5 i e6 oraz p¦tl¦ e3. Diagram taki b¦dziemy nazywali multigrafem.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 4
Def. Rz¡d (stopie«) wierzchoªka v w grae G, oznaczany jako deg(v), jest równy liczbie kraw¦dzi, które zawieraj¡ v.
Tw. Suma rz¦du wszystkich wierzchoªków w grae G jest dwa razy wi¦ksza ni» liczba wszystkich kraw¦dzi grafu G.
Przykªad. Dla grafu przedstawionego na rysunku:
G
A
B
F
C
E
D
deg(A) = 3, deg(B) = 3, deg(C) = 2, deg(D) = 4,
deg(E) = 2, deg(F ) = 3, deg(G) = 1, czyli w sumie 18.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 5
Def.
Rozpatrzmy graf G = G(V, E).
Graf H =
H(V 0, E0) nazywamy podgrafem grafu G, je»eli zbiór wierzchoªków i kraw¦dzi grafu H zawiera si¦ odpowiednio w zbiorze wierzchoªków i kraw¦dzi grafu G, czyli V 0 ⊆ V
i E0 ⊆ E. W szczególno±ci:
• podgraf
H(V 0, E0)
grafu G(V, E) nazywamy
podgrafem wyznaczonym przez wierzchoªki V 0, je»eli zbiór kraw¦dzi E0 zawiera wszystkie kraw¦dzie grafu G, których ko«ce nale»¡ do wierzchoªków grafu H
• je»eli v jest wierzchoªkiem grafu G, to G − v jest podgrafem G otrzymanym poprzez usuni¦cie v z G oraz wszystkich kraw¦dzi w G które zawieraj¡ wierzchoªek v
• je»eli e jest kraw¦dzi¡ grafu, to G − e jest podgrafem G otrzymanym poprzez usuni¦cie e z G
Uwaga. Zgodnie z powy»sz¡ denicj¡, ka»dy graf jest swoim podgrafem.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 6
Grafy G(V, E) oraz G∗(V ∗, E∗) s¡ izomorczne, je»eli istnieje bijekcja (funkcja ró»nowarto±ciowa i na) f : V → V ∗
taka, »e {u, v} jest kraw¦dzi¡ grafu G wtedy i tylko wtedy, je»eli {f(u), f(v)} jest kraw¦dzi¡ grafu G∗.
Przykªad. Które z poni»szych grafów s¡ izomorczne?
Odp.: {A, R}, {F, T }, {K, X}, {M, S, V, Z}
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 7
Dla danego grafu G mo»na otrzyma¢ nowy graf G∗ dziel¡c wybran¡ kraw¦d¹ dodatkowym wierzchoªkiem. Dwa grafy G i G∗ nazywamy homeomorcznymi, je»eli utworzono je z tego samego grafu (lub grafów izomorcznych) za pomoc¡
takiej operacji dzielenia kraw¦dzi.
Przykªad.
Grafy na powy»szym rysunku nie s¡ izomorczne ale s¡
homeomorczne.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 8
Def. Droga jest to wyznaczona przez kraw¦dzie trasa polegaj¡ca na podró»owaniu od wierzchoªka do wierzchoªka grafu po ª¡cz¡cych je kraw¦dziach.
Drog¦ opisujemy
podaj¡c odpowiedni¡ krotk¦ kraw¦dzi.
Def. cie»ka o pocz¡tku w wierzchoªku v0 i ko«cu w wierzchoªku vn jest to trasa wyznaczona przez wierzchoªki grafu G(V, E), ª¡cz¡ca kolejno wierzchoªki v0 i v1, v1 i v2,
. . . , vn−1 i vn za pomoc¡ odpowiednich kraw¦dzi. cie»k¦
opisujemy podaj¡c odpowiedni¡ krotk¦ wierzchoªków.
Def. Dªugo±¢ drogi/±cie»ki jest równa liczbie kraw¦dzi/
wierzchoªków j¡ tworz¡cych.
Def.
Droga/±cie»ka jest prosta, je»eli wszystkie jej
kraw¦dzie/wierzchoªki s¡ ró»ne.
Def. cie»k¦ nazywamy zamkni¦t¡, je»eli v0 = vn.
Def. Cyklem nazywamy ±cie»k¦ zamkni¦t¡ o dªugo±ci co najmniej 3, dla której wszystkie wierzchoªki s¡ ró»ne z wyj¡tkiem v0 = vn.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 9
Przykªad. Dla pokazanego na rysunku grafu i podanych krotek wierzchoªków w poda¢, które z nich s¡ ±cie»kami (S),
±cie»kami prostymi (SP ), ±cie»kami zamkni¦tymi (SZ), cyklami (C)?
v
v
v
1
2
3
v
v
v
4
5
6
α = (v1, v4, v5, v2, v3, v1), β = (v1, v2, v5, v3, v2, v5) γ = (v1, v2, v5, v3, v2, v1), δ = (v4, v1, v5, v2, v3, v6) η = (v1, v5), = (v4, v5, v3, v2, v1, v4)
Odp.: α nie jest S; β jest S, nie jest SP , SZ, C; γ jest S, SZ, nie jest SP , C; δ jest S, SP , nie jest SZ, C; η jest S, SP , nie jest SZ, C; jest C
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 10
Def. Graf G nazywamy grafem spójnym, je»eli istnieje
±cie»ka ª¡cz¡ca dowoln¡ par¦ wierzchoªków.
Def. Odlegªo±¢ pomi¦dzy wierzchoªkami u i v w grae spójnym, oznaczana jako d(u, v), to dªugo±¢ najkrótszej
±cie»ki ª¡cz¡cej u i v.
Def. rednica grafu spójnego G, oznaczana jako diam(G), to najwi¦ksza odlegªo±¢ pomi¦dzy dwoma dowolnymi
wierzchoªkami grafu G.
Przykªad.
graf G
graf H
b
e
b
e
d
d
a
g
a
g
c
f
c
f
Graf G jest spójny, diam(G) = 3. Graf H jest niespójny.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 11
Def.
Wierzchoªek v grafu spójnego G jest punktem
artykulacji (wierzchoªkiem rozcinaj¡cym), je»eli graf G − v jest grafem niespójnym.
Def. Kraw¦d¹ e grafu spójnego G jest mostem, je»eli graf G − e jest grafem niespójnym.
Przykªad.
graf G
graf H
b
e
b
f
d
d
e
a
g
a
c
f
c
g
Dla grafu G wierzchoªek d jest punktem artykulacji (nie ma innych takich punktów, nie ma równie» mostów).
Dla grafu H kraw¦d¹ {d, e} jest mostem, wierzchoªki d i e s¡ punktami artykulacji.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 12
Def. Graf G jest peªny, je»eli ka»dy wierzchoªek G
jest poª¡czony bezpo±rednio kraw¦dzi¡ z ka»dym innym wierzchoªkiem. Graf peªny o n wierzchoªkach oznaczmy jako Kn. Oczywi±cie ka»dy graf peªny musi by¢ spójny.
Na rysunku poni»ej przedstawiono grafy K1 − K5
K
K
K
1
2
3
K
K
4
5
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 13
Def.
Graf G jest regularny stopnia k, je»eli ka»dy
wierzchoªek ma rz¡d k. Zatem graf G jest regularny, je»eli ka»dy wierzchoªek ma ten sam rz¡d.
Przykªad.
st. 0
st. 1
st. 3
st. 2
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 14
Def. Graf G jest dwudzielny, je»eli zbiór wierzchoªków V mo»na podzieli¢ na dwa podzbiory M i N takie, »e ka»da kraw¦d¹ grafu G ª¡czy wierzchoªek ze zbioru M z wierzchoªkiem ze zbioru N (czyli nie istnieje kraw¦d¹, która ª¡czy wierzchoªki nale»¡ce do tego samego podzbioru).
Def. Graf G jest dwudzielny peªny, je»eli ka»dy wierzchoªek ze zbioru M jest poª¡czony z ka»dym wierzchoªkiem ze zbioru N. Graf taki oznaczamy Km,n, gdzie m jest liczb¡
wierzchoªków w zbiorze M oraz n jest liczb¡ wierzchoªków w zbiorze N.
Przykªady grafów dwudzielnych peªnych.
K
K
K
2,3
3,3
2,4
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 15
Def.
Graf G nazywamy planarnym, je»eli mo»na go
przedstawi¢ na pªaszczy¹nie tak, »e »adne kraw¦dzie nie przecinaj¡ si¦.
Czy poni»szy graf jest planarny?
Odp. Tak.
Tw.
(Kuratowskiego) Graf jest planarny wtedy i tylko
wtedy, gdy nie zawiera ani podgrafu homeomorcznego do grafu regularnego K5 ani podgrafu homeomorcznego do grafu dwudzielnego K3,3.
Grafy K5 i K3,3 nie s¡ planarne.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 16
Graf skierowany to graf, w którym wszystkie kraw¦dzie maj¡ okre±lony kierunek.
Grafy tego typu cz¦sto stosuje si¦ do opisu ukªadów dynamicznych (np.: automaty Moore'a i Mealy'ego, ukªady dynamiczne z czasem ci¡gªym i integratorami, ukªady dyskretno-czasowe z opó¹nieniami).
Def. Graf skierowany G skªada si¦ z dwóch zbiorów:
• zbioru V = V (G), którego elementami s¡ tzw.
wierzchoªki grafu,
• zbioru E = E(V ), którego elementami s¡ pary
uporz¡dkowane (u, v), które nazywamy kraw¦dziami
grafu.
Zakªadamy, »e kraw¦d¹ e = (u, v) zaczyna si¦ w
wierzchoªku u i ko«czy si¦ w wierzchoªku v. Je»eli u = v to odpowiedni¡ kraw¦d¹ nazywamy p¦tl¡.
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 17
Rozpatrzmy przykªad.
A
B
C
D
Powy»szy graf skªada si¦ z dwóch zbiorów:
• V = {A, B, C, D}
• E = {(A, B) , (B, B) , (B, D) , (C, B) , (C, D) , (D, A) , (D, C)}
Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych 18