Week 8

Question 1

What is a network flow?

Answer 1

• A flow network G = (V,E) is a weighted graph with vertices V and a set of directed edges E in which each edge has a flow value and a non negative integer capacity c(u, v)
• the flow value: 0 <= f(u,v) <= c(u,v)
• the graph has a source s node and a sink t node
• we assume that s has no in-coming edges and t has no out-going edges

Question 2

What is the flow conservation constraint?

Answer 2

• for every vertex other than s and t, the amount of flow into the vertex must be equal to the amount of flow out of the vertex

Question 3

What is the maximum flow problem?

Answer 3

• given a flow network G, with source s and sink t, find the maximum flow value from s to t

Question 4

How do you calculate the value of the flow? (maximum flow)

Answer 4

By adding all of the flows (NOT THE CAPACITIES) that are outcoming from the source

Question 5

What is a popular algorithm for find the maximum flow in a flow network?

Answer 5

• the Ford-Fulkerson algorithm
• It searches for a flow augmenting path from the source vertex S to the sink t
• We then send as much flow along it as possible, whilst obeying the capacity constraints
• maximum flow we can send along the augmenting path = minimum of c(u,v) - f(u,v) of any of the edges in the augmenting path

Question 6

What are the 3 important things the Ford Fulkerson algorithm depends on?

Answer 6

• Residual networks, cuts and augmenting paths

Question 7

What are residual networks?

Answer 7

• A residual network consists of edges that can admit more flow
• given the flow network G and a flow f in that network, we define the residual network Gf so Gf depends upon the given flow f. We want to account for the edges that can still receive more flow

Question 8

How is a forward edge’s residual value calculated?

Answer 8

∆ = capacity - flow
so if we have the edge in G - 5/8
- the forward edge’s value = 8-5 = 3

Question 9

How is a backward edge’s residual value calculated?

Answer 9

∆ = flow value
so if we have the edge in G - 5/8
- the backward edge’s value = 5

Question 10

What is an augmenting path in a residual graph?

Answer 10

• Given a flow network and a flow f, an augmenting path p is a directed path following forward and backward edges from s to t in the residual network
• informally an augmenting path is a path from the source to the sink in which we can send more net flow down

Question 11

How do we update the edges in the residual network after we increase the flow along an augmenting path?

Answer 11

• on forwards edges we increase the flow by the minimum residual flow left (out of all the edges in the augmenting path)
• on backwards edges we decrease the flow by the minimum residual flow left
• we then update the residual network, as for example some edges may become backwards edges or may not be forwards edges anymore

Question 12

What does the max flow/min cut theorem tell us?

Answer 12

• That the flow is maximum if and only if no augmenting paths exist anymore

Question 13

What is a cut in a flow network?

Answer 13

• A cut (S,T) in a flow network is a partition of the set of vertices in the network into two subsets S and T where T = V - S. In S we include the source node and in T we include all other vertices.

Question 14

• What is the net flow across a cut?
• What is the capacity of a cut?

Answer 14

• Net flow is the sum of the flows of the edges from S side to T side minus the flows of the edges from T side to S side
• Capacity = sum of capacity of edges that go from S side to T side

Question 15

What is the maximum flow equal to in a flow network

Answer 15

Maximum flow is equal to the capacity of a minimum cut in the network

Question 16

How do we know to terminate the Ford-Fulkerson algorithm/know we’ve found the correct cut to observe the max flow min cut theorem?

Answer 16

• If in the residual network, we observe that each of the weights along the incoming edges are saturated (completely full e.g. 1/1, 2/2, 4/4)
• this means that if we look at the residual network each of these edges are denoted as backwards edges
• so if we were to try go towards the sink node t, we have no way of getting there because the only edges that could get us out of the source are pointing back towards the source, so we have no way of producing an augmenting path from the source to the sink
• therefore the BFS/DFS would report there’s no augmenting paths left and the algorithm knows to stop

Question 17

What is the running time of the Ford Fulkerson algorithm?

Answer 17

O(|f|m)

Question 18

What are Bipartite graphs?

Answer 18

• A bipartite graph is a graph whose vertex set can be partitioned into two sets X and Y so that every edge joins a vertex in X to a vertex in Y and vice versa
• can’t have cycles in a bipartite graph of an odd length, since if we start at a node and want to return to it, this is always an even number of edges
• an odd cycle would mean the graph isn’t bipartite
• we use bipartite graphs in situations where we want to pair or assign one set of objects with another set of objects

Question 19

What are matchings?

Answer 19

A matching is a subset of the edges of a bipartite graph where each vertex appears in at most one edge
(matchings share no common endpoints)

Question 20

What algorithm can we use to find a bipartite graphs maximum matching size?

Answer 20

• we can create a flow network with the bipartite graph by adding on a source and sink node to it and linking all the pairs of nodes, we can then use the ford fulkerson algorithm to find the maximum matching size