Hallo beim tollen Diskrete Quatsch!

Praxisanwendungen

Hotelbelegung
Ein Hotel hat durch einen Softwarefehler zu viele Buchungen angenommen, nun müssen Buchungen storniert werden. Aber welche?
Skifahren
Im Skigebiet möchte man alle Skipisten einmal gefahren sein. Gleichzeitig will man aber möglichst wenig Zeit benötigen (je schneller man ist umso mehr kann man fahren!) und am Ende bitte auch wieder am Hotel ankommen. Wie findet man eine optimale Route?
Bergbau
Auch bekannt als "Open Pit Mining Problem"
Ein Bergbauunternehmen möchte im Tagebau Rohstoffe abbauen. Zwischen den wertvollen Rohstoffen befindet sich aber auch Dreck für dessen Entsorgung es bezahlen muss. Was sollte das Unternehmen abbauen wenn es seinen Profit maximieren will?

Fibonacci-Heap
Kurzbeschreibung Fibonacci-Heap
Schlange
Queue
Bei einer Schlange werden, wie z.B. bei einer Warteschlagne, Elemente nur an das Ende einer Liste angehangen und nur Elemente am Anfang der Liste entfernt. Dadurch wird ein Element welches früher der Schlange hinzugefügt wurde auch früher wieder ausgegeben, das First-In-First-Out Prinzip (FIFO).
Stack
Bei einem Stack werden Elemente "oben" auf den Stack gelegt und von dort auch wieder entfernt. Dadurch wird ein Element welches später auf den Stack gelegt wurde auch früher wieder vom Stack entfernt, das Last-In-First-Out Prinzip (LIFO).

Algorithmus von Prim
Der Algortihtmus von Prim unterteilt den Graphen in bereits hinzugefügte Knoten U und noch nicht hinzugefügte Knoten V und betrachtet nur die von U nach V ausgehenden Knoten.

Algorithmus von Dijkstra
Der Algorithmus von Dijkstra findet die kürzesten Wege von einem Knoten zu allen andenren Knoten innerhalb eines Graphens (wenn sie erreichbar sind). Dafür legt der Algorithmus eine Liste an und untersucht immer den den Gewichten nach nächsten noch nicht bearbeiteten Knoten.
Alle Kantengewichte müssen positiv sein.
Variante 1:
Speichert die zu untersuchenden Knoten in einer Liste und sortiert diese bei jeder Iteration nach ihrer Entfernung.

Variante 2:
Speichert die zu untersuchenden Knoten in einem Fibonacci-Heap, dadurch wird eine bessere Laufzeit erreicht.
Benötigt: Fibonacci-Heap
Algorithmus von Moore-Bellman-Ford
Der Algorithmus von Moore-Bellman-Ford findet die kürzesten Wege von einem Knoten zu allen anderen Knoten innerhalb eines Graphens (wenn sie erreichbar sind) oder gibt aus, dass es einen Kreis mit negativem Gesamtgewicht gibt.
Zulässiges Potenzial
Findet ein zulässiges Potenzial wenn der Graph keine Kreise mit negativem Gesamtgewicht enthält.
Benötigt: Algorithmus von Moore-Bellman-Ford

Algorithmus von Edmonds-Karp
Algorithmus von Ford-Fulkerson
Der Algorithmus von Edmonds-Karp findet in einem Netzwerk einen maximalen Fluss von s nach t. Der Algorithmus an sich wurde bereits vorher von Ford-Fulkerson beschrieben und durch Edmonds-Karp dahingehend verbessert, dass zum finden eines s-t-Weges nicht irgendein Algortihmus, sondern die Breitensuche verwendet wird.
Gerichtete kantendisjungte Wege Problem
Das gerichtete kantendisjungte Wege Problem beschreibt ein Problem, nach dem sich jeder s-t-Fluss in eine Familie C von Kreisen und eine Familie P von Wegen zerlegen lässt. Der Algorithmus arbeitet auf einem Netzwerkfluss und findet in diesem die s-t-Wege.
Push Relabel Algorithmus
Ein Algorithmus zum Finden eines maximalen s-t-Flusses mithilfe von s-t-Preflüssen.

Sukzessive kürzeste Wege Algorithmus
Findet einen minimalen b-Fluss in einem gegebenen Graph.

Variante 1:
Nutzt den Moore-Bellman-Ford Algorithmus zum finden kürzester Wege zwischen s und t.
Benötigt: Algorithmus von Moore-Bellman-Ford

Variante 2:
Berechnet erst für alle Knoten ein zulässiges Potenzial, mit den dadurch angepassten Kosten für Kanten (welche alle positiv sind) können wir die kürzesten Wege dann mit Dijkstra berechnen.
Benötigt: Zulässiges Potenzial, Algorithmus von Dijkstra

Minimum Weight Perfect Matching
Zuordnungsproblem
Findet für einen Bipartiten Graphen ein perfektes Matching, oder stellt fest dass es keins gibt.
Benötigt: Sukzessive kürzeste Wege Algorithmus, Algorithmus von Moore-Bellman-Ford