Matematyka dyskretna

Seria 6.

1. Znajd drog krytyczn dla grafu z

Rysunku 1. Odpowiedz na pytanie
dlaczego metoda drogi krytycznej
stosuje

si

tylko

do

grafów

acyklicznych?

2. Rysunek 2 przedstawia sie zdarze .
a) Podaj tablic warto ci funkcji A i L dla tej

sieci.

b) Znajd rezerwy czasowe wierzchołków.
c) Znajd drogi krytyczne.
d) Znajd rezerwy czasowe kraw dzi.

3. Rozwa my sie przedstawion na Rysunku 3.
a) Ile jest dróg krytycznych w tym grafie?
b) Jaka jest najwi ksza rezerwa czasowa kraw dzi w tym grafie skierowanym?
c) Które kraw dzie maj najwi ksz rezerw czasow ?

Z. Doma ski

r

4 v 6 z

1 1 1 2

t

6 y

2 2 2 3

3 1 5

s u w x f

Rysunek

3

6 2 3 1 3

1 7

Rysunek

1

s

3 w 4 y 5 z

v

7 x 4 f

2 2 6 3

7 2 5

s w y f

Rysunek

2

5 4 4

u

3 x

v