Version vom 30.06.2015 Max-Flow in Orientierten Matroiden Winfried Hochstättler & Robert Nickel...

Version vom 26.04.23

Max-Flow in Orientierten Matroiden

Winfried Hochstättler & Robert Nickel

Fernuniversität in HagenLehrstuhl für Diskrete Mathematik und Optimierung

2 von 13

Überblick

Max-Flow in GraphenOrientierte MatroideMax-Flow-Problem in Orientierten MatroidenDekompositionMaxflow-„Mincut“ in Orientierten Matroiden

3 von 13

Maximale Flüsse in Digraphen

+ -Quelle Senke

Max-Flow = Min-Cut

Max-Flow

Fluss

s-t-Fluss: Kirchhoffsche Gesetze gelten in inneren KnotenRundfluss: Kirchhoffsche Gesetze gelten in allen Knoten

Der Fluss ist entlang jedes Schnittes gleich 0

Jeder Rundfluss ist Summe gerichteter Kreise

8 3

5

Kapazität auf jeder Kante

4 von 13

Problembeschreibung verzichtet auf Knoten, denn:

Problemformulierung

Gegeben:Digraph Menge aller Rundflüsse in Kapazität

Gesucht:

5 von 13

Orientierte Matroide

Sei E eine Menge von Kanten / ElementenEin Vektor heißt gerichtete Teilmenge von EKreise im Digraph sind gerichtete Teilmengen von E Eigenschaften ( = Menge aller Kreise):

und

Flussgitter:

6 von 13

Die Menge heißt orientiertes Matroid, wenn sie die Kreisaxiome erfülltRang von :

Beispiele:Gerichtete Kreise (oder auch Schnitte) eines DigraphenMinimal linear abhängige Spalten einer Matrix Radon-Partitionen von Punkten im RaumKomplemente von Schnittmengen eines Pseudohyperebenen-Arrangements

1 2

3

4

5

6

1

2

3

4

5

6

+

+--

1 2

3

456

7 von 13

Kleiner Zusammenhang

Dekomposition (WH & RN 2005): Jedes orientierte Matroid lässt sich zerlegen in direkte Summen und 2-Summen 3-zusammenhängender orientierter Matroide.Beispiel (2-Summe):

Berechnung des Max-Flow auf jeder Komponente

8 von 13

Dekomposition - Beispiel

Löschen der 1-Komponenten (irrelevant für Max-Flow) und Abspalten einzelner 2-KomponentenMax-Flow auf der Klebekante liefert Kapazität für Klebekante in der Hauptkomponente

9 von 13

Max-Flow Min-Cut mal anders

Ein s-t-Fluss ist maximal genau dann wenn es einen s-t-Schnitt mit gleichem Wert gibt.Solch ein Schnitt ist gesättigt bzgl. kEin Rundfluss f ist maximal auf g genau dann, wenn es einen Schnitt gibt mit

Ein Rundfluss f ist maximal auf g genau dann wenn es einen Vektor gibt mit

10 von 13

Verallgemeinertes MFMC

„Wunschsatz“:Sei ein 3-zusammenhängendes Orientiertes Matroid und Dann gilt:

Gilt für reguläre, Rang 3, uniforme und kleine allgemeine orientierte Matroide

11 von 13

*****Oder gemischt:

Struktur des Flussgitters

Alle bisher untersuchten Flussgitter haben folgende Gestalt:

ist regulär (Standard Maxflow-Mincut) ist trivial

12 von 13

Zusammenfassung

Positiv:Maximalen Fluss von vielen OMs berechnenMaxflow-Mincut verallgemeinert

Nicht so positiv:Meistens kein Maximaler Fluss vorhandenStruktur von für allg. OMs noch unbekanntMFMC-Property aus Matroid-Theorie gilt nur für regulären Fall Andere Ansätze wenig viel versprechend (z.B. )

13 von 13

Vielen Dank für die Aufmerksamkeit

Die Wien – Foto von Ottjörg A.C.