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