8/11/26, 11:13 AM Course Outline Generation

CHAPTER SIX: GRAPH THEORY, TREES AND COMPUTATIONAL NETWORKS

Programmes: Bachelor of Science in Software Engineering (BSWE) / Bachelor of Computer Science
(BCS)
Lecturer: Dr. Engr. Tuhame William
Level: Bachelor’s Degree

6.0 INTRODUCTION
Graph theory is an important branch of discrete mathematics concerned with the mathematical
representation and analysis of relationships, connections, networks, and structures.

A graph can be used to represent:

Computer networks
Social networks
Road networks
Communication systems
Web pages and hyperlinks
Software dependencies
Database relationships
Transportation systems
Electrical networks
Network routing
For example, a computer network can be represented using vertices to represent computers or
routers and edges to represent communication links.

Graph theory provides the mathematical foundation for many computing techniques, including:

Network routing
Shortest-path algorithms
Search algorithms
Network optimization
Web crawling
Recommendation systems
Social network analysis
Minimum spanning trees
Scheduling
Artificial intelligence
A particularly important type of graph is a tree. Trees are widely used in computer science for
representing hierarchical relationships and organizing information.

Examples include:

File systems
[Link] 1/31
8/11/26, 11:13 AM Course Outline Generation

Decision trees
Binary search trees
Syntax trees
Database indexes
Network structures

6.1 CHAPTER LEARNING OBJECTIVES

By the end of this chapter, students should be able to:
1. Define graph theory and explain its importance in computing.
2. Identify vertices, edges, degree, paths and cycles in graphs.
3. Distinguish between directed and undirected graphs.
4. Represent graphs using adjacency matrices and adjacency lists.
5. Explain graph connectivity and traversal.
6. Apply shortest-path concepts to computational problems.
7. Define trees and identify their important properties.
8. Explain spanning trees and minimum spanning trees.
9. Apply graph algorithms such as BFS and DFS.
10. Explain practical applications of graphs and trees in software engineering and computer
science.

6.2 MEANING OF GRAPH THEORY

Graph theory is the study of mathematical structures used to represent relationships between
objects.

A graph is generally represented as:

G = (V , E)
where:
G = graph
V = set of vertices
E = set of edges
For example:

V = {A, B, C, D}
and:

E = {{A, B}, {A, C}, {B, D}, {C, D}}

This represents four objects connected by four relationships.

[Link] 2/31
8/11/26, 11:13 AM Course Outline Generation

6.3 BASIC COMPONENTS OF A GRAPH

A graph has two fundamental components:

1. Vertices
A vertex is an individual object or point in a graph.

Vertices may represent:

Computers
People
Cities
Routers
Web pages
Software modules
Vertices are also called nodes.

2. Edges
An edge represents a relationship or connection between two vertices.

For example:

A−B

means that vertex A is connected to vertex B .

6.4 SIMPLE GRAPH EXAMPLE

Consider:

V = {A, B, C, D}

and:

E = {AB, AC, BD, CD}

The structure can be visualized conceptually as:

A
/ \
B C
\ /
D

The vertices are:

[Link] 3/31
8/11/26, 11:13 AM Course Outline Generation

A, B, C, D
The edges are:

AB, AC, BD, CD

6.5 TYPES OF GRAPHS

Several types of graphs are commonly used in computer science.

The most important include:

1. Undirected graphs
2. Directed graphs
3. Weighted graphs
4. Unweighted graphs
5. Simple graphs
6. Complete graphs

6.6 UNDIRECTED GRAPHS

An undirected graph is a graph in which edges do not have a direction.

If:

A−B

then A is connected to B , and B is connected to A.

Mathematically:

AB = BA

Example
A friendship network can be represented as an undirected graph because friendship is generally
considered a mutual relationship.

If:

John is connected to Mary,

then Mary is also connected to John.

6.7 DIRECTED GRAPHS

[Link] 4/31
8/11/26, 11:13 AM Course Outline Generation

A directed graph, or digraph, contains edges with directions.

An edge may be represented as:

A→B

This means that there is a directed relationship from A to B .

However:

A→B

does not necessarily imply:

B→A

Applications
Directed graphs are useful for representing:
Website links
Social media following
One-way roads
Task dependencies
Data flow
Software dependencies

6.8 WEIGHTED GRAPHS

A weighted graph assigns a numerical value to each edge.

For example:
5
A ​
B

means that the connection between A and B has a weight of 5.

The weight may represent:

Distance
Cost
Time
Bandwidth
Energy consumption
Network latency

Example
Suppose:

[Link] 5/31
8/11/26, 11:13 AM Course Outline Generation

A − B = 10 km

B − C = 15 km
The graph can represent distances between locations.

6.9 UNWEIGHTED GRAPHS

An unweighted graph treats all edges as having equal importance or cost.

For example:

A−B−C −D

may represent a network where each connection is treated equally.

Unweighted graphs are commonly used when the existence of a relationship is more important
than its cost.

6.10 SIMPLE GRAPHS

A simple graph is a graph that:
Has no loops.
Has no multiple edges between the same pair of vertices.
A loop occurs when an edge connects a vertex to itself:

A→A
A simple graph does not contain such an edge.

6.11 COMPLETE GRAPH

A complete graph is a graph in which every pair of distinct vertices is connected by an edge.

A complete graph with n vertices is denoted:

Kn ​

The number of edges in a complete graph is:

n(n − 1)
2
​ ​

Worked Example 1
[Link] 6/31
8/11/26, 11:13 AM Course Outline Generation

Find the number of edges in:

K5 ​

Solution

n(n − 1)
E=
2
​

Substitute:

5(5 − 1)
E=
2
​

5(4)
=
2
​

= 10
Therefore:

K5 has 10 edges
​ ​

6.12 DEGREE OF A VERTEX

The degree of a vertex is the number of edges incident to that vertex.

It is commonly represented by:

deg(v)
Consider:

B
|
A------C------D
|
E

Vertex C has four edges connected to it.

Therefore:

deg(C) = 4

Vertex A has:

deg(A) = 1

[Link] 7/31
8/11/26, 11:13 AM Course Outline Generation

6.13 DEGREE IN DIRECTED GRAPHS

In directed graphs, degree is divided into:

In-degree
The number of edges entering a vertex.

Represented as:

deg− (v)

Out-degree
The number of edges leaving a vertex.

Represented as:

deg+ (v)

Worked Example 2
Consider:

A→B

C→B

B→D

For vertex B :

Incoming edges:

A→B

and:

C→B
Therefore:

deg− (B) = 2
Outgoing edges:

B→D
Therefore:

deg+ (B) = 1

[Link] 8/31
8/11/26, 11:13 AM Course Outline Generation

6.14 HANDSHAKING LEMMA

For an undirected graph:

∑ deg(v) = 2∣E∣
​ ​

v∈V

This means that the sum of all vertex degrees is twice the number of edges.

Each edge contributes two to the total degree because it connects two vertices.

Worked Example 3
Consider a graph with 5 edges.

What is the sum of the degrees of all vertices?

Using:

∑ deg(v) = 2∣E∣

we obtain:

2(5) = 10
Therefore:

10 ​

6.15 PATHS
A path is a sequence of vertices connected by edges.

For example:

A−B−C −D

is a path from A to D .

The length of the path is the number of edges.

Therefore:

A−B−C −D

has:

3
[Link] 9/31
8/11/26, 11:13 AM Course Outline Generation

edges.

Hence:

Path length = 3 ​

6.16 WALK
A walk is a sequence of vertices and edges in which vertices or edges may be repeated.

For example:

A−B−C −B−D

is a walk because B occurs more than once.

6.17 TRAIL
A trail is a walk in which no edge is repeated.

Vertices may still be repeated.

6.18 PATH VERSUS WALK VERSUS TRAIL

Structure Repeated vertices? Repeated edges?

Walk Allowed Allowed

Trail Allowed Not allowed

Path Usually not allowed Not allowed

Understanding these concepts is useful when analysing network routes.

6.19 CYCLES
A cycle is a path that begins and ends at the same vertex without repeating intermediate vertices.

For example:

A−B−C −A
forms a cycle.

[Link] 10/31
8/11/26, 11:13 AM Course Outline Generation

Cycles are important in computing because they may represent:

Circular dependencies
Network loops
Deadlocks
Routing loops
Dependency cycles

6.20 CONNECTED GRAPHS

A graph is connected if there is a path between every pair of vertices.

For example:

A---B---C
|
D

Every vertex can be reached from every other vertex.

Therefore, the graph is connected.

6.21 DISCONNECTED GRAPHS

A graph is disconnected if at least one pair of vertices has no path connecting them.

Example:

A---B C---D

There is no path from A to C .

Therefore, the graph is disconnected.

6.22 GRAPH REPRESENTATION

Graphs can be represented in computer programs using different data structures.

Two important representations are:

1. Adjacency matrix
2. Adjacency list

[Link] 11/31
8/11/26, 11:13 AM Course Outline Generation

6.23 ADJACENCY MATRIX

An adjacency matrix is a square matrix used to represent connections between vertices.

Suppose:

V = {A, B, C}
and edges are:

AB, AC
The adjacency matrix is:

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

C 1 0 0

A value of:

means an edge exists.

A value of:

0
means no edge exists.

6.24 ADVANTAGES OF ADJACENCY MATRICES

Advantages include:
Simple representation.
Easy to determine whether an edge exists.
Efficient for dense graphs.
Easy mathematical manipulation.

Disadvantages
Requires:

O(V 2 )
memory.
Can waste memory for sparse graphs.

[Link] 12/31
8/11/26, 11:13 AM Course Outline Generation

6.25 ADJACENCY LIST

An adjacency list stores the neighbours of each vertex.

For:

A − B, A − C
the adjacency list is:

A → B, C
B → A
C → A

Adjacency lists are particularly efficient for sparse graphs.

6.26 MATRIX VERSUS LIST

Feature Adjacency Matrix Adjacency List

Memory O(V 2 ) O(V + E)

Edge lookup Very fast May require search

Sparse graphs Less efficient More efficient

Dense graphs Suitable Can use more overhead

Implementation Simple Relatively flexible

6.27 GRAPH TRAVERSAL

Graph traversal refers to systematically visiting vertices in a graph.

Two major traversal algorithms are:

1. Breadth-First Search (BFS)

2. Depth-First Search (DFS)
These algorithms are fundamental in computer science.

6.28 BREADTH-FIRST SEARCH

Breadth-First Search (BFS) explores a graph level by level.

[Link] 13/31
8/11/26, 11:13 AM Course Outline Generation

It typically uses a:

Queue ​

data structure.

Suppose:

A
/ \
B C
/ \
D E

Starting at A, BFS visits:

A, B, C, D, E

The algorithm first visits A, then its immediate neighbours, then the next level.

6.29 BASIC BFS ALGORITHM

A simplified BFS procedure is:

BFS(Graph, start):
create an empty queue
mark start as visited
add start to queue

while queue is not empty:

remove a vertex from queue
process the vertex

for each unvisited neighbour:

mark neighbour as visited
add neighbour to queue

6.30 APPLICATIONS OF BFS

BFS is useful for:
Finding shortest paths in unweighted graphs.
Network broadcasting.
Web crawling.
Social network analysis.
Finding connected components.

[Link] 14/31
8/11/26, 11:13 AM Course Outline Generation

Level-order traversal of trees.

6.31 DEPTH-FIRST SEARCH

Depth-First Search (DFS) explores as deeply as possible before backtracking.

DFS can use:

A stack, or
Recursion.
For example:

A
/ \
B C
/ \
D E

A possible DFS traversal is:

A, B, D, E, C
The exact traversal can depend on the order in which neighbours are processed.

6.32 BASIC DFS ALGORITHM

DFS(vertex):
mark vertex as visited
process vertex

for each unvisited neighbour:

DFS(neighbour)

6.33 APPLICATIONS OF DFS

DFS is commonly used for:
Detecting cycles.
Topological sorting.
Maze solving.
Finding connected components.
Exploring file systems.
Dependency analysis.

[Link] 15/31
8/11/26, 11:13 AM Course Outline Generation

Searching state spaces.

6.34 BFS VERSUS DFS

Feature BFS DFS

Main structure Queue Stack/recursion

Exploration Level by level Depth first

Shortest path in unweighted Yes Not guaranteed

graph

Memory Can be high Often lower

Cycle detection Yes Yes

Common application Shortest paths Dependency/cycle analysis

6.35 SHORTEST PATH

The shortest-path problem involves finding the minimum-cost path between two vertices.

For an unweighted graph, BFS can be used to find the shortest path.

For a weighted graph with non-negative edge weights, Dijkstra's algorithm is commonly used.

6.36 DIJKSTRA'S ALGORITHM

Dijkstra's algorithm determines the shortest paths from a source vertex to other vertices in a
weighted graph when edge weights are non-negative.

The basic idea is:

1. Assign distance 0 to the source.

2. Assign infinity to all other vertices.
3. Select the unvisited vertex with the smallest known distance.
4. Update distances to its neighbours.
5. Mark the vertex as visited.
6. Repeat until all relevant vertices are processed.

[Link] 16/31
8/11/26, 11:13 AM Course Outline Generation

6.37 WORKED EXAMPLE 4: SHORTEST PATH

Suppose the following network exists:

A --2-- B --3-- D
\ /
5 1
\ /
C

Suppose we want the shortest path from A to D .

Possible routes include:

A−B−D
with cost:

2+3=5

Another route:

A−C −B−D
has cost:

5+1+3=9
Therefore:

A−B−D ​

is the shortest route with total cost:

5 ​

6.38 TREES
A tree is a connected undirected graph that contains no cycles.

Trees are among the most important structures in computer science.

A tree with n vertices always contains:

n−1 ​

edges.

[Link] 17/31
8/11/26, 11:13 AM Course Outline Generation

6.39 PROPERTIES OF TREES

A tree has several important properties:
1. It is connected.
2. It contains no cycles.
3. There is exactly one simple path between any two vertices.
4. A tree with n vertices has n − 1 edges.
5. Removing any edge disconnects the tree.
6. Adding one additional edge creates a cycle.

6.40 WORKED EXAMPLE 5

A tree contains 12 vertices.

How many edges does it have?

Using:

E =V −1
we obtain:

E = 12 − 1

E = 11
Therefore:

11 edges ​

6.41 ROOTED TREES

A rooted tree is a tree in which one vertex is designated as the root.

Example:

A
/ | \
B C D
/ \
E F

Here:

A
is the root.
[Link] 18/31
8/11/26, 11:13 AM Course Outline Generation

6.42 TREE TERMINOLOGY

Important terms include:

Root
The topmost or starting vertex.

Parent
A vertex directly above another vertex.

Child
A vertex directly below another vertex.

Leaf
A vertex with no children.

Internal Vertex
A vertex with at least one child.

Sibling
Vertices having the same parent.

6.43 LEVEL OF A NODE

The level of a node refers to its distance from the root.

For example:

A Level 0
/ \
B C Level 1
/ \
D E Level 2

Therefore:

A=0

B, C = 1

D, E = 2

6.44 HEIGHT OF A TREE

[Link] 19/31
8/11/26, 11:13 AM Course Outline Generation

The height of a tree is the length of the longest path from the root to a leaf.

For the previous tree:

A−B−D
has two edges.

Therefore:

Height = 2 ​

under the edge-counting convention.

6.45 BINARY TREES

A binary tree is a tree in which each node has at most two children.

The two children are commonly called:

Left child
Right child
Example:

10
/ \
5 15
/ \ / \
2 7 12 20

Binary trees are widely used in:

Searching
Sorting
Expression processing
Databases
Compilers
Artificial intelligence

6.46 BINARY SEARCH TREE

A Binary Search Tree (BST) is a binary tree satisfying:

Left subtree < Root < Right subtree

For example:

[Link] 20/31
8/11/26, 11:13 AM Course Outline Generation

50
/ \
30 70
/ \ / \
20 40 60 80

Searching for 60 involves comparing:

60 > 50
so move right.

Then:

60 < 70
so move left.

We find:

60

6.47 SPANNING TREE

A spanning tree of a connected graph is a subgraph that:
1. Contains all vertices.
2. Is connected.
3. Contains no cycles.
If a graph contains n vertices, its spanning tree contains:

n−1
edges.

6.48 MINIMUM SPANNING TREE

A Minimum Spanning Tree (MST) is a spanning tree whose total edge weight is as small as
possible.

MSTs are useful in:

Network design
Telecommunications
Road construction
Electrical networks
Cable installation

[Link] 21/31
8/11/26, 11:13 AM Course Outline Generation

Infrastructure planning
Two common MST algorithms are:
Kruskal's algorithm
Prim's algorithm

6.49 KRUSKAL'S ALGORITHM

Kruskal's algorithm works by:
1. Sorting all edges by weight.
2. Selecting the smallest edge.
3. Adding it if it does not create a cycle.
4. Continuing until all vertices are connected.

6.50 PRIM'S ALGORITHM

Prim's algorithm:
1. Starts with a selected vertex.
2. Selects the smallest edge connecting the current tree to a new vertex.
3. Continues until all vertices are included.

6.51 WORKED EXAMPLE 6: MINIMUM SPANNING TREE

Consider a network with edges:

AB = 2

AC = 4

BC = 1

BD = 5

CD = 3
Using Kruskal's method, arrange the edges from smallest to largest:

BC = 1

AB = 2

CD = 3

AC = 4

[Link] 22/31
8/11/26, 11:13 AM Course Outline Generation

BD = 5
Select:

BC
then:

AB

then:

CD
At this point all four vertices are connected.

Total cost:

1+2+3=6
Therefore, the minimum spanning tree has total weight:

6 ​

6.52 GRAPH THEORY IN SOFTWARE ENGINEERING

Graph theory has numerous applications in software engineering.

6.52.1 Software Dependency Graphs

Software modules can be represented as vertices, while dependencies can be represented as
directed edges.

For example:

A→B
may mean:

Module A depends on Module B.

6.52.2 Version Control

Dependencies between software components can be modelled using graphs.

This helps developers understand:

Dependency relationships
Build order

[Link] 23/31
8/11/26, 11:13 AM Course Outline Generation

Conflicting dependencies
Circular dependencies

6.52.3 Compiler Design

Compilers use tree structures such as:
Parse trees
Abstract syntax trees
Expression trees
to represent program structure.

6.53 GRAPH THEORY IN COMPUTER NETWORKS

Computer networks can be modelled as graphs.

For example:

Routers → vertices
Communication links → edges
Transmission cost → edge weights
Graph algorithms can then determine:
Shortest routes
Network connectivity
Redundant links
Minimum-cost infrastructure
Network failures

6.54 GRAPH THEORY IN SOCIAL NETWORKS

A social network can be represented as a graph.

For example:

Users → vertices
Friendships → edges
Directed graphs can represent following relationships:

A→B
meaning:

A follows B.

Graph analysis can identify:

[Link] 24/31
8/11/26, 11:13 AM Course Outline Generation

Influential users
Communities
Connections
Degrees of separation
Recommendation relationships

6.55 GRAPH THEORY IN DATABASE SYSTEMS

Database relationships can also be modelled using graphs.

For example:

Student → Enrolment → Course

Graph-based models are especially useful where data contains many interconnected relationships.

6.56 GRAPH THEORY IN ARTIFICIAL INTELLIGENCE

Graphs are used in AI for representing:
Knowledge
Search spaces
State transitions
Decision structures
Relationships between entities
For example, a search problem can be represented as:

Initial State → Possible States → Goal State

Algorithms such as BFS and DFS can then explore the state space.

6.57 INTEGRATED WORKED EXAMPLE 7: COMPUTER NETWORK

Suppose a university network contains five routers:

R1 , R2 , R3 , R4 , R5
​ ​ ​ ​ ​

with connections:

R1 − R2
​ ​

R1 − R3
​ ​

R2 − R4
​ ​

[Link] 25/31
8/11/26, 11:13 AM Course Outline Generation

R3 − R4
​ ​

R4 − R5
​ ​

Questions
1. How many vertices are present?
2. How many edges are present?
3. Is the graph connected?
4. Give one path from R1 to R5 . ​ ​

Solution

1. Number of vertices

5 ​

2. Number of edges
There are:

5 ​

edges.

3. Connectivity
Every router can be reached from every other router.

Therefore, the graph is:

Connected ​

4. Example path

R1 − R2 − R4 − R5
​ ​ ​ ​

Therefore:

R1 → R2 → R4 → R5
​ ​ ​ ​ ​

is one valid path.

6.58 CLASSROOM ACTIVITIES

Activity 1: Build a Social Network Graph
Students should form groups of five.

Represent:

[Link] 26/31
8/11/26, 11:13 AM Course Outline Generation

Students as vertices.
Friendships as edges.
Tasks:
1. Draw the graph.
2. Determine the degree of each student.
3. Identify the student with the highest degree.
4. Determine whether the graph is connected.
5. Identify any cycles.

Activity 2: University Network

Design a graph representing a university computer network containing:
3 routers
5 computers
2 servers
Students should:
1. Identify vertices.
2. Identify edges.
3. Assign weights representing network distances.
4. Find a possible shortest route.
5. Explain how graph theory helps network administrators.

6.59 ASSIGNMENT TASKS — CHAPTER SIX

Assignment 1: Graph Fundamentals
Answer the following:
1. Define graph theory.
2. Define a vertex.
3. Define an edge.
4. Explain directed graphs.
5. Explain undirected graphs.
6. Explain weighted graphs.
7. Define degree.
8. Define a path.
9. Define a cycle.
10. Explain graph connectivity.

Assignment 2: Graph Representation

[Link] 27/31
8/11/26, 11:13 AM Course Outline Generation

Given:

V = {A, B, C, D, E}
and:

E = {AB, AC, BD, CE, DE}

students should:
1. Draw the graph.
2. Determine the degree of every vertex.
3. Construct the adjacency matrix.
4. Construct the adjacency list.
5. Determine whether the graph is connected.
6. Identify one path from A to E .

Assignment 3: Graph Algorithms

Explain and demonstrate:
1. Breadth-First Search.
2. Depth-First Search.
3. Dijkstra's algorithm.
4. Kruskal's algorithm.
5. Prim's algorithm.
For each algorithm:
Explain its purpose.
Give the basic steps.
State its major application.
Provide a small worked example.

Assignment 4: Trees
Answer the following:
1. Define a tree.
2. State five properties of trees.
3. Explain rooted trees.
4. Define a leaf node.
5. Define a parent and child.
6. Explain binary trees.
7. Explain binary search trees.
8. A tree contains 25 vertices. How many edges does it contain?
9. Explain why trees cannot contain cycles.
[Link] 28/31
8/11/26, 11:13 AM Course Outline Generation

10. Give five applications of trees in computing.

Assignment 5: Minimum Spanning Tree

Consider a weighted graph with edges:

AB = 4, AC = 2, BC = 1

BD = 5, CD = 8, CE = 10

DE = 2

Tasks:
1. Draw the graph.
2. Apply Kruskal's algorithm.
3. Determine the minimum spanning tree.
4. Calculate the total weight.
5. Explain a practical application of MST in computer networking.

Assignment 6: Software Engineering Application

Consider a software system containing the following modules:
User Interface
Authentication
Database
Payment
Reporting
Assume that:
User Interface depends on Authentication.
Authentication depends on Database.
Payment depends on Database.
Reporting depends on Database.
Tasks:
1. Represent the dependencies using a directed graph.
2. Identify the vertices.
3. Identify the directed edges.
4. Determine whether the dependency graph contains a cycle.
5. Explain how graph theory can help software engineers manage dependencies.

6.60 EXAM-STYLE QUESTIONS

[Link] 29/31
8/11/26, 11:13 AM Course Outline Generation

Question 1
Define graph theory and explain five applications of graph theory in computer science.

Question 2
Given a graph containing 8 vertices and 12 edges:

a) Explain the meaning of vertex and edge.

b) Calculate the sum of the degrees of all vertices.
c) Explain whether the graph must necessarily be connected.
d) Discuss the importance of graph connectivity.

Question 3
Differentiate between:

a) Directed and undirected graphs.

b) Weighted and unweighted graphs.
c) BFS and DFS.
d) Path and cycle.

Question 4
A university has six departments connected through a computer network. The network connections
have different costs.

Explain how Dijkstra's algorithm can be used to identify the shortest communication route between
two departments.

Question 5
A network contains 10 routers.

a) Explain what a spanning tree is.

b) Determine the number of edges in any spanning tree of this network.
c) Explain the purpose of a minimum spanning tree.
d) Compare Prim's and Kruskal's algorithms.

6.61 KEY FORMULAS

Graph Representation

[Link] 30/31
8/11/26, 11:13 AM Course Outline Generation

G = (V , E) ​

Complete Graph

n(n − 1)
∣E∣ =
2
​ ​

Handshaking Lemma

∑ deg(v) = 2∣E∣ ​

Tree

∣E∣ = ∣V ∣ − 1 ​

Generalized Pigeonhole Principle

N
⌈ ⌉
k
​ ​

6.62 CHAPTER SUMMARY

Graph theory provides mathematical tools for modelling relationships, connections and networks.
A graph consists primarily of vertices and edges and can be represented using adjacency matrices
or adjacency lists.

The major concepts covered in this chapter include:

Graphs → Vertices → Edges → Paths → Cycles → Connectivity → Trees → Graph A

 

Students should understand that graph theory is not simply an abstract mathematical topic. It is
directly applicable to real-world computing systems.

For example:

Computer Network → Graph Model → Shortest Path → Optimal Routing ​

Similarly:

Software Modules → Dependency Graph → Dependency Analysis → Reliable Softwar

 

The study of graphs therefore provides an essential foundation for software engineering,
computer science, networking, databases, artificial intelligence, algorithms and computational
mathematics.
[Link] 31/31