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
i
j
składaj cy si z punktów odpowiadaj cych
v4
elementom zbioru V(G) oraz strzałek,
v3
odpowiadaj cych elementom zbioru E(G),
g
f
takich e je li γ ( e)= ( p, q), to strzałka odpowiadaj ca e biegnie od punktu
v1
a
oznaczonego p do punktu oznaczonego q.
v2
Rys. 1
e
a
f
g
i
j
γ(e) (v1,v2)
(v4,v2)
(v4,v1)
(v4,v3)
(v3,v3)
1
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) ={v1, v2, …, vn} 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 vi do vj, w przeciwnym wypadku M[i,j]
jest dodatni liczb całkowit .
Przykład 1. Macierz s siedztwa dla grafu z Rys. 1 ma posta : 0 1 0 0
0 0 0 0
M = 0 0 1 0
1 1 1 0
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.
2
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.
1 1 1 1
0 1 1 1
1
G
M = 0 0 1 1
0
2
0 0 0 1
3
Rys. 2
Ka dej relacji R w zbiorze sko czonym S odpowiada sko czony graf skierowany GR
bez kraw dzi wielokrotnych. Zatem odpowiada tej relacji równie macierz MR, 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 MR 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 e1, e2, …, en nale do zbioru E( G), to ci g kraw dzi e1 e2…en, wraz z ci giem wierzchołków v1v2…vn+1, takim e γ(ej)={vj,vj+1}, jest drog długo ci n od wierzchołka v1 do wierzchołka vn+1.
P tla.
Wierzchołki vj,vj+1 mog by równe, w takim wypadku kraw d ej jest p tl .
3
Droga zamkni ta.
Je li v1 = vn+1, to tak drog nazywamy drog zamkni t .
Przykład 3.
Rozwa my graf przedstawiony na Rys. 1.
j
z
b
Droga efg jest drog zamkni t . Kraw d j
stanowi p tl .
w
a
g
f
h
Rys. 3
Droga zamkni ta mo e składa si z tego
x
e
y
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 {vj, 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.
4
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).
5