8. Elementy teorii grafów (Relacje i ich reprezentacje)

Klasyfikacja, reprezentacja, modele. Macierzowe reprezentacje grafów:
macierz incydencji, macierz stowarzyszona. Wykorzystanie do
modelowania dziedzin problemów decyzyjnych i/lub optymalizacyjnych

Przykład

S = {1,2,3}, T = {a, b} ,S x T = {(1,a), (1,b), (2,a), (2,b),

(3,a), (3,b)}

R = S x T = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

1

2

3

a

b

1

RELACJE
R - relacja dwuargumentowa na zbiorze S x T
Relacja na zbiorze S x T jest to każdy podzbiór tego zbioru.
Elementy relacji R  S x T wyróżniają się spośród elementów zbioru S x T
tym,
że mają pewną wspólną własność.
Mówimy, x jest w relacji z y  (x,y)R

1

2

3

Przykład 1

Dane są zbiory: S = {1,2,3}, T = {1,2,3} ,

Relacja określona na tych zbiorach:

def

R = S x T = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3),(3,1), (3,2),

(3,3)}

Jej reprezentacja graficzna: parze (x,y) odpowiada łuk x y

2

Przykłady relacji R’, R”, R”’  R

R’ = {(1,2),(1,3),(2,3)}  S x T;

a R’ b  a < b dla a S, bT

R” = {(1,1),(2,2),(3,3)}  S x T

;

a R” b  a = b

dla a S,

bT

R’’’ = { }  S x T ;

a R’’’ b  a mod 5 = b mod 5 = 4 mod 5

dla a S, bT

1

2

3

a

b

3

Jest zwrotna

(x,x)  R

, x  S

Jest przeciwzwrotna

(x,x)  R

, x S

Jest symetryczna

(x,y)  R  (y,x)  R, x,y S

Jest antysymetryczna

(x,y)  R & (y,x)  R  x = y

Jest przechodnia

(x,y)  R & (y,z)  R  (x,z)  R

4

Własności relacji

Niech R  S x S oznacza relację R w zbiorze S

Jeżeli R  S x T to R^  T x S

jest relacja odwrotną

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R =

{(a,a), (b,b),

(c,c), (d,d), (a,b)}. Czy relacja ta jest zwrotna (tzn. czy x  S (x,x)

 R )?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,a),

(b,b),(c,c), (d,d)}. Czy relacja ta jest przechodnia (tzn czy (x,y)  R &

(y,z)  R  (x,z)  R )?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R =

{(a,b), (b,c),

(a,a)}. Czy relacja ta jest przeciwzwrotna (tzn. czy x S (x,x)  R )?

Przykład 2

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,a),(c,c), (d,c), (c,d)}. Czy relacja ta jest symetryczna x,y S ((x,y)  R

 (y,x)  R)?

5

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), (b,c),

(c,d), (d,a)}. Czy relacja ta jest przeciwsymetryczna (tzn. czy

)?

.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(a,c), (b,a)}.

Czy relacja ta jest spójna?

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b),

(b,a),(c,c)}. Czy relacja ta jest symetryczna?

Relacja jest spójna, jeżelix,y S, x ≠ y  (y,x)  R  (x,y)  R

Relacje < i ≤ są relacjami spójnymi w zbiorze liczb rzeczywistych

6

Jeżeli dana relacja jest symetryczna, zwrotnia i przechodnia, to jest

relacją

równoważności, na której definiujemy klasy abstrakcji.

Przykład 3

Relacja   N x N a R b  a mod T = b mod T , jest relacją równoważności
generującą w zbiorze liczb naturalnych N klasę abstrakcji klasę – zbiór liczb
przystających modulo T (podzielnych przez T be z reszty).

a

b

c

a

b

c

S = {a,b,c} ; R’ = {(a,b),(c.b),
(a,c)}

G R A F Y - graficzne reprezentacje relacji.

Graf: G = (S, R

),

gdzie

S

– zbiór wierzchołków,

R

– relacja łącząca

elementy

S

Przykład 4

G = (S, R

) ;

S = {a,b,c} ;R = {(a,b),(b,a),(b,c),(c.b),(c,a),(a,c)}

G = (S, R’) ;

7

Graf skierowany

Graf nieskierowany – krawędzie
odwzorowują
relację
symetryczną.

REPREZENTACJE MACIERZOWE

Macierz sąsiedztwa A

(n x n)

,

Macierz incydencji

M

(n x m)

grafu o n wierzchołkach i m krawędziach

a

i,j

- liczba krawędzi łączących wierzchołek „i” z wierzchołkiem

„j”

m

i,j

= 1 jeśli i-ty wierzchołek jest incydenty z j-tą krawędzią

3 b
4

1 a
2

c d
e

m

i,j

= 0 w przeciwnym wypadku

1 2 3

4

1

0 1

1 0

2

1 0

1 1

A =

3

1 1 0 1

4

0 1 1 0

a b

c d e

1

1 0 1 0 0

2

1 0 0 1 1

M =

3

1 1 1 0 0

4

0 1 0 0 1

8

Modelowanie

Problem mostów królewieckich (1736) Leonard Euler

Przejść przez każdy z mostów dokładnie jeden raz i powrócić do
punktu wyjściowego.

6

7

2

3

1 8

3 5

4

A

D

C

B

C

D

B

A

9

Inny problem tej samej klasy:

Jeszcze jedno zastosowanie

.

Problem sieci wodnej (W), gazowej (G) i elektrycznej (E). Są trzy

domy H

1

, H

2

i H

3

, z których każdy musi być podłączony przewodami

do każdej z trzech sieci. Czy jest możliwe dokonanie takich

połączeń bez skrzyżowania przewodów?

H

1

H

2

H

3

W

G

E

10

11

3. Narysuj rysunek grafu G = (X,R), gdzie X = {x,y,z,w} ,
R={(x,y),(w,x),(w,y),(y,z),(y,z),(w,z)}.
Wyznacz macierze incydencji i sąsiedztwa tego grafu. Wyznacz rząd i

zerowość grafu.

4. Wyznacz macierz incydencji grafu zadanego poniższą macierzą sąsiedztwa

.

0

1

1

1

0

1

1

0

0

ZADANIA

1. Zapisz relację dwuargumentową w zbiorze N określona wzorem:

m+n=5 , max{m,n} = 2

2. Podaj przykład relacji która jest:: antysymetryczna i przechodnia ale nie
jest zwrotna;
symetryczna ale nie jest zwrotna ani przechodnia

5. Czy graf może mieć nieparzystą liczbę wierzchołków nieparzystego
stopnia?
6. Dana jest społeczność X w której istnieją relacje S, S’, S”, S”’  X x
X . Która z tych relacji
jest relacja równoważności?
xSy <=> x jest szefem y ; xS’y <=> x jest przyjacielem
y
xS”y <=> x jest synem y ; xS”’y <=> x ma taki sam
wiek jak y