Wegesysteme

Göring, Frank

Abstract zur Dissertation Autor: Frank Göring Titel: Wegesysteme _____________________________________________________________________________________________ Path systems are understood to be Graphs. Thus we consider topological minor- ship as a natural relation of containment for graphs. By ¯xing special vertices of a topological minor in the containing graph we specialise this relation to get a short way to formulate theorems about the exi- stence of path systems. Three new and short proofs of Menger's theorem about the existence of a special path system are given. One of these proofs gives both a new version of this theorem including prescribability of initial and terminal vertices of a non-maximal path system for a maximal path system and an easy implementable linear Algorithm for ¯nding the desired path system. It is shown that this theorem contains wellknown theorems of transversal theory (like Hall's marriage theorem and Ford and Fulkerson's theorem about common transver- sals) as special cases. The prescibability of startvertices even will be shown for Mader's theorem. Moreover the new version of Menger's theorem is used to gi- ve a procedure which investigates the following question: Do some connectivity conditions (possibly combined with a given path system) force the existence of a desired path system in a graph? The procedure is constructivly. Either it ¯nds a counterexample, that is, a graph satisfying the given assumptions but not con- taining the desired path system, or it gives an algorithm with a linear running time in the number of vertices and edges of the input graph which constructs the desired path system. More precisely the algorithm either ¯nds a separator showing that the input graph doesn't satisfy the connectivity condition or the desired path system will be constructed. Two examples demonstrate how this procedure works: Two Theorems about the existance of cycles in a given graph containing prescribed vertices will be deduced.

Wegesysteme werden als Graphen abstrahiert, sodaß als natürliche Enthaltenseinsrelation von Graphen die topologische Minorenrelation betrachtet wird. Durch das Fixieren bestimmter Knotenpunkte des topologischen Minors im großen Graphen wird diese Ordnungsrelation spezialisiert, sodaß Existenzsätze über Wegesysteme eine einfache Formulierung bekommen. Zu Mengers Theorem über die Existenz eines bestimmten Wegesystems werden drei kurze und neue Beweise gegeben. Einer dieser Beweise liefert sowohl eine neue Version des Theorems, die die Vorschreibbarkeit der Start- und Endknoten eines nicht maximalen Wegesystems für ein maximales Wegesystem beinhaltet, als auch einen leicht implementierbaren linearen Algorithmus zum Auffinden dieses Wegesystems. Es wird gezeigt, daß diese Version bekannte Theoreme der Transversaltheorie wie Halls Heiratssatz und das Theorem über gemeinsame Transversalen von Ford und Fulkerson als Spezialfälle hat. Auch für Maders Theorem über die Zahl unabhängiger H-Wege wird die Vorschreibbarkeit der Startknoten gezeigt. Die neue Version von Mengers Theorem wird darüber hinaus verwendet, um ein Verfahren zu begründen, mit welchem untersucht werden kann, ob aus gewissen Zusammenhangsvoraussetzungen (evtl. kombiniert mit einem gegebenen Wegesystem) in einem Graphen die Existenz eines gesuchten Wegesystems folgt. Das Verfahren ist konstruktiv. Entweder findet es ein Gegenbeispiel, also einen Graphen mit den gegebenen Voraussetzungen, der das gesuchte Wegesystem nicht enthält, oder es liefert einen Algorithmus, welcher linear in der Zahl der Knoten und Kanten des gegebenen Graphen das gesuchte Wegesystem findet. Genauer wird bei Eingabe eines beliebigen Graphen entweder einen Trenner gefunden, der beweist, daß die Zusammenhangsvoraussetzung nicht gegeben ist, oder das gesuchte Wegesystem selbst wird konstruiert. An Beispielen wird die Funktionsweise des Verfahren demonstriert: Es werden zwei Existenzsätze über Kreise durch vorgeschriebene Knoten eines gegebenen Graphen damit hergeleitet.

Zitieren

Zitierform:

Göring, Frank: Wegesysteme. 2003.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export