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

Let ${\varphi }_1$ and ${\varphi }_2$ be flows on a weighted digraph. Let ${\gamma }_1$ and ${\gamma }_2$ be nonnegative reals with ${\gamma }_1$ + ${\gamma }_2\le 1$. Show that ${\gamma }_1$ ${\varphi }_2$ + ${\gamma }_2$ ${\varphi }_2$ is a flow on G.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag

Flowing conditions:
(1) $\mathrm{\forall }e\in E:$ $0\le \varphi (e)\le w(e)$, where $\varphi (e)$ is the flow on the edge e, and $w(e)$ is the maximum flow of the edge
(2) $\mathrm{\forall }v\in V\setminus \{s,t\}:\sum _{(v,y)\in E}\varphi (v,y)=\sum _{(x,v)\in E}\varphi (x,v)$
ad (1): ${\gamma }_1,{\gamma }_2\le 1$ -->
${\gamma }_1{\varphi }_1\le {\varphi }_1\le w(e)$ $\mathrm{\forall }e\in E,{\gamma }_1\le 1$
${\gamma }_2{\varphi }_2\le {\varphi }_2\le w(e)$ $\mathrm{\forall }e\in E,{\gamma }_2\le 1$
Since we have the condition ${\gamma }_1$ + ${\gamma }_2\le 1$, we can say that ${\gamma }_1{\varphi }_1+{\gamma }_2{\varphi }_2\le max({\varphi }_1,{\varphi }_2)$
${\varphi }_1,{\varphi }_2\le w(e)$ --> ${\gamma }_1{\varphi }_1+{\gamma }_2{\varphi }_2\le 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
$\mathrm{\forall }v\in V\setminus \{s,t\}:\sum _{(v,y)\in E}{\gamma }_1{\varphi }_1(v,y)=\sum _{(x,v)\in E}{\gamma }_1{\varphi }_1(x,v)$
III: Vertex $v\in V$ is part of both flows
$\sum _{(v,y)\in E}{\gamma }_1{\varphi }_1(v,y)+\sum _{(v,y)\in E}{\gamma }_2{\varphi }_2(v,y)=\sum _{(x,v)\in E}{\gamma }_1{\varphi }_1(x,v)+\sum _{(x,v)\in E}{\gamma }_2{\varphi }_2(x,v)$