1
Relacje.
Relacja dwuargumentowa.
Dla danych zbiorów S i T relacj dwuargumentow na zbiorze S
×T jest
dowolny podzbiór R zbioru S
×T.
Interesuj ce dla nas b d relacje s siedztwa i osi galno ci dla wierzchołków grafu.
Grafy.
Graf skierowany.
Graf skierowany G składa si z dwóch zbiorów, niepustego zbioru V(G)
wierzchołków grafu i zbioru E(G) kraw dzi grafu oraz z funkcji
γ
odwzorowuj cej
zbiór E(G) w zbiór V(G)
×V(G).
wierzchołek –vertice (v);
kraw d – edge (e).
Je li e jest kraw dzi grafu G i
γ
(e)= (p, q) to p nazywamy pocz tkiem kraw dzi e, a
q ko cem kraw dzi e i mówimy, e e biegnie od p do q.
Rysunkiem grafu skierowanego jest wykres
składaj cy si z punktów odpowiadaj cych
elementom zbioru V(G) oraz strzałek,
odpowiadaj cych elementom zbioru E(G),
takich e je li
γ
(e)= (p, q), to strzałka
odpowiadaj ca e biegnie od punktu
oznaczonego p do punktu oznaczonego q.
e
a
f
g
i
j
γ
(e) (v
1
,v
2
)
(v
4
,v
2
)
(v
4
,v
1
)
(v
4
,v
3
)
(v
3
,v
3
)
a
f
g
i
j
v
1
v
2
v
4
v
3
Rys.
1
2
Macierze.
Macierze dwuwymiarowe s wa nym narz dziem do opisywania grafów
skierowanych i relacji dwuargumentowych. W potrzebnym nam tutaj zakresie
b dziemy postrzega macierz w sposób uproszczony, jako prostok tn tablic liczb.
W badaniu relacji sko czonych grafów skierowanych i nieskierowanych u yteczne
jest poj cie s siedztwa. Dla danego grafu G i wierzchołków x,y w zbiorze V(G)
mówimy, e wierzchołek x jest s siedni do w stosunku do wierzchołka y, je li istnieje
kraw d w E(G) od x do y. Mówimy wtedy, e wierzchołki x, y s ze sob w relacji
s siedztwa.
Macierz opisuj c t relacj jest macierz s siedztwa. Niech G b dzie skierowanym
grafem sko czonym a V(G) ={v
1
, v
2
, …, v
n
} zbiorem wierzchołków tego grafu.
Macierz s siedztwa.
Macierz M wymiaru n
×n, której ka dy wyraz M[i,j] jest liczb kraw dzi od
wierzchołka i do wierzchołka j.
Zatem M[i,j]=0, je li nie istnieje kraw d od v
i
do v
j
, w przeciwnym wypadku M[i,j]
jest dodatni liczb całkowit .
Przykład
1. Macierz s siedztwa dla grafu z Rys. 1 ma posta :
W przypadku grafów bez kraw dzi wielokrotnych (wi cej ni jedna kraw d ł czy
dwa wierzchołki) istnieje wzajemnie jednoznaczna odpowiednio mi dzy grafami
skierowanymi, a relacjami.
=
0
1
1
1
0
1
0
0
0
0
0
0
0
0
1
0
M
3
Przykład
2. We my relacj R na zbiorze {0,1,2,3} okre lon przez ≤. Zatem (m,n)∈ R
wtedy i tylko wtedy gdy m
≤ n. Macierz M oraz graf G odpowiadaj ce relacji R s
przedstawione na Rys.
2.
Ka dej relacji R w zbiorze sko czonym S odpowiada sko czony graf skierowany G
R
bez kraw dzi wielokrotnych. Zatem odpowiada tej relacji równie macierz M
R
, której
wyrazami s 0 i 1. Poniewa zbiorem wierzchołków grafu jest zbiór S, wi c je li n
jest moc zbioru S to macierz M
R
jest macierz wymiaru n
× n.
Droga.
Drog w grafie skierowanym G nazywamy ci g kraw dzi taki, e koniec
jednej kraw dzi jest pocz tkiem nast pnej.
Je li e
1
, e
2
, …, e
n
nale do zbioru E(G), to ci g kraw dzi e
1
e
2
…e
n
, wraz z ci giem
wierzchołków v
1
v
2
…v
n
+1
, takim e
γ
(e
j
)={v
j
,
v
j
+1
}, jest
drog długo ci n od
wierzchołka v
1
do wierzchołka v
n
+1
.
P tla.
Wierzchołki v
j
,
v
j
+1
mog by równe, w takim wypadku kraw d e
j
jest p tl .
=
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
1
M
0
1
2
3
G
Rys.
2
4
Droga zamkni ta.
Je li v
1
= v
n
+1
, to tak drog nazywamy drog zamkni t .
Przykład 3.
Rozwa my graf przedstawiony na Rys. 1.
Droga
efg jest drog zamkni t . Kraw d j
stanowi p tl .
Rys.
3
Droga zamkni ta mo e składa si z tego
samego ci gu kraw dzi, przechodzonych
„tam i z powrotem” np. efggfe.
Jednak najwa niejszymi drogami zamkni tymi s te, w których adna kraw d si nie
powtarza.
Droga prosta.
droga w której wszystkie kraw dzie s ró ne.
W drodze prostej adna kraw d nie jest wykorzystana dwa razy, chocia taka droga
mo e przechodzi przez ten sam wierzchołek wi cej ni jeden raz.
Cykl.
Zamkni t drog prost , której ci giem wierzchołków jest ci g {v
j
, j=1,…, n}
nazywamy cyklem je li wierzchołki s ró ne.
Graf acykliczny.
Droga acykliczna.
Graf nie zawieraj cy cykli.
„Podgraf” składaj cy si z wierzchołków
i kraw dzi tej drogi jest acykliczny.
Graf jest acykliczny wtedy i tylko wtedy gdy nie zawiera zamkni tych dróg prostych.
x
y
w
z
e
f
g
a
b
h
j
5
Graf H jest podgrafem grafu G, je li V(H)
⊆ V(G), E(H) ⊆ E(G) oraz funkcja
γ
grafu
G, okre lona na E(G) pokrywa si z funkcj
γ
grafu H okre lon na E(H).
Gdy graf G nie ma kraw dzi wielokrotnych i je li traktujemy zbiór E(G) jako zbiór
jedno- i dwu-elementowych podzbiorów V(G) to warunek nało ony na funkcj
γ
wynika z inkluzji E(H)
⊆ E(G).