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).