Minoren gerichteter Graphen

Seit 1983 begrndet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mchtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Fr gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie. Verschiedene Anstze 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. Enge Verbindungen zu zwei gerichteten Ruber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen fr ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf. Einschrnkungen der mglichen Kontraktionen scheinen ein Ausweg zu sein. Zusammen mit einigen fundamentalen Anforderungen wird dieser Ansatz systematisch verfolgt und schrittweise Einschrnkungen betrachtet. Die Minoren-theorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie gegenbeispiele fr die beschrnktheit der dag-weite. analoge resultate folgen fr die jeweiligen gerichteten ruber-und-gendarmen-spiele.