1. MaxFlow mit augmentierenden Wegen berechnen (war relativ aufwändig mit 3 Augmentierungen und hat viel Zeit gekostet. Hier sollte man auf jeden Fall nicht mehr denken müssen, um Zeit zu sparen.)
2. MinCostFlow-Problem mit schon gegebenem zulässigen Fluss und einer durchzuführenden Kreislöschung + Angabe Gesamtkosten

Beide Graphen hatten Umfang ~6 Knoten

1. Maximierungsproblem, das mit 6 Variablen zu modellieren war (Vorgabe!), wobei eine Kostenmatrix mit 9 Einträgen gegeben war und 9 Variablen naheliegender wären. Der Trick: Man musste erkennen, dass eine Spalte der Kostenmatrix nicht direkt relevant für das Optimierungsproblem war, weil es keine Ressourcen verbraucht hat. Die nicht verbrauchten Ressourcen werden „automatisch“ durch den Schlupf abgedeckt.
2. Für das oben modellierten Problem sollte geprüft werden, ob ein gegebenes Szenario (es wurde eine zulässige Lösung beschrieben) optimal ist. Hier musste man mit komplementären Schlupf und dualem Problem beweisen, ob die Lösung optimal ist.

1. Es war ein Maximierungsproblem gegeben, das graphisch zu lösen war und ein algebraischer Beweis für die Optimalität anzugeben (mit Dualproblem, analog zu Übungsaufgaben)
2. Eine Iteration vom Simplex mit gegebenem Startpunkt sollte durchgeführt werden
3. Angabe der nächsten erreichten Basislösung und eine Angabe, wie viele Iterationen noch nötig sind

Es war die Äquivalenz folgender Aussagen zu beweisen:

• Anzahl der Zusammenhangskomponenten k = |V| - |E|
• der Graph ist ein Wald

1. Angabe ob Laufzeiten (z.B. O(c log n)) polynomiell sind oder nicht (ohne Begründung)
2. Wahr/Falsch-Aussagen (ohne Begründung) zu Graphen-Problemen (kürzeste Teilwege, …)
3. Optimalitätskriterium für kürzeste Wege angeben
4. 1x beweisen und 1x widerlegen, dass gegebene Mengen Matroide sind