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

Aus VoWi
Zur Navigation springen Zur Suche springen

Let and be flows on a weighted digraph. Let and be nonnegative reals with + . Show that + 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
}}


Hilfreiches[Bearbeiten | Quelltext bearbeiten]

Lösungsvorschlag[Bearbeiten | Quelltext bearbeiten]

Flowing conditions:
(1) , where is the flow on the edge e, and is the maximum flow of the edge
(2)
ad (1): -->


Since we have the condition + , we can say that
-->
ad (2): There are three cases
I: Vertex is part of no flow OK
II: Vertex is part of one flow
flow is equally reduced on incoming and outgoing

III: Vertex is part of both flows