Zadanie 1.
Sprawdx
, czy sekwencja wstępująca stopni wierzchołków poniższego grafu jest ciągiem hamiltonowskim.
5 1
3
2 4
Zadanie 2.
(Punkt (1) tego zadania jest obowiązkowy.)
Macierz M jest macierzą incydencji pewnego grafu G.
(1) Czy w tym grafie spełnione są warunki dostateczne (Diraca, Ore a, na liczbę krwawędzi) istnienia
cyklu Hamiltona?
(2) Czy sekwencja wstępująca stopni wierzchołków tego grafu jest ciągiem hamiltonowskim?
(3) Czy ten graf ma cykl Hamiltona?
1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 1 1 0 0 1 0 0 1
0 0 0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 1 1
Zadanie 3.
(1) (obowiązkowy) W poniższym grafie H zbuduj drzewo rozpinające T metodą przeszukiwania grafu wszerz.
zaczynając od wierzchołka 7.
(2) Wyznacz kod Prufera tego drzewa.
(3) Wyznacz zbiór wszystkich cykli fundamentalnych względem T.
(4) Przedstaw cykl (1, 2, 5, 3, 6, 4, 1) jako różnicę symetryczną cykli fundamentalnych.
Zadanie 4.
(1) Wyznacz w poniższym grafie H maksymalną liczbę dróg wierzchołkowo rozłącznych między
wierzchołkami 1 i 9. Wskaż te drogi.
Stosując twierdzenie Mengera (w wersji wierzchołkowej), wyznacz minimalną moc zbioru rozdzielającego wierzchołki
1 i 9.
(2) Wyznacz w H maksymalną liczbę dróg krawędziowo rozłącznych między 1 i 9. Stosując tw. Mengera
(w wersji krawędziowej), wyznacz minimalną moc zbioru rozspajającego wierzchołki 1 i 9 oraz wskaż taki zbiór
minimalnej mocy.
(3) Ile wynoszą spójnoS
ć wierzchołkowa oraz spójnoS
ć krwędziowa tego grafu?
7
H
c
2
b
7
c d
2
a
b
5
i
d e
a
5
j
1
i
e 3
9
j
1
k
3
9
k l
f
6
g
l
f
6
4
g
h
4
8
h
8
7
7
c
2
b
c
2
b
d
a
5 d
a
5
i
e
i
e
j
1
j
3
1
9 3
9
k
k
l
f
6
g l
f
6
g
4
h 4
h
8
8