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

From VoWi
Jump to navigation Jump to search

Let and be flows on a weighted digraph. Let and be nonnegative reals with + . Show that + is a flow on G.

Hilfreiches[edit | edit source]

Lösungsvorschlag[edit | edit source]

Flowing conditions:
(1) , where is the flow on the edge e, and is the maximum flow of the edge
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