Prof. Dr.-Ing. Jan Lunze

Graphentheoretische Methoden der Systemtheorie

Lehrveranstaltung im Sommersemester 2023

Vorlesung und Übung, 3 SWS, 4 LP
Mittwochs, 10:15 – 13:45 Uhr, Raum ID 03/463

Häufig haben kompliziert erscheinende systemdynamische Eigenschaften relativ einfache Ursachen, die man mit graphentheoretischen Methoden aufdecken kann. Die Lehrveranstaltung zeigt an zahlreichen Szenarien, wie man Modellbildungs-, Analyse- und Entwurfsaufgaben unter Ausnutzung struktureller Eigenschaften systematisch vereinfachen kann. Dabei lernen die Hörer, wie man aus vielfältigen Informationen Strukturgraphen abstrahiert und Probleme der System- und Regelungstheorie mit graphentheoretischen Methoden löst. Viele Anwendungsbeispiele der Elektrotechnik und der Informationstechnik illustrieren dieses Vorgehen.

Ziele der Lehrveranstaltung
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 diese Frage beantworten, 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.

Gliederung
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 her, indem sie die Eigenschaften von Graphen als Parameter und Kenngrößen von Matrizen interpretiert. 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.

Mit dieser Unterteilung spricht die Veranstaltung ein breites Themenfeld an, wobei die Vorlesungen und Übungen jeweils auf die wichtigsten Aspekte eines Themas eingehen und das Skript auch weiterführende Informationen enthält.

Gestaltung der Lehrveranstaltung
Die Lehrveranstaltung gliedert sich in wöchentliche Vorlesungen und Übungen zu je zwei Stunden, was über den Zeitraum von neun Wochen einer Veranstaltung mit 3 Semesterwochenstunden und folglich 4 Leistungspunkten entspricht. Die Aufteilung des Stoffs in die Vorlesungen und die Übungen folgt dem "`Hauptsatz der Didaktik"', der besagt, dass das Produkt aus Genauigkeit der Vermittlung neuen Wissens und der Verständlichkeit einer Lehrveranstaltung konstant ist:

      Genauigkeit * Verständlichkeit = konstant.

Ein sofort in allen Einzelheiten vorgetragener neuer Sachverhalt ist folglich schwer verständlich. Deshalb muss sich jede Vorlesung auf die wichtigsten Fakten, Begriffe und Ansätze konzentrieren und die zu behandelnde Methodik zunächst in ihren Grundzügen schildern, wofür häufig vereinfachende Annahmen eingeführt werden. Wer die groben Züge verstanden und selbst aufgeschrieben hat, kann sich anhand des Skripts ein genaues Bild machen und die Übungsaufgaben lösen, die sich natürlich auf die Methodik mit allen ihren Details beziehen. Darauf aufbauend dienen die Übungen zur Diskussion des Lehrstoffes. Im Sinne einer guten Verständlichkeit werden in den Vorlesungen keine vorgefertigten Bilder und Formelsammlungen gezeigt, sondern die Modellansätze und Lösungsmethoden schrittweise an der Wandtafel vorgeführt. Zahlreiche Beispiele illustrieren den Stoff.

Hinweise für den Besuch der Lehrveranstaltung
Auch bei bester Vorbereitung kann eine Lehrveranstaltung nur effektiv sein, wenn die Teilnehmer die folgenden Hinweise beachten:

Zeitplan