Modell Teil 3

Startknoten (meist mit unendlichem Excess)

Zielknoten (Height = 0)

• Für jede Kante E gilt: 0≥ f€ ≤ we

• Für jeden Knoten v, v≠s, v≠t, gilt:∑ f(u,v) = ∑ f(v,u)

F(f) ≔ ∑ f(s, v) − ∑ f(v, s)

C(f) = ∑ c(u, v) ∗ f(u, v)

∑ f(u, v) ≥ ∑ f(v, u)

• Netzwerk (G, (w,c), s, t) mit Fluss f

• Def. Gewichteter Graph G‘ (V,E‘, (w‘,c‘)) mit (u,v) € E‘, wenn (u,v) € E & f(u,v) < w(u,v) mit w‘(u,v):=w(u,v)-f(u,v) & c‘(u,v)=c(u,v) oder (v,u)€E & f(v,u)>0 mit w‘(u,v):=f(v,u) & c‘(u,v)=-c(u,v)

Maximale Kantenbewertung je Kante

• Eingabeparameter: Netzwerk (G,w,s,t) mit G(V,E)

• Eintscheidungsoptionen: Kantenbewertung f (Fluss)

• Restriktionen: Flussbedingung->Kantenbewertung f muss ein Fluss im NW sein

• Zielfunktion: Flussstärke F(f) soll maximiert werden

Übermaß = Eingehende Kantenbewertungen – Ausgehende Kantenbewertungen

minimaler Wert, der zuschneidenden Kanten zur Flussunterbrechung (entspricht Maximalfluss)

• Gesättigt: Es kann keine weitere Matchingkante hinzugefügt werden, ohne das Matching M zu verändern

• Maximal: Die maximal mögliche Anzahl an Matchingkanten

• Perfekt: Alle Knoten sind durch eine Matchingkante verbunden

• Zuordnung: Ein perfektes Matching in einem bipartiten Graphen

• Vergrößernder Weg: Weg W = (s,…,t) (Wenn M=0, ist jedes neue Knotenpaar mit Kantenverbindung ein Vergr. Weg)

• Bedingung:

1. s und t sind keine Endpunkte von Kanten des Matchings M

2. W durchläuft abwechselnd eine Nicht-Matchingkante und eine Matchingkante

3. W ist kreisfrei (jeder Knoten kommt nur einmal vor)

Ordnet jedem Knoten eine reelle Zahl zu (für jede Kante (u, v) ∈ E die Gleichung: l(u) + l(v) ≤ w(u,v))

Für jede Matchingkante gilt die Gleichung: l(u) + l(v) = w(u,v))

• Gerichtet: Für jeden Knoten gilt: Eingehende Kanten = Ausgehende Kanten

• Ungerichtet: Für jeden Knoten gilt: Die Kantenanzahl ist gerade (mod 2=0)

Ein geschlossener Kantenzug, der jede Kante einmal enthält