MDA ID zadprzedkol(3) cz2 13 14

background image

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.

background image

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

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
MDA ID zadprzedkol(3),1 2013 14
Cwiczenia nr 13 (z 14) id 98681 Nieznany
cwiczenie9b am 13 14 id 125935 Nieznany
Materialy do seminarium tech chem 13 14 id 284873
cwiczenie10a am 13 14 id 125803 Nieznany
cwiczenie8a am 13 14 id 125925 Nieznany
cwiczenie2c am 13 14 id 125856 Nieznany
cwiczenie10b am 13 14 id 125804 Nieznany
cwiczenie7a am 13 14 id 125918 Nieznany
Cwiczenia nr 13 (z 14) id 98681 Nieznany
MDA ID punktacja(1,2) 2013 14
cwiczenie8b am 13 14
lek przewodnik 13 14 i r
np ps 13 14

więcej podobnych podstron