Upload
christin-faerber
View
215
Download
0
Embed Size (px)
Citation preview
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.