OR 2019 Quiz Teil C Frage 5 wurde editiert! 1. Welche der folgenden Aussagen sind wahr? Die Inzidenzmatrix eines ungerichteten Graphen ist vollständig unimodular. Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist vollständig unimodular. Die Inzidenzmatrix eines gerichteten bipartiten Graphen ist vollständig unimodular. Wenn die Inzidenzmatrix eines ungerichteten Graphen vollständig unimodular ist, dann ist der Graph bipartit. 2. Sei $G$ ein ungerichteter bipartiter Graph und $A$ seine Inzidenzmatrix. Welche der folgenden Programme berechnen die Matchingzahl von $G$?(a) $\max\{1^Tx : x\in\mathbb{R}^E_{\geq 0}, Ax\leq 1\}$.(b) $\min\{1^Ty : y\in\mathbb{Z}^V_{\geq 0}, A^Ty\geq 1\}$.(c) $\max\{1^Tx : x\in\mathbb{Z}^E_{\geq 0}, Ax\geq 1\}$.(d) $\min\{1^Ty : y\in\mathbb{R}^V_{\geq 0}, A^Ty\leq 1\}$. (a) (b) (c) (d) 3. Welche der folgenden Matrizen sind vollständig unimodular?(a) $\begin{pmatrix}1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\end{pmatrix}$(b) $\begin{pmatrix}1 & 1 & 0 & 0 & -1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & -1\end{pmatrix}$(c) $\begin{pmatrix}0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ 0 & 0 & 1\end{pmatrix}$(d) $\begin{pmatrix}-1 & -1 & 0 & 0 & 0\\ 1 & 0 & 1 & -1 & 0\\ 0 & 1 & -1 & 0 & -1\\ 0 & 0 & 0 & 1 & 1\end{pmatrix}$ (a) (b) (c) (d) 4. Sei $c\in \mathbb{R}^n$ und $P\subseteq \mathbb{R}^n$ ein rationales Polyeder für das gilt:$$\text{max}\{c^Tx:\ x\in P\}<\infty.$$Welche der folgenden Aussagen sind korrekt?(a) $\text{max}\{c^Tx:\ x\in P\}=\text{max}\{c^Tx:\ x\in P_I\}$(b) $\text{max}\{c^Tx:\ x\in P_I\}=\text{max}\{c^Tx:\ x\in P, x\in \mathbb{Z}^n\}$(c) $\text{max}\{c^Tx:\ x\in P, x\in \mathbb{Z}^n\}=\text{max}\{c^Tx:\ x\in P\}$(d) $\text{conv}(P_I)=\text{conv}(P\cap\mathbb{Z}^n)$(e) $P_I$ ist ein Polytop (a) (b) (c) (d) (e) 5. Gegeben sei das folgende Polyeder:$$P=\left\{ x\in \mathbb{R}^2:\ \begin{pmatrix}0 & -1\\ -2 & 1\\ 2 & 1\end{pmatrix}x \leq \begin{pmatrix}0\\-1\\5\end{pmatrix} \right\}.$$Welche der folgenden Ungleichungen beschreiben Chvatal-Gomory cuts von $P$?(a) $x_2\leq 1$(b) $ x_1\leq 2$(c) $x_1+x_2\leq 3$(d) $4x_1+x_2\leq 10$(e) $\frac{1}{3}x_1 + x_2 \leq 2$ (a) (b) (c) (d) (e) 6. Sei $P$ ein rationales Polyeder, $P^{(0)} = P$ und $P^{(i+1)}= (P^{(i)})'$ der Chvatal-Gomory Abschluss von $P^{(i)}$.Welche der folgenden Aussagen sind korrekt?(a) $P^{(i)}\subset P^{(i+1)}$(b) $P_I\subseteq P^{(i)}$(c) $P\subseteq P_I$(d) $P^{(i)}\subseteq P$ (a) (b) (c) (d) Time is Up!
