buchspektrum Internet-Buchhandlung

Neuerscheinungen 2012

Stand: 2020-01-07
Schnellsuche
ISBN/Stichwort/Autor
Herderstraße 10
10625 Berlin
Tel.: 030 315 714 16
Fax 030 315 714 14
info@buchspektrum.de

Steffen Seidler

Minoren gerichteter Graphen


Eine systematische Einführung in die Minoren gerichteter Graphen und der Anwendung auf reduzible Flussgraphen
Aufl. 2012. 108 S. 220 mm
Verlag/Jahr: AV AKADEMIKERVERLAG 2012
ISBN: 3-639-39952-8 (3639399528)
Neue ISBN: 978-3-639-39952-3 (9783639399523)

Preis und Lieferzeit: Bitte klicken


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. 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. 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. Einschränkungen der möglichen Kontraktionen scheinen ein Ausweg zu sein. Zusammen mit einigen fundamentalen Anforderungen wird dieser Ansatz systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die Minoren-theorie 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.