Mathematics notes, chapter 5
Network in Graph Theory
Textbook Mathematics Form 4 KSSM (DLP), pages 128–153
What this chapter covers
- Identify and explain a network as a graph, with vertices, edges, degrees, loops and multiple edges (5.1.1)
- Compare directed and undirected graphs, and weighted and unweighted graphs (5.1.2)
- Identify and draw subgraphs and trees, including a tree with minimum total weight (5.1.3)
- Represent information in the form of networks (5.1.4)
- Solve problems involving networks (5.1.5)
5.1Network
A network as a graph (5.1.1)
A graph is a set of dots joined by lines. Each dot is a vertex and each line joining two vertices is an edge. A network is a graph used to show how objects are linked, for example towns joined by roads or people joined by friendship.
| Network | Vertices | Edges |
|---|---|---|
| Transport | Towns, cities, stations | Roads, highways, railway lines |
| Social | People, groups, organisations | Relationships such as friends or family |
A graph is written as G = (V, E). V is the set of vertices and E is the set of edges, each edge written as a pair of vertices. The edge (1, 2) is the same edge as (2, 1) in an undirected graph.
The degree of a vertex, d(v), is the number of edges joined to it. For every graph, the sum of the degrees is twice the number of edges: Σd(v) = 2 × n(E).
In the graph above: d(1) = 2, d(2) = 3, d(3) = 2, d(4) = 3, d(5) = 3, d(6) = 1. The sum is 14 = 2 × 7.
A simple graph has no loops and no multiple edges. A loop starts and ends at the same vertex and adds 2 to that vertex's degree. Multiple edges are two or more edges between the same pair of vertices.
Example 6 (textbook p. 133): can a graph have these degrees?
(a) 3, 2, 2, 1, 3: sum = 11, which is odd, so it cannot be drawn.(b) 2, 1, 1, 3, 3, 2: sum = 12, which is even, so it can be drawn.
Reading a graph from V and E (Example 5, textbook p. 133)
V = {P, Q, R, S} and E = {(P, P), (P, Q), (P, S), (Q, S), (Q, S), (Q, R), (S, R), (R, R)}.A pair such as (P, P) is a loop. A pair that appears twice, such as (Q, S), is a multiple edge.
n(E) = 8, so the sum of degrees = 16. Check: d(P) = 2 + 1 + 1 = 4, d(Q) = 1 + 2 + 1 = 4, d(S) = 1 + 2 + 1 = 4, d(R) = 1 + 1 + 2 = 4. Sum = 16.
Counting a loop as 1 in the degree. A loop is a line leaving the vertex and coming back, so it adds 2.
A graph has 9 edges. What is the sum of the degrees? Could a graph have vertex degrees 4, 3, 3, 2, 2?
Show answerHide answer
Sum = 2 × 9 = 18.
4 + 3 + 3 + 2 + 2 = 14, which is even, so it can be drawn (7 edges).
4 + 3 + 3 + 2 + 2 = 14, which is even, so it can be drawn (7 edges).
Directed, undirected, weighted and unweighted graphs (5.1.2)
| Undirected graph | Directed graph | |
|---|---|---|
| Edges | No direction. (A, B) and (B, A) are the same edge. | Each edge has an arrow, from the initial vertex to the terminal vertex. (B, A) and (A, B) are different edges. |
| Degree | d(v) = number of edges at v | d(v) = din(v) + dout(v) |
din(v) is the number of edges going into v. dout(v) is the number of edges coming out of v. A loop counts once in and once out.
A vertex that appears in V but in no edge is an isolated vertex.
| Weighted graph | Unweighted graph | |
|---|---|---|
| Edges | Each edge has a value (weight) | No values on the edges |
| Examples | Distance, travelling time, cost, current | Organisation chart, flow map, tree map |
Example 8 (textbook p. 138): v1 to v5
Shortest: v1 → v2 → v5 = 600 + 500 = 1 100 m = 1.1 kmLongest: v1 → v2 → v3 → v4 → v5 = 600 + 900 + 500 + 500 = 2 500 m = 2.5 km
Between 1.4 km and 2.1 km: v1 → v3 → v4 → v5 (1 500 m) and v1 → v2 → v4 → v5 (1 900 m)
In a directed graph you may only follow an arrow in its own direction. List every route first, then add the weights along each one.
In a directed graph, vertex T has edges (T, S), (T, P), (T, T) and (Q, T). Find din(T), dout(T) and d(T).
Show answerHide answer
dout(T): (T, S), (T, P), (T, T) = 3
din(T): (T, T), (Q, T) = 2
d(T) = 3 + 2 = 5
din(T): (T, T), (Q, T) = 2
d(T) = 3 + 2 = 5
Subgraphs and trees (5.1.3)
A graph H is a subgraph of G if its vertices and edges all come from G, and each edge keeps the same pair of vertices as in G. A single vertex, a single edge with its two vertices, and G itself are all subgraphs of G.
A tree is a connected graph with no loops and no multiple edges, where each pair of vertices is joined by only one path. A tree with n vertices has n − 1 edges.
Is H a subgraph of G? (Example 9, textbook p. 139)
Check three things: (1) every vertex of H is in G; (2) every edge of H is in G; (3) each edge joins the same two vertices as in G.A drawing fails if an edge is moved to join different vertices, or if a loop is drawn on a different vertex, even when the picture looks similar.
Thinking that any graph with n − 1 edges is a tree. It must also be connected. Example 10(d) (textbook p. 140) has 6 vertices and 4 edges, so it is not a tree because some vertices are not joined to the rest.
Making a tree from a graph: a connected graph with n vertices and more than n − 1 edges has too many edges. Remove edges, always keeping every vertex connected, until n − 1 edges are left. In a weighted graph, remove the edges with the greatest weights first.
Check a tree
A connected graph has 8 vertices.A tree needs 8 − 1 = 7 edges.
If it has 10 edges, then 10 − 7 = 3 edges must be removed.
A tree has 12 vertices. How many edges does it have? A connected graph has 6 vertices and 8 edges; how many edges are removed to make a tree?
Show answerHide answer
12 − 1 = 11 edges.
A tree needs 5 edges, so 8 − 5 = 3 edges are removed.
A tree needs 5 edges, so 8 − 5 = 3 edges are removed.
Representing information as a network (5.1.4)
Choose what the vertices are (people, places, games) and what the edges are (the links between them). A table with two items per row becomes a graph: one edge per row.
Example 15 (textbook p. 144): pupils and games
Vertices: the games. Edges: the pupils. Each pupil likes two games, so each pupil is one edge joining those two games (Edmund joins Badminton and Chess). Choose as edges the information that is not repeated.Check: the sum of degrees = 2 × number of edges. If 6 pupils each give 2 games, the sum of degrees is 12.
Weights can be distance, time or cost. A shorter distance may not give a shorter time, because of traffic (Example 14, textbook p. 143).
A tree never has a closed path, so it is the cheapest way to link every vertex. This is why a minimum total weight tree is used to plan cables, pipes and roads that must reach every place once.
Solving problems with networks (5.1.5)
- List every possible route or choice.
- Add the weights (cost, time, distance) for each one.
- Compare against the conditions in the question (cheapest, fastest, through certain vertices).
- Give a reason, for example comfort, safety, time and cost (Example 16, textbook p. 146).
Example 16 (textbook p. 146): choosing the transport
Johor Bahru to Kota Bharu. Bus RM64 to RM75, 9 hours. Train with a bed: adult RM49 to RM55, child RM32 to RM38, 17 hours. Cab RM120 per cab, 9 hours.Two adults and two children (cheapest prices): bus 4 × 64 = RM256. Train 2 × 49 + 2 × 32 = RM162. Cab = RM120.
The cab is the most economical for four people. For one adult the bus (RM64 to RM75) is better: it costs less than the cab and takes the same 9 hours.
A bus ticket costs RM42 per adult and a train ticket RM28. A cab costs RM90 for up to 4 people. Which is cheapest for 4 adults?
Show answerHide answer
Bus 4 × 42 = RM168; train 4 × 28 = RM112; cab RM90. The cab is cheapest.