5.1 Network
Graph theory is an important branch of mathematics used to model relationships between discrete objects. A graph consists of a set of dots called vertices and lines linking them called edges. A network is part of a graph where vertices and edges have specific characteristics, representing real-world systems such as transportation, computer networks, and social connections.
Learning Objectives
- Identify and explain a network as a graph.
- Compare and contrast directed graphs and undirected graphs, as well as weighted graphs and unweighted graphs.
- Identify and draw subgraphs and trees.
- Represent information in the form of networks.
- Solve problems involving networks.
Comparison between a Loop and Multiple Edges
See how loops and multiple edges contribute to vertex degrees and how their edge pairs are written.
Brief Explanation
What is a Graph?
A graph is used to represent discrete objects and their relationships. It is denoted as an ordered pair \(G = (V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges linking pairs of vertices.
What is a Network?
A network is part of a graph where the vertices and edges possess their own characteristics. The data structure has a many-to-many relation.
Degree of a Vertex
The degree of a vertex is the number of edges that connect to it. The sum of degrees of a graph is twice the number of edges:
\[\sum d(v) = 2\,n(E) \quad (v \in V)\]
The sum of degrees of any graph is always an even number. A graph cannot be drawn if the sum of degrees is odd. An isolated vertex has a degree of 0 and is not connected to other vertices.
| Graph type | Key feature | Degree rule |
|---|---|---|
| Simple graph | No loops and no multiple edges | Each edge contributes 1 to each endpoint |
| Multiple edges | More than one edge connects the same two vertices | Each edge is counted separately |
| Loop | An edge starts and ends at the same vertex | Adds 2 to the degree of that vertex |
| Directed graph | Each edge has a direction (arrow) | \(d(v) = d_{in}(v) + d_{out}(v)\) |
| Weighted graph | Each edge has a numerical value | Weight represents distance, time, cost, etc. |
Try Answering First
Read the question, answer it in your mind, then press “Check Answer”.
A graph has 5 vertices with degrees 2, 3, 3, 4, and 2. Can this graph be drawn? State your reason.
A tree has 8 vertices. How many edges does the tree have?
In a directed graph, vertex \(A\) has 3 arrows pointing towards it and 2 arrows pointing away from it. What is the degree of vertex \(A\)?
Subgraphs, Trees and Networks
Subgraphs and the minimum-weight tree, representing a table as a network, and solving route problems.
What is a subgraph?
A subgraph is part of a graph, or the whole graph, redrawn without changing the original positions of the vertices and edges. A graph \(H\) is a subgraph of graph \(G\) if all three conditions hold:
(a) the vertex set of \(H\) is a subset of the vertex set of \(G\), that is \(V(H) \subset V(G)\);
(b) the edge set of \(H\) is a subset of the edge set of \(G\), that is \(E(H) \subset E(G)\);
(c) the vertex pairs of the edges of \(H\) are the same as the edges of \(G\).
In short: a vertex in \(G\) is a subgraph of \(G\); an edge together with the vertices it connects is a subgraph of \(G\); and every graph is a subgraph of itself. Condition (c) matters — if a loop or an edge label is moved to a different vertex, the graph is not a subgraph.
Trees and the minimum-weight tree
A tree is a subgraph with these properties: it is a simple graph (no loops, no multiple edges); all vertices are connected and each pair of vertices is joined by exactly one path; and the number of edges \(= n - 1\) for \(n\) vertices.
For a weighted graph, the minimum-weight tree is the tree that connects every vertex with the smallest possible total weight.
An undirected weighted graph: 5 vertices, 7 edges. Draw a tree with the minimum total weight.
The minimum-weight tree: total weight \(= 55\).
Representing information in the form of a network
A network can be drawn as a directed or undirected graph, and as a weighted or unweighted graph. To turn a table into a network, choose one column to be the vertices and the other to be the edges.
The table below shows six pupils and the two games each one likes. Let the vertices be the types of games and the edges represent the pupils’ names. Each pupil likes exactly two games, so each pupil produces exactly one edge.
| Name of pupil | Games liked |
|---|---|
| Edmund | Badminton, Chess |
| Azwan | Football, Sepak takraw |
| Rajan | Chess, Football |
| Aina | Chess, Netball |
| Maria | Badminton, Netball |
| Jenny | Netball, Volleyball |
The resulting network: 6 vertices (games) and 6 edges (pupils). Degrees \(= 3, 3, 2, 2, 1, 1\); sum of degrees \(= 12 = 2 \times 6\) edges.
Solving network problems: shortest and longest route
The diagram below shows the one-way paths Izarul can choose for his running practice. Vertex \(v_1\) is the starting position and \(v_5\) is the ending position. Determine (a) the shortest distance, (b) the longest distance, and (c) the vertices passed through if the run is between 1.4 km and 2.1 km.
Every edge is one-way, in the direction of the arrow. Weights are in metres.
Common Mistakes
- Counting a loop as degree 1 instead of degree 2. A loop adds 2 to the degree of its vertex.
- Confusing the order of vertex pairs in directed graphs; writing \((A, B)\) when the arrow actually points from \(B\) to \(A\), which should be \((B, A)\).
- Forgetting that every tree must be fully connected; drawing a disconnected graph with \(n - 1\) edges and mistakenly calling it a tree.
- Forming closed cycles when asked to draw a tree from a graph.
Misconceptions
Any graph with \(n(E) = n(V) - 1\) is automatically a tree.
The condition \(n(E) = n(V) - 1\) is necessary but not sufficient on its own; all vertices must also be connected with no cycles or loops.
In an undirected graph, \((u, v)\) and \((v, u)\) represent two separate edges.
In an undirected graph, \((u, v)\) and \((v, u)\) represent the exact same edge. They only represent different edges in a directed graph.
Summary
- Graph: \(G = (V, E)\) where \(V\) is the set of vertices and \(E\) is the set of edges.
- Degree Sum Formula: \(\sum d(v) = 2 \times n(E)\), which must always be an even number.
- Loop adds 2 to the vertex degree; multiple edges connect the same pair of vertices.
- Directed graph: Edges have arrows; \(d(v) = d_{in}(v) + d_{out}(v)\).
- Weighted graph: Edges carry values representing quantities like distance, cost, or time.
- Subgraph: A subset of vertices and edges preserving original graph connections.
- Tree: A connected simple subgraph without cycles, having \(n\) vertices and \(n - 1\) edges.
Short Activity
Complete all parts first, then press the check answer button.
A. Objective Quiz
1 Which of the following sets of vertex degrees cannot form a graph?
2 Which statement is a necessary property of a tree with \(n\) vertices?
B. Fill in the Blanks
3 If a graph has 7 edges, the sum of degrees of all its vertices is .
4 In a directed graph, the degree of a vertex \(v\) is determined by adding the number of edges entering the vertex, \(d_{in}(v)\), and the number of edges leaving the vertex, .
C. Drag and Drop: Match Each Concept to Its Description
Drag each concept to the correct description. On a phone, tap the answer choice first, then tap the description box.
