# 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