2
x
x
1
G: p
e
10
14 n
a
d
7
g k
8 8
s
s
y
y b 4
8 3
t
t
6
6
f
m
c
15
h j
7
12
5
v
v
ZADANIE 1.
W powyższej sieci przepustowoSci zaznaczone są przy łukach liczbami podkreSlonymi. Wyznacz przepływ maksymalny
w tej sieci. Wyznacz minimalny przekrój.
ZADANIE 2.
Dlaczego w definicję Scieżki powiększającej włączono warunek, że jest to droga prosta (w grafie pochodnym)?
ZADANIE 3.
(1) Rozpoczynając od wierzchołka 2, zbuduj w grafie G drzewo rozpinające T , przeszukując graf wszerz.
(2) Wyznacz kod Prûfera drzewa T.
(3) Wskaż wszystkie cykle fundamentalne względem drzewa T.
(4) Przedstaw cykl (6, 1, 4, 8, 5, 3, 6) jako różnicę symetryczną cykli fundamentalnych.
(5) Ile wynosi w G maksymalna liczba dróg krawędziowo rozłącznych między wierzchołkami 6 i 8?
(6) Ile wynosi w G maksymalna liczba dróg wierzchołkowo rozłącznych między wierzchołkami 6 i 8?
(7) StosujÄ…c odpowiedniÄ… wersjÄ™ tw. Mengera, wyznacz minimalnÄ… moc zbioru rozspajajÄ…cego (rozdzielajÄ…cego )
wierzchołki 6 i 8 oraz wskaż taki zbiór krawędzi (wierzchołków) o minimalnej mocy.
(8) Ile wynosi spójnoSć krawędziowa (wierzchołkowa) tego grafu? Uzasadnij.
(9) Czy w tym grafie istniejÄ… zbiory rozspajajÄ…ce (rozdzielajÄ…ce) minimalne, ale nie o minimalnej mocy?
ZADANIE 4.
W grafie peÅ‚nym K8 wyznacz drzewo rozpinajÄ…ce o kodzie Prûfera (3,7,3,7,1,4).
ZADANIE 5.
Czy w grafie H sekwencja wstępująca stopni wierzchołków spełnia warunek Chvatala?
Czy w H istnieje cykl Hamiltona?
JeSli H nie spełnia war. Chvatala, dodaj do grafu jak najmniej krawędzi, by ten war. był spełniony.
Czy ten nowy graf spełnia war. Ore a?
ZADANIE 6.
Czy graf SH jest turniejem? Czy spełnia warunki z tw. Nasha-Williamsa?
Czy spełnia założenia twierdzenia Meyniela? Czy ma cykl Hamiltona?
2 3
2 3
H:
SH:
4
1 4
1
6
6
5
5
ZADANIE 7.
Niech K = (V, E) będzie pewnym grafem nieskierowanym, V = {1, 2, ..., n }.
X = { {i, j} E: j = a d(i) > 2}.
Y = { v V: ( V {v, w} X) ( ( v1 , v2 , v3 ) , vi V, v1 = b, v3 = v, {vi ,vj} E, i, j = 1, 2, 3)}
w
Przyjmując a = 4, b = 2, zaznacz zbiór X Y na rysunku grafu H.
Wyszukiwarka
Podobne podstrony:
Zad(4)dom GS zaoczzad(2) dom zaocz GSzad(3) dom zaocz GSGS zad dom(6)zad(5) dom zaocz GSZałącznik nr 18 zad z pisow wyraz ó i u poziom Izadzad 12009 rozw zadwięcej podobnych podstron