A

B

C

D

a

f

d

c

e

b

5

4

3

2

1

6

MDA Zadania powtórkowe przed 3. kolokwium

Zadanie 1.
Czy istnieje graf skierowany G, który ma cykl Eulera, ale którego graf pochodny PG nie ma cyklu Eulera?

Zadanie 2.
G = (V, E) graf nieskierowany zdefiniowany jest nastêpuj¹co: zbiór wierzcho³ków V = {1, 2, ..., n}, n ³ 8;
zbiór krawêdzi E = {{i, j}; i = 1,..., n-1; j = i+1}

Ç {n, 1} Ç {n - 2, 4}.

Ile zer ma macierz s¹siedztwa tego grafu?
Czy ten graf ma drogê Eulera? Uzasadnij. Jeœli tak, to jak¹ d³ugoœæ ma ta droga?
Czy ten graf ma cykl Eulera? Uzasadnij. Jeœli nie ma cyklu Eulera, dodaj jak najmniejsz¹ liczbê krawêdzi, ¿eby
w grafie istnia³ cykl Eulera.

Zadanie 3.
Rozwa¿my klasy izomorfizmu grafów nieskierowanych o 5 wierzcho³kach.
Ile jest ró¿nych klas grafów, które maj¹ drogê Eulera?

Zadanie 4.
G = (V, E) graf nieskierowany;

|V|= n, |E|= k;

W którym z poni¿szych przypadków graf G na pewno nie jest planarny. Który mo¿e byæ planarny?
Który musi byæ planarny? Podaj pe³ne uzasadnienie.
(a) n = 6 k = 11; (b) n = 8 k = 19.

Zadanie 7.
Czy graf dwudzielny

ma cykl Hamiltona. Jeœli tak, to zlicz, ile jest ró¿nych cykli Hamiltona w tym grafie.

Zadanie 8.

.

Zadanie 5.
Spróbuj skonstruowaæ graf nieskierowany, który ma 10 wierzcho³ków, 40 krawêdzi i dwie sk³adowe spójne.
Czy istnieje graf spójny o 10 wierzcho³kach i 40 krawêdziach?

Zadanie 6.
Wiemy, ¿e graf nieskierowany G ma cykl Eulera. Czy jego graf krawêdziowy LG musi mieæ cykl Hamiltona?
Jeœli tak - uzasadnij. Jeœli nie, podaj przyk³ad opowiedniego grafu G.

K

7,7

E

F

M jest macierz¹ s¹siedztwa grafu nieskierowanego X.
SprawdŸ, czy w X spe³nione s¹ warunki istnienia cyklu Hamiltona.
Podaj te warunki.
(a) Warunek na liczbê krawêdzi.
(b) Warunek z twierdzenia Diraca.
(c) Warunek z twierdzenia Ore’a.
(d) Czy sekwencja wstêpuj¹ca stopni wierzcho³ków spe³nia warunek
z twierdzenia Chvatala?
(e) Czy graf X jest hamiltonowski? Uzasadnij. Jeœli graf ma cykl Hamiltona - wyznacz ten cykl.
(f) Czy graf X jest dwudzielny?

Zadanie 9.
Czy graf A jest izomorficzny z grafem B? Czy graf C jest izomorficzny z grafem D?
Czy graf E jest izomorficzny z grafem F? Uzasadnij.

ú

ú

ú

ú

ú

ú

ú

ú

ú

û

ù

ê

ê

ê

ê

ê

ê

ê

ê

ê

ë

é

0

1

1

1

1

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

1

1

0

0

1

1

1

1

0

0

0

1

1

1

0

1

1

1

0

1

0

1

0

1

1

1

0

Zadanie 9.
Czy graf SH jest turniejem? Czy w SH spe³none s¹ za³o¿enia tw. Nasha-Williamsa?
Czy spe³nione s¹ za³o¿enia twierdzenia Meyniela? Czy graf ma cykl Hamiltona?
Czy do tego grafu mo¿na dodaæ ³uki w taki sposób, ¿eby by³y spe³nione za³o¿enia twierdzenia
Camiona?

1

2

3

4

5

6

SH

Zadanie 10.
W grafie pe³nym K

n

(Okreœl, jak jest wartoœæ n ?)

1) Wyznacz drzewo rozpinaj¹ce T o kodzie Prüfera ( 4, 4, 5, 3, 3 ).
2) Czy cykl ( 3, 7, 5, 4, 3 ) jest cyklem fundamentalnym tego grafu wzglêdem drzewa T ? Uzasadnij.
Czy cykl ( 3, 5, 4, 3 ) jest fundamentalny wzglêdem T? Uzasadnij.
4) Przedstaw cykl ( 4, 3, 2, 1, 5, 4 ) jako ró¿nicê symetryczn¹ cykli fundamentalnych.

Zadanie 11.
Rozpatrzmy graf dwudzielny G = K

100,97

.

Niech T bêdzie drzewem rozpinaj¹cym grafu G.

Niech y oznacza liczbê wszystkich cykli fundamentalnych grafu G (wzglêdem drzewa T).
Podaj jak najwê¿szy przedzia³, w jakim mieœci siê liczba y. Uzasadnij.
.