By the end of this chapter, you will be able to:
These skills will help you analyze and solve complex problems efficiently, making you a valuable asset in any technical field.
Graph theory is a fundamental area of discrete mathematics with wide applications across various professional fields in Kenya. It provides tools for modelling relationships and networks, essential in sectors such as healthcare for patient referrals, county government for resource allocation, banking for transaction networks, and retail for supply chain management. Understanding graph theory enables professionals to analyse complex systems, identify critical connections, and optimise operations efficiently.
The foundation of graph theory lies in understanding its basic elements. In professional contexts like managing networks within a county referral hospital or structuring information flow in a university, precise knowledge of graph components such as nodes, edges, vertices, and adjacency is crucial. These terms describe the structure and connectivity of graphs, which model relationships between entities.
A node represents a fundamental unit or point in a graph where connections converge. In practical terms, a node can represent entities such as departments in a county government office, computers in a retail business network, or patients in a hospital referral system. Nodes serve as the anchors for relationships modelled by graphs.
$$\text{Node} = \text{A distinct point representing an entity in a graph}$$
Example 1: In a county referral hospital, there are 7 departments represented as nodes in a network graph. Calculate the total number of nodes.
Given: Number of departments \(n = 7\)
$$\text{Total nodes} = n$$
$$= 7$$
Answer: 7 \text{ nodes}
Example 2: A retail business has 12 stores represented as nodes. If 3 new stores open, how many nodes will the graph have?
Given: Initial nodes \(n = 12\), new nodes \(m = 3\)
$$\text{Total nodes} = n + m$$
$$= 12 + 3$$
$$= 15$$
Answer: 15 \text{ nodes}
Example 3: A SACCO has 20 branches represented as nodes. 5 branches close down. What is the new number of nodes?
Given: Initial nodes \(n = 20\), closed nodes \(c = 5\)
$$\text{Remaining nodes} = n, c$$
$$= 20 - 5$$
$$= 15$$
Answer: 15 \text{ nodes}
An edge is a connection or link between two nodes in a graph, representing a relationship or pathway. In a university campus, edges could represent pathways between buildings; in a bank, they may represent transaction routes between branches. Edges can be directed or undirected depending on the nature of the relationship.
$$\text{Edge} = \text{A connection linking two nodes in a graph}$$
Example 1: In a county government office network, 5 nodes are connected such that each node is linked to every other node by an edge. Calculate the total number of edges for an undirected graph.
Given: Number of nodes \(n = 5\)
$$\text{Total edges} = \frac{n(n-1)}{2}$$
$$= \frac{5 \times (5-1)}{2}$$
$$= \frac{5 \times 4}{2}$$
$$= \frac{20}{2}$$
Answer: 10 \text{ edges}
Example 2: A hotel chain has 6 branches connected by roads represented as edges in a graph. If the roads are two-way (undirected), find the number of edges if each branch is connected to 3 others.
Given: Number of nodes \(n = 6\), degree per node \(d = 3\)
$$\text{Total edges} = \frac{n \times d}{2}$$
$$= \frac{6 \times 3}{2}$$
$$= \frac{18}{2}$$
Answer: 9 \text{ edges}
Example 3: In a directed graph representing email communication between 4 departments in a university, each department sends emails to every other department. Calculate the number of edges.
Given: Number of nodes \(n = 4\)
$$\text{Total edges} = n(n-1)$$
$$= 4 \times (4-1)$$
$$= 4 \times 3$$
Answer: 12 \text{ edges}
The terms vertex and node are often used interchangeably in graph theory. A vertex is a point where edges meet, representing entities or locations. In a farm cooperative network, vertices can represent individual farms connected by trade routes (edges). Recognising vertices helps in visualising and analysing network structures.
$$\text{Vertex} = \text{A point in a graph representing an entity, equivalent to a node}$$
Example 1: A cooperative has 8 members represented as vertices in a graph. What is the total number of vertices?
Given: Number of members \(v = 8\)
$$\text{Total vertices} = v$$
$$= 8$$
Answer: 8 \text{ vertices}
Example 2: In a county referral hospital, 10 clinical units are vertices in a graph. If 2 new units are added, how many vertices are there?
Given: Initial vertices \(v = 10\), new vertices \(n = 2\)
$$\text{Total vertices} = v + n$$
$$= 10 + 2$$
$$= 12$$
Answer: 12 \text{ vertices}
Example 3: A retail business network has 15 vertices representing outlets. If 4 outlets are closed, find the remaining vertices.
Given: Initial vertices \(v = 15\), closed vertices \(c = 4\)
$$\text{Remaining vertices} = v, c$$
$$= 15 - 4$$
$$= 11$$
Answer: 11 \text{ vertices}
Two vertices are adjacent if they are connected directly by an edge. Adjacency indicates immediate connection or relationship. For example, in a county government office network, adjacent vertices might represent departments that share resources or communicate directly. Understanding adjacency is key in network traversal and optimisation.
$$\text{Adjacency} = \text{Two vertices connected directly by an edge}$$
Example 1: In a graph representing 6 branches of a bank, vertex \(A\) is connected to vertices \(B\) and \(C\). Identify the vertices adjacent to \(A\).
Given: Vertex \(A\) connected to \(B, C\)
Adjacency: Vertices adjacent to \(A\) are \(B, C\)
Answer: B \text{ and } C \text{ are adjacent to } A
Example 2: A university network graph has vertices \(X, Y, Z\), where \(X\) is connected to \(Y\) but not to \(Z\). Which vertices are adjacent to \(X\)?
Given: \(X\) connected to \(Y\), not connected to \(Z\)
Adjacency: Vertex \(Y\) is adjacent to \(X\), vertex \(Z\) is not
Answer: Y \text{ is adjacent to } X; Z \text{ is not adjacent to } X
Example 3: In a retail supply chain graph, store \(M\) is adjacent to stores \(N\) and \(O\). Store \(N\) is adjacent to \(M\) and \(P\). List all vertices adjacent to \(N\).
Given: \(N\) connected to \(M, P\)
Adjacency: Vertices adjacent to \(N\) are \(M, P\)
Answer: M \text{ and } P \text{ are adjacent to } N
A county government office network has 8 departments represented as nodes. Calculate the total number of nodes. (2 marks)
In a SACCO network graph with 7 nodes where each node is connected to every other node by an undirected edge, find the total number of edges. (3 marks)
A hotel chain has 5 branches connected in a directed graph where each branch sends information to every other branch. Calculate the total number of edges. (3 marks)
A retail business graph has 10 vertices. If 4 vertices are removed, what is the new number of vertices? (2 marks)
In a university network graph, vertex \(P\) is connected directly to vertices \(Q\) and \(R\). Identify the vertices adjacent to \(P\). (2 marks)
Create a free account to open more of this chapter.
Free: practical guides, quick cards, workplace scenarios and more.
Create a free accountThis chapter introduced fundamental concepts in graph theory, starting with key terminologies such as nodes, edges, vertices, and adjacency, which form the basis for understanding graph structures. It then explored various types of graphs including null graphs, simple graphs, multigraphs, directed graphs, and undirected graphs, highlighting their distinct characteristics. The chapter detailed methods for representing graphs through adjacency matrices, adjacency lists, and incidence matrices, explaining how each format captures graph information differently. Practical applications of graphs were examined in several real-world contexts such as computer networks, social networks, transport systems, and scheduling tasks. Through these topics, the chapter provided a comprehensive overview of how graph theory models relationships and connections in diverse fields. Understanding these concepts equips students with essential tools for analyzing and solving problems involving discrete structures.
A county referral hospital has 4 departments represented as nodes in a graph. Each department is connected to every other department by a single corridor. How many edges does this graph have? (2 marks)
A retail business has a network of 5 stores connected by direct delivery routes. If each route is bidirectional and there are no multiple routes between the same two stores, calculate the total number of edges. (3 marks)
At the start of this chapter we promised you would be able to:
Tick each one you can genuinely do.
So, are you there yet?
You're competent when you can confidently do 50% or more of what this chapter promised.
Sign in to record how you're doing.