TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 25

Let $\phi _{1}$ and $\phi _{2}$ be flows on a weighted digraph. Let $\gamma _{1}$ and $\gamma _{2}$ be nonnegative reals with $\gamma _{1}$ + $\gamma _{2}\leq 1$. Show that $\gamma _{1}$ $\phi _{2}$ + $\gamma _{2}$ $\phi _{2}$ is a flow on G.

Lösungsvorschlag

Flowing conditions:
(1) $\forall e\in E:$ $0\leq \phi (e)\leq w(e)$, where $\phi (e)$ is the flow on the edge e, and $w(e)$ is the maximum flow of the edge
(2) $\forall v\in V\setminus \{s,t\}:\sum _{(v,y)\in E}\phi (v,y)=\sum _{(x,v)\in E}\phi (x,v)$
ad (1): $\gamma _{1},\gamma _{2}\leq 1$ -->
$\gamma _{1}\phi _{1}\leq \phi _{1}\leq w(e)$ $\forall e\in E,\gamma _{1}\leq 1$
$\gamma _{2}\phi _{2}\leq \phi _{2}\leq w(e)$ $\forall e\in E,\gamma _{2}\leq 1$
Since we have the condition $\gamma _{1}$ + $\gamma _{2}\leq 1$, we can say that $\gamma _{1}\phi _{1}+\gamma _{2}\phi _{2}\leq max(\phi _{1},\phi _{2})$
$\phi _{1},\phi _{2}\leq w(e)$ --> $\gamma _{1}\phi _{1}+\gamma _{2}\phi _{2}\leq w(e)$
ad (2): There are three cases
I: Vertex $v\in V$ is part of no flow OK
II: Vertex $v\in V$ is part of one flow
flow is equally reduced on incoming and outgoing
$\forall v\in V\setminus \{s,t\}:\sum _{(v,y)\in E}\gamma _{1}\phi _{1}(v,y)=\sum _{(x,v)\in E}\gamma _{1}\phi _{1}(x,v)$
III: Vertex $v\in V$ is part of both flows
$\sum _{(v,y)\in E}\gamma _{1}\phi _{1}(v,y)+\sum _{(v,y)\in E}\gamma _{2}\phi _{2}(v,y)=\sum _{(x,v)\in E}\gamma _{1}\phi _{1}(x,v)+\sum _{(x,v)\in E}\gamma _{2}\phi _{2}(x,v)$