Chapter 5: Networks in Graph Theory

Overview

Welcome to Chapter 5 of Form 4 Mathematics! This chapter introduces you to the fascinating world of graph theory and networks. You'll learn how to represent relationships and connections using graphs, understand different types of graphs, and solve real-world problems involving networks. Graph theory has applications in computer science, transportation, social networks, and many other fields.

What You'll Learn:

Identify and describe graphs as networks
Compare directed vs. undirected graphs and weighted vs. unweighted graphs
Find subgraphs and trees
Represent information in network form
Solve problems involving networks

Learning Objectives

After completing this chapter, you will be able to:

Identify and describe networks as graphs
Compare and contrast directed and undirected graphs
Compare and contrast weighted and unweighted graphs
Identify and draw subgraphs and trees
Represent information in network form
Solve problems involving networks

Key Concepts

Graphs

A graph G consists of a set of vertices V and a set of edges E, written as G = (V, E). Vertices are points, while edges are lines connecting pairs of vertices.

Basic Components:

Vertices (V): The nodes or points in the graph
Edges (E): The connections between vertices
Graph notation: $G = (V, E)$

Example:

V = {A, B, C, D} (vertices)
E = {AB, BC, CD, DA} (edges)
G = (V, E) represents the complete graph

Degree

The degree of a vertex is the number of edges connected to it. The sum of degrees of all vertices in a graph is twice the number of edges:

\sum_{v \in V} d(v) = 2|E|

Example: In a triangle graph with vertices A, B, C:

Each vertex has degree 2 (connected to 2 other vertices)
Sum of degrees = $2 + 2 + 2 = 6$
Number of edges = 3 (since $6 = 2 \times 3$ )

Degree Sequence: For a graph, the degree sequence lists the degrees of all vertices in non-increasing order.

Directed vs. Undirected Graphs

Undirected Graphs:

Edges have no direction (no arrows)
Connections are bidirectional
Mathematical representation: If there's an edge between A and B, it's the same as between B and A
Example: Friendship networks, road networks (if bidirectional)

Directed Graphs (Digraphs):

Edges have direction (arrows)
Connections are one-way
Mathematical representation: $(u, v) \neq (v, u)$ unless both edges exist
Example: Twitter follows, web links, one-way streets

Weighted vs. Unweighted Graphs

Unweighted Graphs:

Edges have no numerical values
Only presence/absence of connections matters
Binary representation: edge exists (1) or doesn't exist (0)
Example: Social networks (friend or not friend)

Weighted Graphs:

Edges have numerical values (weights)
Weights can represent distance, cost, time, etc.
Mathematical representation: $w: E \rightarrow \mathbb{R}$ where $w(e)$ is the weight of edge $e$
Example: Road networks (distance between cities), computer networks (data transfer rates)

Subgraphs

A subgraph is a subset of a graph or the entire graph itself. Formally, if $G = (V, E)$ , then $H = (V_H, E_H)$ is a subgraph of $G$ if:

$V_H \subseteq V$ (vertex subset)
$E_H \subseteq E$ (edge subset)
Every edge in $E_H$ connects vertices in $V_H$

Example: If G = ({A, B, C, D}, {AB, BC, CD, DA}), then:

({A, B, C}, {AB, BC}) is a subgraph
({A, C}, {AC}) is a subgraph (if AC edge exists)

Trees

A tree is a subgraph that connects all vertices without forming any cycles.

Properties of Trees:

Connected (all vertices reachable from any other vertex)
No cycles
If a tree has n vertices, it has exactly n-1 edges
Adding any edge creates exactly one cycle
Removing any edge disconnects the tree

Mathematical Properties: For a tree T with n vertices and m edges:

$m = n - 1$
$\sum_{v \in V} d(v) = 2(n - 1)$
Number of leaves (degree 1 vertices) ≥ 2

Important Formulas and Methods

Sum of Degrees Formula

The sum of degrees of all vertices is twice the number of edges:

\sum_{v \in V} d(v) = 2|E|

Example: If a graph has 6 vertices with degrees 3, 3, 2, 2, 2, 2: Sum of degrees = 3 + 3 + 2 + 2 + 2 + 2 = 14 Number of edges = 14 / 2 = 7

Graph Representation

Adjacency Matrix: A matrix showing which vertices are connected.

Example: For graph with vertices A, B, C and edges AB, BC:

	A	B	C
A	0	1	0
B	1	0	1
C	0	1	0

Adjacency List: A list showing the neighbors of each vertex.

Example: A: [B] B: [A, C] C: [B]

Finding Optimal Paths

In weighted graphs, finding optimal paths involves:

Shortest Path: Minimum total weight
Maximum Path: Maximum total weight
Minimum Spanning Tree: Connect all vertices with minimum total weight

Dijkstra's Algorithm (Shortest Path):

Start at the source vertex
Initialize distances: $d(s) = 0$ , $d(v) = \infty$ for all other vertices
Use priority queue to select vertex with minimum distance
Update distances to adjacent vertices
Repeat until all vertices processed

Kruskal's Algorithm (Minimum Spanning Tree):

Sort all edges by weight in ascending order
Initialize forest with each vertex as separate tree
Add edges to forest if they don't form cycles
Stop when all vertices connected

Step-by-Step Solved Examples

Example 1: Basic Graph Concepts

Problem: A graph has vertices A, B, C, D, E with edges AB, AC, AD, BC, CD, DE. Find: a) The degree of each vertex b) The sum of all degrees c) Verify the sum of degrees formula

Solution: a) Degrees:

A: connected to B, C, D → degree 3
B: connected to A, C → degree 2
C: connected to A, B, D → degree 3
D: connected to A, C, E → degree 3
E: connected to D → degree 1

b) Sum of degrees = 3 + 2 + 3 + 3 + 1 = 12 c) Number of edges = 6 (AB, AC, AD, BC, CD, DE) Sum of degrees = 12 = 2 × 6 ✓

Example 2: Directed vs. Undirected Graphs

Problem: Compare the following: a) An undirected graph representing friendship in a class b) A directed graph representing who follows whom on social media

Solution: a) Undirected Friendship Graph:

Vertices: Students in class
Edges: Bidirectional (if A is friends with B, then B is friends with A)
No weights needed (simple friendship)

b) Directed Social Media Graph:

Vertices: Users
Edges: Unidirectional (if A follows B, it doesn't mean B follows A)
Possible weights could be interaction frequency

Example 3: Weighted Graph Applications

Problem: A delivery company has routes between cities with distances:

A to B: 150 km
A to C: 200 km
B to C: 100 km
B to D: 175 km
C to D: 125 km

Find the shortest path from A to D.

Solution: List all possible paths from A to D:

A → B → D: 150 + 175 = 325 km
A → C → D: 200 + 125 = 325 km
A → B → C → D: 150 + 100 + 125 = 375 km

Answer: The shortest path is 325 km (either A → B → D or A → C → D).

Example 4: Tree Identification

Problem: Determine which of the following are trees: a) Graph with 4 vertices and 3 edges forming a path b) Graph with 4 vertices and 4 edges forming a cycle c) Graph with 5 vertices and 4 edges with no cycles

Solution: a) Tree: 4 vertices, 3 edges, connected, no cycles ✓ b) Not a Tree: Has a cycle ✓ c) Tree: 5 vertices, 4 edges, no cycles (connected by definition) ✓

Example 5: Network Problem

Problem: A small computer network has 6 computers. The network administrator wants to ensure that every computer can communicate with every other computer either directly or through other computers. What is the minimum number of connections needed?

Solution: This requires a spanning tree. For n vertices, a tree has n-1 edges. Number of connections needed = 6 - 1 = 5

Answer: Minimum 5 connections are needed.

Example 6: Spanning Tree Visualization

Problem: Find the minimum spanning tree for the following weighted network:

A --4-- B --2-- C
|      |      |
5      3      6
|      |      |
D --7-- E --1-- F

Solution: Using Kruskal's algorithm:

Sort edges: EF(1), BC(2), AB(4), DE(7), AC(5), BD(3), DF(6), AE(5), BE(3), CF(6)
Add EF, BC, AB, DE (avoiding cycles)
Final MST: AB, BC, EF, DE

MST Weight: $4 + 2 + 1 + 7 = 14$

Example 7: Network Flow Problem

Problem: A water supply network connects reservoir R to cities A, B, C. The capacities are:

R → A: 100 units
R → B: 150 units
A → B: 50 units
A → C: 80 units
B → C: 120 units

What's the maximum flow from R to C?

Solution: Flow Analysis:

Path R → A → C: min(100, 80) = 80 units
Path R → B → C: min(150, 120) = 120 units
Path R → A → B → C: min(100-80=20, 50, 120-120=0) = 0 units

Total Maximum Flow: $80 + 120 = 200$ units

Real-world Applications

1. Transportation Networks

Applications:

Shortest Route Planning: Using Dijkstra's algorithm for navigation
Traffic Flow Optimization: Balancing loads across road networks
Airline Route Design: Hub-and-spoke vs. point-to-point networks

2. Computer Science Applications

Applications:

Internet Structure: Routing tables and packet forwarding
Social Networks: Friend recommendation algorithms, community detection
Distributed Systems: Load balancing, fault tolerance

3. Business and Management

Applications:

Supply Chain: Optimizing logistics and reducing transportation costs
Organizational Charts: Reporting relationships and communication flows
Project Management: Critical path method for task scheduling

4. Biology and Medicine

Applications:

Food Webs: Predator-prey relationships and ecosystem balance
Disease Spread: Contact tracing and epidemic modeling
Neural Networks: Brain connectivity and information processing pathways

Important Terms

Term	Definition	Example
Graph	Set of vertices connected by edges	Network of cities connected by roads
Vertex	Point or node in a graph	City in a road network
Edge	Line connecting two vertices	Road between two cities
Degree	Number of edges connected to a vertex	Number of roads connected to a city
Directed Graph	Graph with edges having direction	One-way streets, Twitter follows
Undirected Graph	Graph with bidirectional edges	Friendship networks, two-way roads
Weighted Graph	Graph with numerical values on edges	Road distances, connection costs
Unweighted Graph	Graph without numerical values	Simple friendship networks
Subgraph	Subset of a graph	Partial network of selected cities
Tree	Connected graph with no cycles	Network without redundant connections

Summary Points

Graph = (Vertices, Edges)
Sum of Degrees = 2 × Number of Edges
Directed: One-way connections
Undirected: Two-way connections
Weighted: Connections have values (distance, cost, etc.)
Unweighted: Connections are present/absent
Tree: Connected, no cycles, n vertices → n-1 edges
Applications: Transportation, computer networks, social networks

Practice Tips for SPM Students

1. Visual Learning

Draw graphs for different scenarios
Practice identifying vertices and edges
Learn to recognize different graph types

2. Problem-Solving Strategies

Start by identifying vertices and edges
Determine if the graph should be directed or undirected
Decide if weights are needed for the application
Look for patterns in degrees and connections

3. Common Applications to Practice

Shortest path problems (maps, distances)
Network connectivity problems
Spanning tree applications (minimum connections)
Degree sequence problems

4. Common Mistakes to Avoid

Confusing directed and undirected graphs
Forgetting that weighted graphs need numerical values
Misidentifying cycles in graphs
Incorrectly calculating degrees

SPM Exam Tips

Paper 1 (Multiple Choice)

Look for keywords indicating direction (one-way, follows, points to)
Identify weighted vs. unweighted based on numerical values
Remember tree properties (no cycles, n-1 edges for n vertices)
Use the sum of degrees formula for verification

Paper 2 (Structured)

Clearly label all vertices and edges
Show your method for finding optimal paths
Explain why a graph is or is not a tree
Use real-world context to explain your answer

Did You Know? The Seven Bridges of Königsberg problem, solved by Euler in 1736, is considered the birth of graph theory. The problem asked whether it was possible to walk through the city crossing each of its seven bridges exactly once!

Next Chapter: In Chapter 6, you'll explore linear inequalities in two variables and learn to graph and solve systems of inequalities, which is essential for optimization problems and real-world constraint analysis.