Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.

Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.:1 Einleitung 1.1 Grundbegriffe der Graphentheorie 1.2 Reduzibilität 2 Über Minoren von Graphen 2.1 Minoren von Graphen 2.2 Topologische Minoren von Graphen 2.3 Baumzerlegung und Baumweite tw(G) 2.4 Wegzerlegung und Wegbreite pw(G) 2.5 Räuber-und-Gendarmen-Spiele auf Graphen 2.6 Resultate und Anwendungen 3 Über Minoren von Digraphen 3.1 Übertragung der Minorenrelation auf Digraphen 3.2 Hindernisse bei der De?nition einer gerichteten Baumweite 3.3 Arboreale Weite dtw(D) 3.3.1 Arboreale Weite und Räuber-und-Gendarmen-Spiele 3.3.2 Resultate und Anwendungen 3.4 Gerichtete Baumweite dtwR(D) 3.5 D-Weite dw(D) 3.6 DAG-Weite dgw(D) 3.6.1 DAG-Weite und Räuber-und-Gendarmen-Spiele 3.6.2 Resultate und Anwendungen 3.7 Räuber-und-Gendarmen-Spiele auf Digraphen 3.8 Eingeschränkte Minorenrelation für Digraphen 3.8.1 Die Teilgraphenrelation für Digraphen 3.8.2 Die topologische Minorenrelation für Digraphen 3.8.3 Die Minorenrelation auf Digraphen nach JRST 3.8.4 Eingeschränkte Minorenrelationen 4 Verbindungen zwischen Reduzibilität und Minoren von Digraphen 4.1 Reduzibilität und initiale Wurzeldigraphen 4.2 Charakterisierung der Reduzibilität durch eingeschränkte Minoren 4.3 Resultate der Minorentheorie für reduzible initiale Wurzeldigraphen 5 Zusammenfassung und Ausblick Literaturverzeichnis Abbildungsverzeichnis