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
Wyszukiwarka
Podobne podstrony:
zad(2) dom zaocz GSzad(3) dom zaocz GSzad(5) dom zaocz GSGS zad dom(6)zad dom met bad rol 11 zimaMPW zad dom 3Zad dom 4 gr7Przykład Zad Dom 1zad domzad dom md zMPO zad dom 3zad przedkol GSZałącznik nr 18 zad z pisow wyraz ó i u poziom Iwięcej podobnych podstron