6 - Graph Matching 2 Flashcards
What is a network?
A directed graph G=(V, E) such that:
- there are vertices s,t ∈ V such that:
- s has indegree 0 (s is the source)
- t has outdegree 0 (t is the sink)
- each edge (u,v) ∈ E has non-negative capacity c(u, v) ∈ R (the set of real numbers)
- Assume nonexistent edges have capacity 0 and every vertex lies on some path between s and t
What is a flow?
A flow in a graph is a function F : E -> R such that:
- Capacity constraint: for every edge, 0 <= flow <= capacity
- Flow conservation constraint: for every vertex other than s, t, total incoming flow = total outgoing flow
- val(f) of flow is total flow from s, or total flow into t
What is flow capacity constraint?
for every edge 0 <= flow <= capacity
What is flow conservation constraint?
For every vertex other than s and t total incoming flow = total outgoing flow
Example of network with flow
An alternative flow
What is a flow that is saturating?
Flow is saturating if f(s,v) = c(s,v) for all vertices v
What is an augmenting path?
With respect to a flow f, an augmenting path is a path from s to t comprising edges of G but not necessarily directed as in G
What are the conditions for each edge (u,v) in an augmenting path?
Each edge (u,v) in path must satisfy one of two conditions:
- (u,v) ∈ E ( (u,v) is in same direction as in G) and f(u,v) < c(u,v)
- (u,v) is a forward edge
- difference c(u,v) - f(u,v) is the slack of (u,v)
- (v,u) ∈ E ( (u,v) is opposite in drection to an edge in G) and v(v,u) > 0
- (u,v) is a backward edge
Example of augmenting path
Augmenting a flow along an augmenting path
What is the augmenting path theorem?
A flow is maximum if and only if it admits no augmenting path
What is a cut?
A set of edges separating source from sink
What happens if you remove the edges of a cut?
Leaves no path from s t t
