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

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

## Lösungsvorschlag

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