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