Matematyka dyskretna

Seria 4

1. Który z grafów ma cykl Eulera? Podaj ciąg wierzchołków w cyklu Eulera w każdym przypadku, w którym istnieje taki cykl.

2. 
   Który z poniższych grafów jest grafem Hamiltona? Znajdź cykle Hamiltona dla tych grafów.

3. Dla podanych poniżej map skonstruuj grafy. Znajdź drogi Eulera dla tych grafów.

4. Czy graf pełny K_m jest grafem Hamiltona?

Z. Domański

v₁

v₂

v₃

v₄

v₅

v₆

v₇

v₈

v₉

v₁₀

c

e

g

h

f

d

a

b

k

j

i

a

b

c

d

e

f

g

h

a

b

c

f

e

d

g

h

v₁

v₂

v₃

v₄

v₅

v₁

v₂

v₃

u

v₄

v₅

v₆

v₇

v₈

v

water

land

A

B

C

D

E

F

G