md1

A

ZADANIA DOMOWE PRZED 4. KOLOKWIUM NA ST DZIENNYCH

Zadanie I    'TĄic UoIm» Irmiiri

Ro/atr/> gnij / uzasadnieniem czy piy o podanych rysunkach lą Hulerowskic:

Hi s%Ww każdym z nich wyznacz drogę (cykl) Eulera /a pomocą algorytmu Fleuiy*egp \J Zadanie 2

Czy po dodaniu do pierwszego z grafów podanych w zadaniu 1 a) 1.    6)2.    e) 3.

krawędzi można uzyskać graf. w który m będzie isuuala droga Eujsra? Odpowiedź zilustruj ni

* ZI» §§ (SB™ 523>-“ ®P> i, \ | p

Czy graf pochodny dla dDwtfhego Eulerowskiego grafu skierowanego jest zawsze Eulerowski?! jw ^ Odpowiedź uzasadnij! tjAK    ;5q

Zadanie 4    \

C/>' graf krawędziowy dla grafu Eulerowskiego jest zaws/e Eulerowski? Odpowiedź uzasadnij 11 ^ Zadanie 5

W grafach z zadania I zamień każdą krawędź na luk lak. aby pgwitatyz nich Eulerowskio grały, skierowane. z    t    jjl _c.

1t*    !

iii

W podanych gnu£Hspraw& ktiire z omawianych na wykładzie i na ćwiczeniach warunków*

dostatecznych istnienia cyklu Hamiltona (tw. Diraca, Ore, Cłndtala, o liczbie krawędzi dla grafów meskicrowanych oraz tw. Reda, Thomossena i Coraiona) są spełnione, a które nie: