Matematyka dyskretna

Seria 3

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

2. Czy możliwe jest aby owad poruszający się wzdłuż krawędzi sześcianu przeszedł każdą krawędź dokładnie raz?

3. 
   Które grafy pełne
   mają cykle Eulera?

4. 
   
   
   
   
   
   
   
   
   
   
   
   
   Rozważmy graf pokazany na Rys. 2. Opisz drogę Eulera dla tego grafu lub wyjaśnij dlaczego taka droga nie istnieje.

Z. Domański

v

s

u

r

t

w

s

w

t

u

v

v

w

u

z

y

x

y

x

z

y

x

z

Rysunek 1

s

z

y

Rysunek 2

u

v

t