OR

Kobination aus Eingabeparametern, Entscheidungsoptionen, Restriktionen und Zielfunktionen

• Eine Lösung ist eine Entscheidungsoption

• Zulässige Lösung Erfüllt die Restriktionen

Belegung aller Eingabeparameter mit Werten

ist eine präzise & eindeutige Darstellung von Verfahrensschnitt für ein Optimierungsproblem, die jeder Problemdistanz des Problems eine Handlungsoption zuordnet

• bipartit

• ungerichtet

• ungewichtet

• zusammenhängend

• schlicht

• Ein graph G isz ein Paar G=(V,E) bestehend aus einer nicht leeren Knotenmenge V und einer Kantenmenge E

• Für eine Kante e heißen u&v Endpunkte von e=(u,v)

• 2 durch eine Kante verbundene Knoten heißen Nachbarn

• alle Knoten in einem Kantenzug sind verschieden

• Kantenzug: eine endliche Folge von Knoten, bei der jeweils 2 aufeinanderfolgende Knoten Nachbarn sind oder Vorgänger/Nachfolger

Vollständiger Graph

Ein vollständig bipartiter Graph

EIn stark zusammenhängender Graph

eine endliche Folge von Knoten, bei der jeweils 2 aufeinanderfolgende Knoten Nachbarn sind oder Vorgänger/Nachfolger

Startknoten=Endknoten

Wie viele Knoten enden in einem Punkt

Ein Wert, der von der Funktion nicht unterschritten wird

Triple kann auch mit negativen Kantengewichten umgehen

• Färbungsalgorithmus

• Dijkstraalgorithmus

• A* Algorithmus

• Floyd-Warshall-Algorithmus (Tripel Alg)

• Ford und Fulkerson

• Preflow-Push-Verfahren

• Kürzeste Wege Problem

• Algorithmus von Klein

• Hopcroft & Karp

• Ungarische Methode

• Eulersche Tour

• Briefträgerproblem

• Exaktes Verfahren

• Aufteilung der Knoten in zwei mengen, sodass keine Kante die Endpunkte in der gleichen Menge hat oder der Hinweis, dass der Grpah bipartit ist

• Gibt es zwischen jedem Knotenpaar eines ungerichteten Graphen einen Weg, so ist dieser Graph zusammenhängend

• Ein gerichteter Graph ist schwach zusammenhängend, wenn sein ungerichteter Pendant zusammenhängend ist, d.h wenn der ungerichtete Graph zusammenhängend ist, der entsteht, wenn alle gerichtette Kanten als ungerichtet aufgefasst werden.

• Gibt es zwischen jedem Knotenpaar eines gerichteten Graphen einen Weg, so ist diese Graph stark zusammenhängend

Die Funktion, die dem Weg seine Länge zuordnet, soll minimiert werden

• Exaktes Verfahren

• Bestimmt kürzeste Wege zwischen einem Knoten und allen anderen Knoten eines Graphen

• Exaktes Verfahren

• Berechntet den kürzesten Weg zwischen zwei Knoten

• dem Dijkstra-Algorithmus sehr ähnlich, verbessert diesen sogar für den Fall, dass Zusatzinformationen über den Grpahen vorliegen

• Exkates Verfahren

• Bestimmt kürzeste Wege zwischen allen Knotenpaaren eines Grpahen

• Alle Tripel von Knoten betrachten (Transitionen, Startknoten, Zielknoten)

• geht auch mit negativen Kantengewichten

• Exaktes Verfahren

• Gehört zu Maximalflussproblem

• Ausgabe: Fluss f mit maximaler Stärke

• Der Fluss f hat genau dann die maximale Stärke, wenn es im zugehörigen Residualgraphen keinen Weg von s nach t gibt (Beweis:Umkehrschluss)

• Resiudalgraph: ist ein gewichteter (Multi-) Graph mit identischer Knotenmenge V und der folgenden Kantenmenge E’ mit zugehörigen Gewichten

  Entspricht beim Nullfluss dem Originalgraphen

• Gesucht ist ein maximaler Fluss, also eine Kantenbewertung die

  1. Kapazitätsbedingung einhält

  2. Flusserhaltung einhält

  3. maximale Flussstärke hat

• exaktes Verfahren

• Fluss:

  • geht soviel rein wie raus?

  • Keine negativen Werte

  • Kapazitäten einhalten

• Präfluss

  • Kapazitäten einhalten, wenn ja wahrscheinlich ein Präfluss

  • Zuviel rein wie raus? - Verlust ist okay

• Exaktes Verfahren

• Im Fall irrationaler Eingabeparameter sogar endlos laufen

• Exaktes Verfahren

• Maximal Matching

• Kantengewicht egal

• ungerichtete, bipartite Graphen

  
  

• Exaktes Verfahren

• Minimal gewichtetes, perfektes Matching

• Gleichheitsmatching: Wenn die Summe von V1 und V2 kleiner, gleich das Gewicht der Kante ist

• ein geschlossener Kantenzug, der jede Kante genau einmal beinhaltet

• für gerichtete Graphen

• ein gerichteter, nicht negativ gewichtetter, stark zusammenhängender Graph