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ójnoœæ krawêdziowa (wierzcho³kowa) tego grafu? Uzasadnij.
5. Czy w tym grafie istniej¹ zbiory rozspajaj¹ce (rozdzielaj¹ce) minimalne, ale nie o minimalnej mocy?

6

1

3

5

2

4

7

8

a

b

c

d

e

g

f

h

j

m

k

n

p

r

G

6

1

3

5

2

4

7

8

a

b

c

d

e

g

f

h

j

m

k

n

p

r

G

6

1

3

5

2

4

7

8

a

b

c

d

e

g

f

h

j

m

k

n

p

r

G

6

1

3

5

2

4

7

8

a

b

c

d

e

g

f

h

j

m

k

n

p

r

G

Zadanie S1
Na nastêpnej stronie jest rysunek sieci S1 oraz kilkanaœcie schematów tej sieci; s jest Ÿród³em, t jest ujœciem sieci.

W sieci S1 przepustowoœæ ka¿dego ³uku wynosi 40.
Nad ³ukami zaznaczono wartoœci pewnej funkcji. Nie dla wszystkich ³uków te wartoœci s¹ podane.

1) Uzupe³nij wartoœci funkcji (dla siedmiu ³uków, dla których wartoœæ nie jest podana) w taki sposób,
by otrzymaæ funkcjê przep³ywu ze Ÿród³a s do ujœcia t. Otrzymasz pewien przep³yw F.
(Na rysunku wpisz te wartoœci nad ³ukami.)
2) Wyznacz przekrój P

U

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 P

U.

)

3) Wyznacz przepustowoϾ przekroju P

U

.

/4) Wyznacz wartoœæ przep³ywu F przez przekrój P

U

./

5) Konstruuj¹c ci¹g œcie¿ek powiêkszaj¹cych (wystartuj, oczywiœcie, z przep³ywu F ), wyznacz przep³yw
maksymalny w sieci S1.
(Œcie¿ki zaznacz na kolejnych rysunkach oraz wypisz je pod rysunkiem, odpowiadaj¹cym danej œcie¿ce.
Oblicz równie¿ wartoœæ przep³ywu, jaki otrzymujesz w ka¿dym kroku algorytmu.)
6) Udowodnij, ¿e w efekcie procedury otrzymany zosta³ przep³yw maksymalny.
(Zaznacz na rysunku wartoœci koñcowego przep³ywu maksymalnego.)
7) Wyznacz przekrój o minimalnej przepustowoœci.

MDA Zadania treningowe przed 3. kolokwium - cz. 2.

s

a

b

c

d

e

f

g

h

i

j

k

l

t

37

39

4

7

2

0

2

6

1

0

1

40

0

2

1

0

5

s

a

b

c

d

e

f

g

h

i

j

k

l

t

37

39

4

7

2

0

2

6

1

0

1

40

0

2

1

0

5

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

s

a

b

c

d

e

f

g

h

i

j

k

l

t

S1

s

a

b

c

d

e

f

g

h

k

t

20

s

a

b

c

d

e

f

g

h

k

t

s

a

b

c

d

e

f

g

h

k

t

20

20

20

20

20

20

20

20

20

20

20

10

10

15

10

30

10

5

10

s

a

b

c

d

e

f

g

h

k

t

s

a

b

c

d

e

f

g

h

k

t

s

a

b

c

d

e

f

g

h

k

t

s

a

b

c

d

e

f

g

h

k

t

s

a

b

c

d

e

f

g

h

k

t

Zadanie S2
W sieci S2 = ((V, A), c), (s jest Ÿród³em, t jest ujœciem ), przepustowoœci ³uków c (x,y) zaznaczono przy ³ukach liczbami podkreœlonymi.
Pocz¹tkowa funkcja przep³ywu F ma wartoœæ 0 dla ka¿dego ³uku (x,y).
(1) Czy œcie¿ka p1 = (s, b, e, g, t) jest œcie¿k¹ powiêkszaj¹c¹ przep³yw F ? Uzasadnij.
(2) Wyznacz przepustowoœæ przekroju P odpowiadaj¹cego zbiorowi wierzcho³ków U = {s, b, g, d }.

U

(3) Buduj¹c ci¹g œcie¿ek powiêkszaj¹cych, wyznacz przep³yw maksymalny ze Ÿród³a s do ujœcia t .
Wypisz tworzone po kolei œcie¿ki i zaznacz je na schematach sieci. Na ka¿dym kroku algorytmu
oblicz wartoœæ W(MF) uzyskanego przep³ywu MF.
(4) Zaznacz na schemacie sieci uzyskany koñcowy przep³yw maksymalny.
(5) Wska¿ przekrój sieci miêdzy Ÿród³em s a ujœciem t, maj¹cy minimaln¹ przepustowoœæ.
Uzasadnij, ¿e jest to przekrój o minimalnej przepustowoœci.
(6) Uzasadnij fakt, ¿e wyznaczony koñcowy przep³yw MF jest rzeczywiœcie przep³ywem maksymalnym.

S2