Network flow

Analyse directed networks with capacities; apply the maximum-flow minimum-cut theorem to find the maximum flow through a network.

Networks · MS-N2

Sub-topics

Network concepts

Identify vertices, edges, degree, weighted and directed networks; recognise connected networks; interpret network diagrams in practical contexts.

Flow problems

Apply the maximum-flow minimum-cut theorem to directed networks; identify cuts, calculate cut capacity, and determine the maximum flow from source to sink.

Open Math

Network flow

Networks · MS-N2

Name:

Date:

Network concepts

Q1Straightforward

A network has 5 vertices and 7 edges. How many edges does it have?

Q2Straightforward

In a network diagram, vertex A is connected to vertices B, C and D. What is the degree of vertex A?

Q3Straightforward

In a directed network, what does an arrow on an edge represent?

A.The weight (capacity) of the edge
B.The direction that flow or travel is permitted along the edge
C.That the edge has been traversed
D.That the two vertices are the same

Q4Straightforward

A network has 4 vertices: P, Q, R and S. The edges are PQ, PR, QR and QS. What is the degree of vertex Q?

Q5Straightforward

A weighted network has numbers assigned to each edge. What do these numbers typically represent in a flow-network context?

A.The number of vertices in the network
B.The capacity (maximum flow) along that edge
C.The length of time the network has been in use
D.The degree of the vertex at each end

Q6Moderate

A network has 6 vertices. The degrees of five of the vertices are 2, 3, 2, 4 and 1. The sum of all degrees in any network equals twice the number of edges. If the total degree sum is 16, what is the degree of the sixth vertex?

Q7Moderate

A connected network has 5 vertices with degrees 2, 4, 3, 3 and 2. Using the handshaking lemma, how many edges does this network have?

Handshaking lemma: sum of all degrees =

2 \times

(number of edges).

Q8Moderate

In a flow network, what is the **source** vertex?

A.A vertex where all edges point inward (no outgoing edges)
B.A vertex where all edges point outward (no incoming edges), where flow originates
C.A vertex with the highest capacity edge attached
D.Any vertex in the middle of the network

Q9Moderate

A pipeline network has a source S and a sink T. The edges leaving S have capacities 5, 8 and 3. What is the maximum possible flow that can leave S?

Q10Moderate

A directed network has 4 vertices (S, A, B, T) and directed edges S→A (capacity 6), S→B (capacity 4), A→T (capacity 5), B→T (capacity 7) and A→B (capacity 3). What is the total capacity of all edges entering the sink T?

Q11Challenging

A network is described as **connected**. Which of the following correctly defines a connected network?

A.Every vertex has the same degree
B.There is a path between every pair of vertices
C.The network has no cycles
D.Every edge is directed

Q12Challenging

A directed network models water flow in a irrigation system. The source S has two outgoing pipes: S→A (capacity 10 L/min) and S→B (capacity 6 L/min). A has two outgoing pipes: A→C (capacity 7 L/min) and A→B (capacity 4 L/min). B has one outgoing pipe: B→T (capacity 9 L/min). C has one outgoing pipe: C→T (capacity 8 L/min).

What is the total capacity of edges that enter the sink T?

Q13Challenging

A connected network has 7 edges. Using the handshaking lemma, what is the total sum of the degrees of all vertices?

Flow problems

Q14Straightforward

A cut divides the vertices of a network into two sets: those containing the source (S-side) and those containing the sink (T-side). A cut passes through three edges with capacities 4, 6 and 3. What is the capacity of this cut?

Q15Straightforward

The maximum-flow minimum-cut theorem states that:

A.The maximum flow equals the number of edges in the network
B.The maximum flow from source to sink equals the capacity of the minimum cut
C.The minimum cut passes through the source vertex
D.The maximum flow equals the sum of all edge capacities

Q16Straightforward

A simple directed network has source S, one intermediate vertex A and sink T. The edges are S→A (capacity 5) and A→T (capacity 9). What is the maximum flow from S to T?

Q17Moderate

A directed network has source S, sink T and one intermediate vertex A. Edges: S→A (capacity 7), S→T (capacity 3), A→T (capacity 5).

There are two paths from S to T:
- Path 1: S→T directly (capacity 3)
- Path 2: S→A→T (the bottleneck is the smaller of 7 and 5)

What is the maximum flow from S to T?

Q18Moderate

A directed network has source S, sink T, and two intermediate vertices A and B. The edges are:
- S→A (capacity 6), S→B (capacity 4)
- A→T (capacity 5), B→T (capacity 7), A→B (capacity 3)

A cut is drawn so that the S-side contains {S} and the T-side contains {A, B, T}. Calculate the capacity of this cut.

Q19Moderate

Using the same network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3):

A second cut is drawn so that the S-side = {S, A, B} and the T-side = {T}. Calculate the capacity of this cut.

Q20Moderate

For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), two of the possible cuts have capacities 10 and 12 respectively. A third cut (S-side = {S, A}, T-side = {B, T}) passes through edges S→B (4), A→T (5) and A→B (3). What is the capacity of this third cut?

Q21Moderate

For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), the three cut capacities are 10, 12 and 12. What is the maximum flow from S to T?

Q22Challenging

A directed pipeline network has source S, sink T and intermediate vertices P and Q:
- S→P (capacity 8), S→Q (capacity 5)
- P→T (capacity 6), Q→T (capacity 4), P→Q (capacity 3)

Consider the cut with S-side = {S, P} and T-side = {Q, T}. Calculate its capacity.

Q23Challenging

Using the same pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3):

You have found these cut capacities so far:
- Cut {S}: capacity 13
- Cut {S, P}: capacity 14

Now find the capacity of the cut with S-side = {S, Q} and T-side = {P, T}.

Q24Challenging

For the pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3), the cuts evaluated so far are:
- Cut {S}: 13
- Cut {S, P}: 14
- Cut {S, Q}: 12
- Cut {S, P, Q}: edges P→T (6) and Q→T (4) = 10

Using the maximum-flow minimum-cut theorem, what is the maximum flow from S to T?

Q25Challenging

A directed network has source S, sink T and intermediate vertices A, B and C:
- S→A (capacity 10), S→B (capacity 8)
- A→C (capacity 6), A→B (capacity 4)
- B→T (capacity 9), C→T (capacity 7)

The cut with S-side = {S, A, B} and T-side = {C, T} passes through edges A→C and B→T. Calculate the capacity of this cut.

Worked solutions and answers at openmath.au/year-12/standard-2/network-flow