# 6 - Graph Matching 2 Flashcards

1
Q

What is a network?

A

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
2
Q

What is a flow?

A

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
3
Q

What is flow capacity constraint?

A

for every edge 0 <= flow <= capacity

4
Q

What is flow conservation constraint?

A

For every vertex other than s and t total incoming flow = total outgoing flow

5
Q

Example of network with flow

A
6
Q

An alternative flow

A
7
Q

What is a flow that is saturating?

A

Flow is saturating if f(s,v) = c(s,v) for all vertices v

8
Q

What is an augmenting path?

A

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

9
Q

What are the conditions for each edge (u,v) in an augmenting path?

A

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
10
Q

Example of augmenting path

A
11
Q

Augmenting a flow along an augmenting path

A
12
Q

What is the augmenting path theorem?

A

A flow is maximum if and only if it admits no augmenting path

13
Q

What is a cut?

A

A set of edges separating source from sink

14
Q

What happens if you remove the edges of a cut?

A

Leaves no path from s t t