\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

TODO: put stuff on Hall's theorem and bipartite matchings into the HTML files. Make a separate file. Include stuff like that doubly-stochastic matrices are convex combinations of permutation matrices.
Für die folgenden Programmieraufgaben können Sie meinen Code FlowNetwork.java) verwenden und modifizieren. Unter Anderen erhält der Code eine Funktion flowNetwork.edmondsKarp():
  • Nach vollendetem Aufruf enthält jede Edge e in der lokalen Variable e.flow den Wert des gefundenen Maxflows \(f\).
  • Der Rückgabewert ist ein Vector<Boolean> der Länge n, der für jeden Knoten \(v\) (indiziert von 0 bis n-1) anzeigt, ob es im Residualnetzwerk \(G_f\) einen Pfad von \(s\) nach \(v\) gibt und codiert somit einen Minimum Cut.

Bipartite Matchings

Lesen Sie bitte meine Folien zum Maximum-Matching-Problem, solange ich die nicht in dieser Seite selbst integriert habe. Für die folgenden Programmieraufgaben verwenden wir das folgende Datenformat für bipartite Graphen: 
l r m l = Anzahl Knoten links, r = Anzahl Knoten rechts, m = Anzahl Kanten                    
name_0 name_1 ... name_{n-1} Namen der Knoten; jeder ein String ohne Whitespace                    
u1 v1
u2 v2 
... 
u_m v_m Die Kanten; zwei Knotennamen pro Zeile, insgesamt m Zeilen für die Kanten. Der 
    Knoten u_m ist in der linken Menge, der Knoten v_m in der rechten Menge.
Dieser bipartite Graph:
hätte also die Codierung 
5 5 12
a b c d e u v w x y 
a v 
a w 
b u 
b x 
c v 
c w 
c x 
d u 
d y 
e w 
e x 
e y
Übungsaufgabe Schreiben Sie ein Programm, dass einen bipartiten Graphen in diesem Format einliest (adaptieren Sie dafür den Code in der Klasse FlowNetwork.java). Ausgabe Ihres Codes soll eine Liste von Kanten sein, nämlich jene in einem Maximum Matching.
Übungsaufgabe Schreiben Sie einen Algorithmus (Code oder Papier), der die Knotenmenge \(X \subseteq L\) findet, die \( |X| - |\Gamma(X)|\) maximiert.

Baseball-Eliminierung

Bis ich es ins Vorlesungsskript integriert habe, schauen Sie sich bitte direkt meine Folien zur Baseball-Eliminierung an. Um auf dem Rechner zu behandeln, müssen wir auch hier ein Input-Format festlegen. Nehmen Sie als Beispiel diese Tabelle:
Wir codieren diese Probleminstanz als Text wie folgt: 
4 5 
Atlanta Philadelphia New_York Montreal
Atlanta 83 
Philadelphia 80
New York 78
Montreal 77
Atlanta Philadelphia 1 
Atlanta New_York 6 
Atlanta Montreal 1 
Philadelphia Atlanta 1 
Philadelphia Montreal 2
Also
  • In Zeile 1 die Anzahl n von Teams und Anzahl m von "Team-Paaren"
  • In Zeile 2 die Namen der n Teams. Sie dürfen davon ausgehen, dass der Name keinen Whitespace enthält, also New_York statt New York.
  • Zeile 3 bis n+2: für jedes Team die Anzahl der bereits erworbenen Punkte (Siege in einem Match).
  • die restlichen m Zeilen: pro Zeile die Namen zweier Teams und die Anzahl an Matches, die sie noch zu spielen haben.
Fehlt ein Teampaar ist den letzten m Zeilen, wie zum Beispiel oben New York - Philadelphia, so bedeutet dies, dass diese keine weiteren Spiele gegeneinander spielen werden.
Übungsaufgabe Schreiben Sie ein Programm für Baseball-Eliminierung. Das Input-Format ist wie eben beschrieben. Output-Format soll sein: n Zeilen, jede Zeile im Format Philadelpha cannot finish in first place oder New_York can still finish in first place.

Hier sind zwei Beispiel-Inputdateien: baseball-4-teams und baseball-5-teams.