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 .
Ile zer ma macierz sÄ…siedztwa tego grafu?
Czy ten graf ma drogÄ™ Eulera? Uzasadnij. JeS
li tak, to jaką długoS
ć ma ta droga?
Czy ten graf ma cykl Eulera? Uzasadnij. JeS
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 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?
JeS
li tak - uzasadnij. JeS
li nie, podaj przykład opowiedniego grafu G.
Zadanie 7.
Czy graf dwudzielny K ma cykl Hamiltona. JeS
li tak, to zlicz, ile jest różnych cykli Hamiltona w tym grafie.
7,7
Zadanie 8.
M jest macierzÄ… sÄ…siedztwa grafu nieskierowanego X.
. 0 1 1 1 0 1 0
Sprawdx
, czy w X spełnione są warunki istnienia cyklu Hamiltona.
1 0 1 1 1 0 1
Podaj te warunki.
(a) Warunek na liczbę krawędzi.
1 1 0 0 0 1 1
(b) Warunek z twierdzenia Diraca.
1 1 0 0 1 1 1
(c) Warunek z twierdzenia Ore a.
0 1 0 1 0 0 1
(d) Czy sekwencja wstępująca stopni wierzchołków spełnia warunek
z twierdzenia Chvatala?
1 0 1 1 0 0 1
(e) Czy graf X jest hamiltonowski? Uzasadnij. JeS
li graf ma cykl Hamiltona - wyznacz ten cykl.
0 1 1 1 1 1 0
(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.
A
B C
a
D
4
d
5
3
f
6
c
1
2
e
b
E
F
Zadanie 9.
2 3
SH
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?
4
Czy do tego grafu można dodać łuki w taki sposób, żeby były spełnione założenia twierdzenia 1
Camiona?
6
5
Zadanie 10.
W grafie pełnym K n (OkreS
l, jak jest wartoS
ć 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 mieS
ci siÄ™ liczba y. Uzasadnij.
.