Matematyka dyskretna

Seria 1

1. Podaj tabelę funkcji γ dla każdego z grafów skierowanych z Rys.1.

2. Wykonaj rysunek grafu skierowanego G, w którym zbiór wierzchołków V(G) = {w,x,y,z}, zbiór krawędzi E(G) = {a,b,c,d,e,f,g}, a funkcja γ podana jest w następującej tabeli:

E a b c d e f g

γ(E) (x,w) (w,x) (x,x) (w,z) (w,y) (w,z) (z,y)

3. Są 4 grupy krwi A, B, AB i 0. Grupa 0 może być podawana każdemu, grupy A i B mogą być podawane osobom mającym grupę AB lub odpowiednio A lub B. Grupa AB może być podawana tylko osobom z grupą krwi AB. Narysuj graf skierowany, który przedstawia te informacje. Czy graf ten jest acykliczny?

4. Podaj relacje osiągalności dla grafów skierowanych z Rys.1. oraz zbuduj macierze sąsiedztwa dla tych grafów.

5. Relacja R w zbiorze S = {1,2,3,4,5} jest określona w następujący sposób: (m,n)  R, jeśli liczba m-n jest parzysta. Zbuduj macierz tej relacji i określ jej własności.

Z. Domański

Rys. 1b

Rys. 1a

a

w

v

w

v

c

b

e

d

b

a

d

d

y

x

y

x

f

Rys. 1c

b

a

c

c

z

y

x