University:
Amherst College
Course:
COSC 311 | Algorithms
Academic year:

2023
Views:

64

Pages:

1
Author:

Brennen Smith

Network Flow The Network Flow Problem Input: • A directed, weighted graph G = (V, E) • For each edge e = (u, v) ∈ E, a positive integer capacity c(e) • A source node s ∈ V , where s has no incoming edges • A target node t ∈ V , where t has no outgoing edges Output: A valid flow f of maximum value (that is, arg maxf {v(f )}). Notation • A flow f is a function that maps each edge e = (u, v) in a graph G = (V, E) to a nonnegative number f (e) = f (u, v) representing the amount of flow sent along that edge. • The value of a flow, denoted v(fP ), is the total amount of flow sent from the source node s to the target node t, where v(f ) = (s,u) f (s, u). • Any valid flow must satisfy the following two conditions: – Capacity condition: For each edge e ∈ E, the amount of flow sent along the edge must be at most the edge’s capacity. That is, 0 ≤ f (e) ≤ c(e) for all edges e, where c(e) is the capacity (weight) of edge e. – Conservation condition: For each node v ∈ V (v 6= s, t), the amount P of flow into the node must be equal to the amount of flow out of the node. That is, u,v f (u, v) = P v,w f (v, w) for all nodes v.

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock