MDA Zadania treningowe przed 3. kolokwium - cz. 2.
Zadanie M 1.
1. Ile wynosi w G maksymalna liczba dróg krawędziowo rozłącznych między wierzchołkami 6 i 8?
2. Ile wynosi w G maksymalna liczba dróg wierzchołkowo rozłącznych między wierzchołkami 6 i 8?
3. 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.
4. Ile wynosi spójnoS
ć krawędziowa (wierzchołkowa) tego grafu? Uzasadnij.
5. Czy w tym grafie istnieją zbiory rozspajające (rozdzielające) minimalne, ale nie o minimalnej mocy?
G
2
G
2
1 p
e
1 p
e
n
a
n
d
a
d
g k
8
g k
8 b 4
b 4 3
6
3
6
r
f
m
r
f
m c
c
h j
h j
7
5
7
5
G
2
1 p
e
G
2
n
a
1 p
e d
n
g k
a 8
d
b 4
3
g k
6
8
b 4
r
f
m
3
6 c
r
f h j
m
7
c
5
h j
7
5
Zadanie S1
Na następnej stronie jest rysunek sieci S1 oraz kilkanaS
cie schematów tej sieci; s jest x
ródłem, t jest ujS
ciem sieci.
W sieci S1 przepustowoS
ć każdego łuku wynosi 40.
Nad łukami zaznaczono wartoS
ci pewnej funkcji. Nie dla wszystkich łuków te wartoS
ci są podane.
1) Uzupełnij wartoS
ci funkcji (dla siedmiu łuków, dla których wartoS
ć nie jest podana) w taki sposób,
by otrzymać funkcję przepływu ze x
ródła s do ujS
cia t. Otrzymasz pewien przepływ F.
(Na rysunku wpisz te wartoS
ci nad łukami.)
2) Wyznacz przekrój PU sieci odpowiadający zbiorowi wierzchołków U = {s, a ,b, g, h}.
(Wypisz i zaznacz na schemacie łuki wchodzące w skład przekroju PU.)
3) Wyznacz przepustowoS
ć przekroju PU.
/4) Wyznacz wartoS
ć przepływu F przez przekrój PU./
5) Konstruując ciąg S
cieżek powiększających (wystartuj, oczywiS
cie, z przepływu F ), wyznacz przepływ
maksymalny w sieci S1.
(R
cieżki zaznacz na kolejnych rysunkach oraz wypisz je pod rysunkiem, odpowiadającym danej S
cieżce.
Oblicz również wartoS
ć przepływu, jaki otrzymujesz w każdym kroku algorytmu.)
6) Udowodnij, że w efekcie procedury otrzymany został przepływ maksymalny.
(Zaznacz na rysunku wartoS
ci końcowego przepływu maksymalnego.)
7) Wyznacz przekrój o minimalnej przepustowoS
ci.
39
S1
39 37
37 a e
i
a e
i
1
1 40
40
0
1
0
1 j 0
b f
j 0
4
b f
4
1
1 s
t
s 6
t
6 2
2
5
0
5
0
k
c g
k
c g
7
7 2
0
2
0
d l
h
d l
h 2
2
a e i
a e i
a e i
j
j
b f
b f
j
b f
s
s
t
t
s
t
k
k c g
c g
k
c g
d l
d l h
h
d l
h
a e i
a e i
a e i
j
j
b f
b f
j
b f
s
s
t
t
s
t
k
k c g
c g
k
c g
d l
d l h
h
d l
h
a e i
a e i
a e i
j
j
b f
b f
j
b f
s
s
t
t
s
t
k
k c g
c g
k
c g
d l
d l h
h
d l
h
a e i
a e i
a e i
j
j
b f
b f
j
b f
s
s
t
t
s
t
k
k c g
c g
k
c g
d l
d l h
h
d l
h
Zadanie S2
W sieci S2 = ((V, A), c), (s jest x
ródłem, t jest ujS
ciem ), przepustowoS
ci łuków c (x,y) zaznaczono przy łukach liczbami podkreS
lonymi.
Początkowa funkcja przepływu F ma wartoS
ć 0 dla każdego łuku (x,y).
(1) Czy S
cieżka p1 = (s, b, e, g, t) jest S
cieżką powiększającą przepływ F ? Uzasadnij.
(2) Wyznacz przepustowoS
ć przekroju PU odpowiadającego zbiorowi wierzchołków U = {s, b, g, d }.
(3) Budując ciąg S
cieżek powiększających, wyznacz przepływ maksymalny ze x
ródła s do ujS
cia t .
Wypisz tworzone po kolei S
cieżki i zaznacz je na schematach sieci. Na każdym kroku algorytmu
oblicz wartoS
ć W(MF) uzyskanego przepływu MF.
(4) Zaznacz na schemacie sieci uzyskany końcowy przepływ maksymalny.
(5) Wskaż przekrój sieci między x
ródłem s a ujS
ciem t, mający minimalną przepustowoS
ć.
Uzasadnij, że jest to przekrój o minimalnej przepustowoS
ci.
(6) Uzasadnij fakt, że wyznaczony końcowy przepływ MF jest rzeczywiS
cie przepływem maksymalnym.
20
a
a
d
d
10
S2
20
20
20 10
g
g
20
10
15
20
20
s
s
e
e
b
b
10
t
t
20
5
20
20
20
h
h
30
c
c
f
f 10
20
k
k
a
d a
d
g
g
s e
b
s e
b
t
t
h
h
c
f c
f
k
k
a
d
a
d
g
g
s e
b
s e
b
t
t
h
h
c
f
c
f
k
k
a
d
a
g d
s e
b g
t
s e
b
h t
c
h
f
c
f
k
k