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.
.