FS20

1.

b)

Sei $G=(A\uplus B,E)$ bipartit mit $E\ne \varnothing$, dann ist $|A|=|B|$.

True:

• Wir zählen die Kanten zwischen A und B (da G bipartit ist, sind das alle).
• von A gehen $k|A|$ aus, sind also $k|A|$ Kanten. Genauso gilt dies mit $k|B|$ Kanten für die eingehenden Kanten in $B$.
• Wir haben beide Male die Kanten gezählt, es gilt also:
• ${\sum }_{a\in A}\mathrm{deg}(a)={\sum }_{b\in B}\mathrm{deg}(b)$
• $k|A|=k|B|$
• $⟹|A|=|B|$.

c)

Brücke ⇒ v ist artikulationsknoten oder hat deg = 1.

Proof: It’s True. Assume $e$ is a bridge.

• by assumption $G-e$ is disconnected, so $G-e$ has two non-empty, disjunct connected components $A$ and $B$, $u\in A,v\in B$.
  • note $e$ is the only edge connecting $A,B$.
• If $|B|>1$, $v$ has neighbours in $B$.
  • As removing $v$ removes $e$, $G-v$ must also be disconnected, with at least one other non-empty connected component (from $v$‘s neighbours)
• else, $|B|=1$ and thus $v$ has $\mathrm{deg}(v)=1$.

f)

Network with even edges only has at least one even-edged maxflow.

We divide all $c(e)$ by 2, giving $c^{\prime }(e)$ to form a new Network $N^{\prime }$ with integral capacities. Let $f^{\prime }$ be a maxflow.
Then we set $f=2f^{\prime }$ in $N$. This must also be a maxflow, and it has all even edges.

• $2f^{\prime }(e)\le 2c^{\prime }(e)=c(e)$ so it’s a valid flow
• If it wasn’t maximal, i.e. there’s a larger flow in $N$, we could also divide it’s $f(e)$ by $2$ and get a valid flow in $N^{\prime }$, which would be larger than our maxflow $f^{\prime }$, contradiction.

2

a)

State everything clearly and use the sum notation to make it very nice and legible.

b)

Do not draw in the edges which have 0 capacity in the residual network.

5

Be careful to note that we do not “run the procedure again”, instead we extend the colouring by continuing, now with the greedy in the second phase, on the elements in $V\setminus K$.

6

a)

Wir können mit dem Union Bound hier schön verwenden, da die Events nicht independent sind! → Worth memorising