1

Podstawy systemów dyskretnych

dr inż. Grzegorz Bazydło

[e-mail], www.uz.zgora.pl/~gbazydlo

Lista zadań nr 2

Zadanie 1

Określ liczbę wierzchołków, krawędzi oraz stopień każdego wierzchołka dla podanego grafu:
a)

b)

Zadanie 2

Poniżej zaprezentowano wzór cząsteczki metanu (CH

4

) oraz propanu (C

3

H

8

):

metan

propan

a) Traktując powyższe diagramy jako grafy, co możesz powiedzieć o wierzchołkach reprezentujących atom

węgla (C) lub wodoru (H)?

b) Istnieją dwie różne cząsteczki o wzorze chemicznym C

4

H

10

. Narysuj grafy im odpowiadające.

Zadanie 3

Narysuj graf o wierzchołkach A, B,…, M, który reprezentuje różne trasy, jakie można przebyć pokonując labi-

rynt przy pałacu Hampton Court:

Zadanie 4

Sprawdź, czy dane dwa grafy są izomorficzne:
a)

b)

2

Zadanie 5

Odszukaj każdy z trzech podanych grafów (i, ii oraz iii):

w poniższych grafach:

Zadanie 6

Który z poniższych grafów jest podgrafem grafu z rysunku a) z zadania 4?