[SOLVED] CS Exercise 6.1

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.SystemsFachgebiet Regelungssysteme 5254 e8G(A1): 1 2 3 1 6 43524ee22Figure 1: Precedence graphs for Exercise 6.1.47 -513 1 335e G(A2) : 1Exercise 6.2Let A Rnn 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