Exercise 6.1
Prof. Dr.-Ing. Jo ̈rg Raisch
Germano Schafaschek
Soraia Moradi
Behrang Nejad
Fachgebiet Regelungssysteme
Fakulta ̈t IV Elektrotechnik und Informatik Technische Universita ̈t Berlin Lehrveranstaltung ”Ereignisdiskrete Systeme“ Wintersemester 2020/2021
Exercise sheet 6
CoSntrGol
For both precedence graphs G(Ai), i ∈ {1, 2}, shown in Figure 1, solve the following. a) Give an example of an elementary path ρi in G(Ai) such that | ρi |L = 4.
b) Give an example of an elementary circuit θi in G(Ai) such that | θi |W < 5.
c) Give an example of a non-elementary circuit βi in G(Ai).
d) Give an example of a non-elementary path μi in G(Ai) that is not a circuit. e) Determine the elements (A5i )46 and (A6i )22.
Sys
tem
s
Fachgebiet Regelungssysteme
5
254 e8
G(A1): 1 2 3 1 6 4
35
24
e
e
2
2
Figure 1: Precedence graphs for Exercise 6.1.
47 -5
13 1 335
e
G(A2) : 1
Exercise 6.2
Let A ∈ Rn×n be a max-plus square matrix. Prove that, for all k ≥ 1, (Ak)ij is the maximal weight of all paths of length k from node j to node i in G(A), and that (Ak)ij = ε in case no such path exists. (Hint: use natural induction on k.)
6
1