Matematyka dyskretna

Seria 1

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

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

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 g podana jest w następującej tabeli:

E                               a                 b                 c                d                 e                 f                g

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