Operations Research – Quiz

1. Welche der folgenden Aussagen definiert einen Baum? (Mehrere Antworten sind hier möglich)
2. Sei $G=(V,E)$ ein zusammenhängender Graph, $l\in\mathbb{R}^{E}$ eine Kantenlängenfunktion. Welcher der folgenden Algorithmen berechnet einen minimalen Spannbaum $H=(V,T)$? (Mehrere Antworten sind möglich)

a) Setze $T=\{e_0\}$ für beliebiges $e_0\in E$
$\quad$ While $H=(V,T)$ kein Baum:
$\quad$ $\quad$ Wähle $e\in E\setminus T$ mit minimalem $l$ sodass $H=(V,T\cup\{e\})$ ein Wald ist
$\quad$ $\quad$ $T=T\cup\{e\}$

b) Setze $T=\emptyset$.
$\quad$ While $H=(V,T)$ ein Wald:
$\quad$ $\quad$ Wähle $e\in E\setminus T$ mit minimalem $l$ sodass $H=(V,T\cup\{e\})$ ein Wald ist
$\quad$ $\quad$ $T=T\cup\{e\}$

c) Setze $T=\emptyset$
$\quad$ While $H=(V,T)$ kein Baum:
$\quad$ $\quad$ Wähle $e\in E\setminus T$ mit minimalem $l$ sodass $H=(V,T\cup\{e\})$ ein Wald ist
$\quad$ $\quad$ $T=T\cup\{e\}$

d) Setze $T=E$
$\quad$ While $T \neq \emptyset$:
$\quad$ $\quad$ Wähle $e\in E\setminus T$ mit minimalem $l$ sodass $H=(V,T\cup\{e\})$ ein Wald ist
$\quad$ $\quad$ $T=T\setminus\{e\}$
3. Was ist die Anzahl der Spannbäume in diesem Graph?

4. Was ist die Anzahl kürzester Wege von s nach t in folgendem Graph?

Wege
5. Welche der folgenden Vektoren sind Potentiale des gegebenen Graphen?
(Mehrere Antworten sind möglich)

Potentiale
6. Welche der folgenden Graphen sind bipartit? (Mehrere Antworten sind möglich)

bipartit
7. Welcher der folgenden Sätze gibt korrekt die Aussage des Matchingtheorems von König wieder? (Mehrere Antworten sind möglich)
8. Welcher $M$-augmentierende Weg wird in der ungarischen Methode zur Berechnung eines Matchings mit maximalem Gewicht im folgenden Graphen mit gegebenem Matching (fett gedruckte Kante) gewählt? (Mehrere Auswahlen sind möglich)
ungarische Methode
9. Seien $D=(V,A)$, $s, t \in V$ und $f$ ein $s$-$t$-Fluss. Wie sind die Kanten des Residualgraphs $D_f$ definiert? (Mehrere Auswahlen sind möglich)
10. Gegeben ist der folgende Graph mit angegebener Kapazität und maximalem s-t-Fluss (in Klammern). Für welche Mengen $U \subseteq V$ ist $\delta^{out}(U)$ ein minimaler s-t-Schnitt? (Mehrere Antworten sind möglich)

Fluss