z zadania17 05 2008

ZADANIA DOMOWE PRZED 4. KOLOKWIUM

Jeśli są, to w każdym z nich wyznacz drogę (cykl) Eulera za pomocą algorytmu Fleury’ego.

Zadanie 2

Czy po dodaniu do pierwszego z grafów podanych w zadaniu 1.:

a)    1,

b)    2,

c)    3,

krawędzi można uzyskać graf, w którym będzie istniała droga Eulera? Odpowiedź zilustruj na rysunku!

Zadanie 3

Czy graf pochodny dla dowolnego Eulerowskiego grafu skierowanego jest zawsze Eulerowski? Odpowiedź uzasadnij!

Zadanie 4

Czy graf krawędziowy dla grafu Eulerowskiego jest zawsze Eulerowski? Odpowiedź uzasadnij! Zadanie 5

W grafach z zadania 1. zamień każdą krawędź na łuk tak, aby powstały z nich Eulerowskie grafy skierowane.

Zadanie 6

W podanych grafach sprawdź, które z omawianych na wykładzie i na ćwiczeniach warunków dostatecznych istnienia cyklu Hamiltona (tw. Diraca, Ore, Chyatala, o liczbie krawędzi dla grafów nieskierowanych oraz tw. Redei, Thomassena i Camiona) są spełnione, a które nie:

W2