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ń.

1. Podaj tablicę wartości funkcji A i L dla tej sieci.

2. Znajdź rezerwy czasowe wierzchołków.

3. Znajdź drogi krytyczne.

4. Znajdź rezerwy czasowe krawędzi.

3. Rozważmy sieć przedstawioną na Rysunku 3.

1. Ile jest dróg krytycznych w tym grafie?

2. Jaka jest największa rezerwa czasowa krawędzi w tym grafie skierowanym?

3. Które krawędzie mają największą rezerwą czasową?

Z. Domański

v 7 x 4 f

s 3 w 4 y 5 z

Rysunek 1

1 7

6 2 3 1 3

v

u 3 x

5 4 4

Rysunek 2

s w y f

7 2 5

2 2 6 3

Rysunek 3

s u w x f

3 1 5

2 2 2 3

t 6 y

1 1 1 2

r 4 v 6 z