Neue Lehrveranstaltung
Graphentheoretische Methoden der Systemtheorie (141 015)
Prof. Dr.-Ing. Jan Lunze
Vorlesung mit Übungen
3 SWS im Sommersemester
| Vorlesung und Übung: |
Mi. | 10:15 - 13:45 Uhr - ID 03/463 |
| Die MATLAB-Übungen finden in CIP-Pool 2 (ID 03/121) statt. | ||
Beginn: Mittwoch, den 05.04.2023
Moodle: 
Didaktisches Konzept
Die Lehrveranstaltung soll zeigen, dass wichtige systemdynamische Eigenschaften im Wesentlichen von der Frage abhängig sind, welche Signale oder Komponenten eines dynamischen Systems mit welchen anderen verkoppelt sind. Graphen, die die Systemstruktur darstellen, sind anschaulich, erleichtern das intuitive Verständnis von Analyse- und Entwurfsverfahren und erklären, wann bestimmte Eigenschaften auftreten und wann nicht. Darüber hinaus gibt es natürlich viele Eigenschaften, die auch durch die Parameterwerte des Systems beeinflusst werden und nicht allein aus einer strukturellen Betrachtung abgeleitet werden können. Die Grenze zwischen beiden Gebieten aufzuzeigen, ist ein weiteres wichtiges Ziel dieser Lehrveranstaltung.
Die Grundlagen der Graphentheorie sollen nur so weit erläutert werden, wie sie für die Behandlung der einzelnen Themen notwendig sind. Deshalb ist die Lehrveranstaltung in drei Teile unterteilt:
I. Methoden, die die Grundbegriffe der Graphentheorie und Graphensuche nutzen
Bei der Graphensuche werden gerichtete oder ungerichtete Graphen systematisch „durchschritten“, um Pfade zwischen zwei Knoten zu finden bzw. Graphen in stark verbundene Teilgraphen zu zerlegen. Diese Methoden führen auf systematische Lösungsverfahren für logische Entscheidungsprobleme und zu Bayesnetzen, die eine Verbindung zwischen der Graphentheorie und der Wahrscheinlichkeitsrechnung herstellen.
- Wichtige graphentheoretische Methoden:
Erreichbarkeitsanalyse gerichteter Graphen, Zerlegung von Graphen in stark zusammenhängende
Komponenten, Graphensuche (Dijkstra-Algorithmus, A*-Algorithmus), Systemanalyse mit Bayesnetzen,
MATLAB-Funktionen zur Behandlung von Graphen - Anwendungsbeispiele:
Routenplanung im Straßenverkehr, Bahnplanung von Robotern, Diagnose eines Motorkühlsystems,
Modellierung und Verhalten einer Heckleuchte
II. Methoden, die auf der algebraischen Graphentheorie beruhen
Die algebraische Graphentheorie stellt eine Verbindung zwischen den algebraischen Modellen dynamischer Systeme und graphentheoretischen Verfahren dar, denn sie interpretiert die Eigenschaften von Graphen als Parameter und Kenngrößen von Matrizen. Umgekehrt bestimmt sie Eigenschaften von Matrizen wie deren Rang oder deren Determinante als Kenngrößen eines Graphen. Damit bildet sie die Grundlage für verschiedene Zerlegungs- und Aggregationsverfahren und führt auf generische Eigenschaften linearer Systeme (z. B. Steuerbarkeit und Beobachtbarkeit) sowie zu Analysemethoden von Netzwerken.
- Wichtige graphentheoretische Methoden:
Erreichbarkeitsanalyse mit Adjazenzmatrizen, graphentheoretische Interpretation des Rangs
und der Determinante einer Matrix, Mason-Regel, Lösung von Maximalflussproblemen
(Max-Flow-Min-Cut-Theorem), Fundamentalzyklen und Zyklenraum von Graphen - Anwendungsbeispiele:
Verhalten geregelter Gleichstrommotoren, Kopplungsanalyse von Elektroenergienetze,
Zustandsbeobachtung einer Verladebrücke, Datenfluss- und Verkehrsflussprobleme,
Fahrdynamik bei Abbremsvorgängen, Modellierung und Verhalten von RC-Schaltungen,
Lastfluss in Elektroenergiesystemen
III. Methoden, die bipartite Graphen nutzen
Bipartite (paare) Graphen werden genutzt, um Modellgleichungen zu manipulieren, so dass erkennbar wird, welche Ausgangsgrößen eines Systems eindeutig durch ein Modell bestimmt sind. Die Modellgleichungen werden als Constraints für die in ihnen vorkommenden Variablen interpretiert. Ihre Darstellung durch bipartite Graphen ermöglicht die Zerlegung des Modells in Teilmodelle mit unterschiedlichen Eigenschaften.
- Wichtige graphentheoretische Methoden:
Eigenschaften und DM-Zerlegung von bipartiter Graphen - Anwendungsbeispiele:
Lösung linearer Gleichungssysteme mit Anwendung auf elektrische Netze
Zusammenstellung der behandelten systemtheoretischen Probleme und Methoden:
- Zustandsraumdarstellung von Entscheidungsproblemen
- Architektur von Suchsystemen
- Kausales und diagnostisches Schließen mit Bayesnetzen
- Berechnung des E/A-Verhaltens gekoppelter Systeme mit der Masonformel
- Dekomposition gekoppelter Systeme
- Ford-Fulkerson-Algorithmus zur Lösung von Maximalflussproblemen
- Generische Eigenschaften dynamischer Systeme
- Graphentheoretische Methoden zur Modellierung von elektrischen Netzwerken
- Strukturelle Methoden zur Lösung linearer Modellgleichungen
