Network concepts
Identify vertices, edges, degree, weighted and directed networks; recognise connected networks; interpret network diagrams in practical contexts.
Worked examples
Vertices, edges and degree
Straightforward
Problem
A network has vertices A, B, C, D and E with the following edges: AB, AC, BC, BD and CE. Find (a) the total number of edges, (b) the degree of vertex B, and (c) verify using the handshaking lemma.
1
Part (a): count the edges.
List all edges: AB, AC, BC, BD, CE — that is 5 edges.
2
Part (b): find the degree of B.
An edge touches B if B is one of its endpoints. Edges involving B: AB, BC, BD — that is 3 edges, so degree of B = 3.
3
Part (c): verify using the handshaking lemma, that the sum of all degrees equals twice the number of edges.
Degrees: A = 2 (AB, AC), B = 3 (AB, BC, BD), C = 3 (AC, BC, CE), D = 1 (BD), E = 1 (CE).
Answer
(a) 5 edges. (b) Degree of B = 3. (c) Sum of degrees = 10 = 2 × 5, confirming the handshaking lemma.
Directed flow network — source, sink and capacity
Moderate
Problem
A directed network models water flow through a treatment plant. The diagram has: source S, intermediate nodes A and B, sink T; directed edges S→A (capacity 8), S→B (capacity 5), A→T (capacity 6), A→B (capacity 3), B→T (capacity 7). Identify (a) the source and sink, (b) the total capacity leaving S, and (c) the total capacity entering T.
1
Part (a): identify the source and sink.
The source is the vertex with only outgoing edges: S. The sink is the vertex with only incoming edges: T.
2
Part (b): find the total capacity leaving S.
Edges leaving S: S→A (8) and S→B (5).
3
Part (c): find the total capacity entering T.
Edges entering T: A→T (6) and B→T (7).
4
Comment on the result.
In this particular network, total capacity out of S equals total capacity into T (both are 13). This is a coincidence of the edge weights — the actual maximum flow may still be less, depending on intermediate constraints.
Answer
(a) Source = S, sink = T. (b) Capacity out of S = 13 units. (c) Capacity into T = 13 units.
Interpreting a network in context
Moderate
Problem
A road network has five intersections (vertices) A, B, C, D and E. Roads are one-way (directed). The capacities represent vehicles per minute. The network has: A→B (12), A→C (8), B→D (10), C→D (5), C→E (6), D→E (9). A is the entry point; E is the exit. Identify the source, the sink, and determine the maximum possible flow that could leave A.
1
Identify the source and sink.
Source: A — all its edges point away from it. Sink: E — all edges point into it (D→E and C→E).
2
Add the capacities of all edges leaving A to find the maximum possible flow leaving A.
3
Explain why this is only an upper bound.
This is an upper bound on the flow. The actual maximum flow through the network (from A to E) may be less — it depends on which intermediate edges create a bottleneck. This is determined by the maximum-flow minimum-cut theorem, studied in the next sub-topic.
Answer
Source = A, sink = E. The maximum possible flow leaving A is 20 vehicles per minute (an upper bound on the network's true maximum flow).
Practise
Q1·Straightforward
A network has 5 vertices and 7 edges. How many edges does it have?
Explanation
The network has **7 edges**. An edge connects two vertices; here, the 5 vertices are joined by 7 edges.
Q2·Straightforward
In a network diagram, vertex A is connected to vertices B, C and D. What is the degree of vertex A?
Explanation
Vertex A is connected to B, C and D — that is 3 edges meeting at A.
The **degree** of vertex A = **3**.
The **degree** of vertex A = **3**.
Q3·Straightforward
In a directed network, what does an arrow on an edge represent?
Explanation
In a **directed** network (also called a digraph), each edge has an arrow showing the **direction** in which flow or travel is allowed. Flow cannot travel against the arrow.
Q4·Straightforward
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?
Explanation
The edges touching Q are: PQ, QR and QS — that is 3 edges.
Degree of Q = **3**.
Degree of Q = **3**.
Q5·Straightforward
A weighted network has numbers assigned to each edge. What do these numbers typically represent in a flow-network context?
Explanation
In a **flow network**, the number (weight) on each edge represents its **capacity** — the maximum amount of flow that can pass along that edge per unit time. For example, an edge labelled 8 can carry at most 8 units of flow.
Q6·Moderate
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?
Explanation
Sum of the five known degrees: .
The sixth vertex must have degree .
(As a check: edges.)
The sixth vertex must have degree .
(As a check: edges.)
Q7·Moderate
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 = (number of edges).
Handshaking lemma: sum of all degrees = (number of edges).
Explanation
Sum of degrees: .
Q8·Moderate
In a flow network, what is the **source** vertex?
Explanation
The **source** is where flow originates. In a directed flow network, all edges at the source point **outward** — no flow enters it from elsewhere. It is usually labelled S.
The **sink** is the opposite: all edges point **inward** to it (usually labelled T).
The **sink** is the opposite: all edges point **inward** to it (usually labelled T).
Q9·Moderate
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?
Explanation
The edges leaving S carry at most units of flow in total.
Maximum possible flow out of S = **16 units**.
(The actual maximum flow through the network may be less than 16, depending on bottlenecks elsewhere.)
Maximum possible flow out of S = **16 units**.
(The actual maximum flow through the network may be less than 16, depending on bottlenecks elsewhere.)
Q10·Moderate
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?
Explanation
The edges entering T are:
- A→T with capacity 5
- B→T with capacity 7
Total capacity into T: units.
- A→T with capacity 5
- B→T with capacity 7
Total capacity into T: units.
Q11·Challenging
A network is described as **connected**. Which of the following correctly defines a connected network?
Explanation
A **connected** network is one in which there is a path from every vertex to every other vertex. If any vertex is isolated (no edges), or if the network splits into separate pieces with no path between them, it is not connected.
Q12·Challenging
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?
What is the total capacity of edges that enter the sink T?
Explanation
Edges entering T:
- B→T: capacity 9 L/min
- C→T: capacity 8 L/min
Total capacity into T: L/min.
- B→T: capacity 9 L/min
- C→T: capacity 8 L/min
Total capacity into T: L/min.
Q13·Challenging
A connected network has 7 edges. Using the handshaking lemma, what is the total sum of the degrees of all vertices?
Explanation
By the handshaking lemma:
Open Math
Network concepts
Networks · MS-N2
Name:
Date:
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 = (number of edges).
Handshaking lemma: sum of all degrees = (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?
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?
Worked solutions and answers at openmath.au/year-12/standard-2/network-flow/network-concepts