OR 2019 Quiz Teil A Frage 8 wurde editiert (Stand 13.5.2019). 1. Was ist die Anzahl kürzester Wege von s nach t in folgendem Graph? 135$\infty$Es gibt keinen kürzesten Weg 2. Welche der folgenden Vektoren sind Potentiale des gegebenen Graphen? (Mehrere Antworten sind möglich) p = (1,2,3,4,5) p = (1,2,3,3,1) p = (-1,0,1,1,-1) 3. 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) Eine Kante $a$ ist genau dann im Residualgraph, falls der Fluss auf $a$ geringer als die Kapazität ist oder $f(a^{-1})$ positiv ist. Eine Kante $a$ ist genau dann im Residualgraph, falls der Fluss auf $a$ geringer als die Kapazität ist oder die Kapazität der Kante $a^{-1}$ positiv ist. Eine Kante $a$ ist genau dann im Residualgraph, falls der Fluss auf $a$ geringer als die Kapazität ist und $f(a^{-1})$ positiv ist. Eine Kante $a$ ist nicht Teil des Residualgraphen genau dann, falls der Fluss auf $a$ gleich der Kapazität ist und $f(a^{-1})$ nichtpositiv ist. 4. 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) U={s,a,b,c,d} U={b,d} U={s,b} U={s,b,d,t} 5. Gegeben ist der folgende Graph mit angegebener Kapazität $c\in\mathbb{R}^E_{\geq 0}$ und $s$-$t$-Fluss $f\in\mathbb{R}^E_{\geq 0}$ (in Klammern). Welche Kantenfolgen definieren einen $s$-$t$-Weg im Residualgraph $D_f$? (Mehrere Antworten sind hier möglich) (s,a,b,c,t) (s,b,d,t) (s,a,c,b,d,t) (s,b,a,c,d,t) 6. Welche der folgenden Graphen sind bipartit? (Mehrere Antworten sind möglich) (a) (b) (c) Keiner 7. Sei $G=(V,M\cup M')$ ein ungerichteter Graph, dessen Kantenmenge aus der Vereinigung zweier Matchings $M$ und $M'$ besteht. Welche der folgenden Aussagen ist korrekt? (Mehrere Antworten sind hier möglich) Jeder Knoten von $V$ hat mindestens zwei Nachbarn Jede Zusammenhangskomponente, die kein Weg ist, ist ein Kreis. Falls $|M'|>|M|$, existiert eine Zusammenhangskomponente, welche mehr Kanten aus $M'$ als aus $M$ enthält. Alle Kreise in $G$ sind ungerade. Alle Kreise in $G$ sind gerade. 8. Sei $G=(V,E)$ ein ungerichteter Graph, $M\subseteq E$ ein Matching und $P=\{e_1,\ldots , e_m\}$ ein $M$-augmentierender Pfad. Welche der folgenden Aussagen ist korrekt? (Mehrere Antworten sind hier möglich) P ist ungerader Länge $e_1\in M$ oder $e_m\in M$ P ist nicht leer $|P\cap M| \geq 1$ $(M\setminus P) \cup (P\setminus M)$ ist ein Matching 9. 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) {{x,b},{b,y},{y,c}} {{a,x}} {{x,b},{b,z}} {{a,y},{y,b},{b,z}} 10. Welcher der folgenden Sätze gibt korrekt die Aussage des Matchingtheorems von König wieder? (Mehrere Antworten sind möglich) In einem bipartiten Graphen ist die Matchingzahl gleich der Kantenüberdeckungszahl. In einem bipartiten Graphen ist die Größe eines größten Matchings gleich der Größe einer minimalen Kantenüberdeckung. In einem bipartiten Graphen ist die Größe eines größten Matchings gleich der Größe einer minimalen Knotenüberdeckung. In einem bipartiten Graphen ist die Kardinalität eines minimalen Matchings gleich der Kardinalität einer maximalen Knotenüberdeckung. Time is Up!
