Satz Flusswert bei Quelle und Senke gleich
Einfache Sprache
Bezüglich des Flusswert ist berechnung über die Quelle oder die Senke gleichermaßen möglich
Satz Flusswert bei Quelle und Senke gleich
$$\sum_{e\in\delta_{out}(s)}f(e)-\sum_{e\in\delta_{in}(s)}f(e) = \sum_{e\in\delta_{in}(t)}f(e)-\sum_{e\in\delta_{out}(t)}f(e) $$
Beweis:
$$\begin{align}&\sum_{e\in\delta_{out}(s)}f(e)-\sum_{e\in\delta_{in}(s)}f(e)&\\ =& \sum_{e\in\delta_{out}(s)}f(e)-\sum_{e\in\delta_{in}(s)}f(e)+\sum_{v\in V\setminus\{s,t\}}\left(\sum_{e\in\delta_{out}(v)}f(e)- \sum_{e\in\delta_{in}(v)}f(e)\right)&\Huge|\normalsize\text{Erweitern}\\ =& \sum_{v\in V\setminus\{t\}}\left(\sum_{e\in\delta_{out}(v)}f(e)- \sum_{e\in\delta_{in}(v)}f(e)\right)&\Huge|\normalsize\text{$s$ in zweite Summe ziehen}\\ =& \sum_{v\in V}\left(\sum_{e\in\delta_{out}(v)}f(e)- \sum_{e\in\delta_{in}(v)}f(e)\right)-\left(\sum_{e\in\delta_{out}(t)}f(e)-\sum_{e\in\delta_{in}(t)}f(e)\right)&\Huge|\normalsize\text{$t$ aus der Summe ziehen}\\ =& \sum_{v\in V}\sum_{e\in\delta_{out}(v)}f(e)- \sum_{v\in V}\sum_{e\in\delta_{in}(v)}f(e) -\left(\sum_{e\in\delta_{out}(t)}f(e)-\sum_{e\in\delta_{in}(t)}f(e)\right)&\Huge|\normalsize\text{Ausmultiplizieren}\\ =& \sum_{e\in E}f(e)- \sum_{e\in E}f(e) -\left(\sum_{e\in\delta_{out}(t)}f(e)-\sum_{e\in\delta_{in}(t)}f(e)\right)&\Huge|\normalsize\text{siehe Unten}\\ =& -\left(\sum_{e\in\delta_{out}(t)}f(e)-\sum_{e\in\delta_{in}(t)}f(e)\right)&\Huge|\normalsize\text{Vereinfachen}\\ =& \sum_{e\in\delta_{in}(t)}f(e)-\sum_{e\in\delta_{out}(t)}f(e)&\Huge|\normalsize\text{Ausmultiplizieren}\\\end{align}$$Da jede Kante genau einmal in der Ausgangskanten-Menge ist und genau einmal in der Eingangskanten-Menge ist, ist es gleich wir die summe über den Eingangsflow über alle