Graphs, Trees and Network Mathematics

Introduction and Context

Information technology systems are rarely isolated objects. Computers communicate through links, software modules depend on one another, users form social relationships, and data moves through interconnected services. Graph theory provides a mathematical language for representing and analysing these relationships.

A graph consists of entities, called vertices or nodes, and relationships between them, called edges or links. Graphs support problems such as:

• finding the shortest route through a network;
• determining whether all computers can communicate;
• identifying critical links or failure points;
• organising file systems and program syntax as trees;
• constructing efficient broadcast or cabling layouts; and
• analysing communities in social or information networks.

This chapter develops the essential mathematics of graphs, trees, paths, connectivity, traversal, spanning trees and network optimisation. The emphasis is on models that can be implemented in IT systems while recognising their assumptions and limitations.

Learning Objectives

By the end of this chapter, you should be able to:

1. define and classify graphs, vertices, edges, degrees, paths and cycles;
2. represent graphs using diagrams, adjacency matrices and adjacency lists;
3. analyse connectivity, routes and components;
4. explain and apply breadth-first search and depth-first search;
5. identify trees and construct spanning trees;
6. use shortest-path and minimum-spanning-tree ideas in network problems;
7. select an appropriate graph model for an IT application; and
8. evaluate practical, ethical and operational limitations of network models.

1. Fundamental Graph Concepts

A graph is commonly written as G = (V,E), where V is a finite set of vertices and E is a set of edges connecting pairs of vertices. In an undirected graph, an edge between A and B has no direction: the relationship A–B is the same as B–A. In a directed graph, or digraph, an edge is an ordered pair such as A → B; direction may represent data flow, dependency or a one-way web link.

A graph may be:

• simple, with no loops and no repeated edges;
• multigraph, allowing multiple edges between the same pair of vertices;
• weighted, with a numerical value on each edge, such as distance, cost, delay or risk;
• unweighted, where an edge indicates connection but carries no numerical weight;
• connected, when every pair of vertices is joined by at least one path; or
• disconnected, when at least one pair has no path between them.

A loop is an edge from a vertex to itself. The degree of a vertex in an undirected graph is the number of incident edges. A loop contributes two to the degree under the standard graph-theoretic convention, because it has two ends at the same vertex. In a directed graph, the in-degree counts incoming edges and the out-degree counts outgoing edges.

For an undirected graph,

where deg(v) is the degree of vertex v and |E| is the number of edges. This is the handshaking theorem. It applies to finite undirected multigraphs, including loops when a loop contributes two to degree. It follows because every edge contributes exactly two incidences. Consequently, the number of odd-degree vertices is always even.

A walk is a sequence of vertices and edges in which repetition is allowed. A trail does not repeat edges. A path does not repeat vertices. A closed walk begins and ends at the same vertex. A cycle is a closed path with no repeated vertices except the first and last. Terminology may vary slightly between textbooks, so definitions should be stated when precision is important.

The length of an unweighted path is its number of edges. In a weighted graph, its total weight is the sum of the weights of its edges:

Here P is a path, e ranges over its edges, and w(e) is the weight of edge e. The formula assumes that path cost is additive and that edge weights are comparable in the same units, such as milliseconds or kilometres.

2. Representing Graphs

Edge lists

An edge list stores each edge as a pair or ordered pair. For example, the undirected edges {A,B}, {A,C}, and {B,D} can be stored as (A,B), (A,C), (B,D). Edge lists are simple and useful when processing all edges, but finding all neighbours of one vertex may require scanning the whole list.

Adjacency lists

An adjacency list records the neighbours of each vertex.

For a sparse graph, an adjacency list usually requires storage proportional to |V| + |E|. For an undirected graph, each edge appears in two lists. Adjacency lists are generally appropriate for breadth-first search, depth-first search and large communication networks.

Adjacency matrices

An adjacency matrix is a square matrix A with one row and column per vertex. For an unweighted simple graph,

For a weighted graph, Aᵢⱼ may contain the edge weight, while a special value such as ∞ indicates no direct edge. In an undirected graph, Aᵢⱼ = Aⱼᵢ, so the matrix is symmetric. Matrix storage uses O(|V|²) space, making it attractive for dense graphs and constant-time edge-existence checks, but inefficient for very sparse graphs.

The number of walks of length k from vertex i to vertex j equals the (i,j) entry of A^k, for an unweighted graph represented in the usual arithmetic setting. This is a mathematically useful result, although computing matrix powers is not always the most efficient practical method for route search.

3. Connectivity, Components and Network Structure

Two vertices are connected if a path joins them. A graph is connected if every pair of vertices is connected. A connected component is a maximal connected subgraph. In a disconnected network, each component represents a group that can communicate internally but not with other groups under the modelled links.

A vertex whose removal increases the number of connected components is an articulation vertex or cut vertex. An edge whose removal disconnects a connected graph is a bridge or cut edge. These concepts help identify routers, servers or communication links whose failure creates major service disruption.

A graph is complete if every pair of distinct vertices is adjacent. The complete undirected graph with n vertices is denoted Kₙ and has

edges. This counts each unordered pair once. A bipartite graph has a vertex set that can be divided into two disjoint sets so that every edge joins vertices in different sets. Bipartite graphs model, for example, users and the systems they access. A graph is bipartite if and only if it contains no odd cycle.

A graph is planar if it can be drawn in the plane without edge crossings, except at vertices. Physical circuit layouts and some visual network diagrams may benefit from planarity analysis, although a network’s logical graph need not be planar.

4. Trees and Hierarchical Structures

A tree is a connected undirected graph with no cycles. If a tree has n vertices, it has exactly n − 1 edges. Equivalent characterisations for a finite undirected graph include:

• it is connected and acyclic;
• there is exactly one simple path between every pair of vertices; and
• it is connected with n − 1 edges.

A forest is an acyclic graph that may be disconnected; its components are trees.

A rooted tree chooses one vertex as the root. Every other vertex has a unique parent, and may have zero or more children. The depth of a vertex is the number of edges from the root. The height of a rooted tree is the greatest vertex depth. A node with no children is a leaf. File systems, XML documents, organisation charts, parse trees and menus are common IT examples.

In a binary tree, each node has at most two children, conventionally called left and right. A binary search tree maintains an ordering in which keys in the left subtree are smaller than the node’s key and keys in the right subtree are larger, subject to the chosen duplicate-key policy. A balanced search tree keeps height relatively small; an unbalanced tree may degrade toward a chain, making search closer to linear than logarithmic.

For a perfectly balanced binary tree with n nodes, search can be approximately logarithmic in n, because each comparison may eliminate about half the remaining search space. The exact performance depends on balance, implementation and operation. Big-O notation describes a growth bound, not an exact running time.

Tree traversal

Three standard depth-first traversals are:

• preorder: visit node, then left subtree, then right subtree;
• inorder: visit left subtree, node, then right subtree; and
• postorder: visit left subtree, right subtree, then node.

For a binary search tree, inorder traversal returns keys in sorted order, assuming the ordering invariant is maintained. Postorder is useful when deleting a tree or evaluating expression-tree subexpressions, because children are processed before their parent.

5. Searching and Traversal

Traversal systematically visits vertices and edges while recording which vertices have already been discovered. A visited set is essential in graphs containing cycles; without it, an algorithm could loop indefinitely.

Breadth-first search

Breadth-first search (BFS) begins at a source vertex and explores all vertices at distance 1, then distance 2, and so forth. It uses a queue. In an unweighted graph, the first time BFS discovers a vertex, it has found a shortest path in number of edges from the source.

A conceptual BFS procedure is:

1. place the source in a queue and mark it discovered;
2. remove the front vertex;
3. inspect each undiscovered neighbour, mark it, record its predecessor, and enqueue it;
4. repeat until the queue is empty.

With adjacency lists, BFS runs in O(|V| + |E|) time, because vertices and adjacency entries are processed a bounded number of times. Its space requirement is also O(|V| + |E|) including the graph representation, or O(|V|) additional working space in a typical implementation.

Depth-first search

Depth-first search (DFS) follows one route as far as possible before backtracking. It uses recursion or an explicit stack. DFS is useful for detecting cycles, finding connected components, producing topological-order information in directed acyclic graphs, and exploring maze-like structures. With adjacency lists, its time complexity is also O(|V| + |E|). DFS does not, in general, produce shortest paths in an unweighted graph.

Worked Example 1: BFS shortest route

Suppose an unweighted network has edges A–B, A–C, B–D, C–D, D–E and C–F. Starting at A, BFS discovers B and C at distance 1. From B it discovers D at distance 2; from C it discovers F at distance 2. From D it discovers E at distance 3. Therefore the shortest distance from A to E is 3 edges. One shortest route is A–B–D–E. A different neighbour-processing order could produce another shortest route of the same length, but cannot produce a shorter one.

6. Weighted Graphs and Shortest Paths

A weighted graph assigns a value to each edge. The value may represent time, monetary cost, physical distance, energy consumption or risk. A shortest-path problem seeks a path with minimum total weight between specified vertices.

Dijkstra’s algorithm

Dijkstra’s algorithm finds shortest paths from one source to all reachable vertices when every edge weight is non-negative. It maintains a tentative distance d(v), initially 0 for the source and ∞ for other vertices. Repeatedly, it selects the unsettled vertex with the smallest tentative distance and relaxes each outgoing edge. Relaxation replaces d(v) if travelling through the selected vertex is cheaper:

Here u and v are adjacent vertices and w(u,v) is the edge weight. The non-negative-weight condition is essential: negative edges can invalidate the algorithm’s settled-distance assumption. With a binary heap and adjacency lists, a common implementation has time complexity O((|V| + |E|) log |V|), though exact complexity depends on the priority-queue implementation.

If negative edge weights are possible, Bellman–Ford is a more suitable single-source method because it can detect reachable negative cycles, although it is generally slower. If a negative cycle is reachable, a finite shortest path may not exist because the route cost can be reduced indefinitely.

Worked Example 2: Dijkstra’s algorithm

Let the edges be A–B = 4, A–C = 2, B–C = 1, B–D = 5, C–D = 8 and C–E = 10, with all weights non-negative. Start at A.

Initial distances are d(A)=0 and d(B)=d(C)=d(D)=d(E)=∞. Relaxing A gives d(B)=4 and d(C)=2. Select C next, since 2 is smallest. Through C, B becomes min(4, 2+1)=3, D becomes 10, and E becomes 12. Select B with distance 3; through B, D becomes min(10, 3+5)=8. Select D with 8, then E remains 12. Thus the shortest distance from A to D is 8, through A–C–B–D; the shortest distance from A to E is 12, through A–C–E.

7. Spanning Trees and Network Optimisation

A spanning tree of a connected undirected graph is a subgraph that includes every vertex and is a tree. Therefore every spanning tree on n vertices has n − 1 edges. Removing any edge from a tree disconnects it; adding any extra edge creates a cycle.

Spanning trees are useful when a network requires a connected backbone without redundant links. In computer networks, a spanning-tree protocol can prevent forwarding loops in a physical topology that contains redundancy. In this operational context, redundancy may be retained physically but selectively disabled for forwarding.

A minimum spanning tree (MST) is a spanning tree with minimum total edge weight. The weight of a tree T is

An MST minimises the sum of selected link costs, not the distance between every pair of vertices and not necessarily the maximum delay. It is therefore different from a shortest-path tree.

Kruskal’s algorithm

Kruskal’s algorithm sorts edges by non-decreasing weight and repeatedly adds the next edge if it does not create a cycle. A disjoint-set data structure efficiently tests whether two endpoints are already in the same component. For a connected graph, the algorithm stops after n − 1 accepted edges.

Prim’s algorithm

Prim’s algorithm begins with one vertex and repeatedly adds the least-weight edge connecting the current tree to a vertex outside it. With appropriate priority-queue implementations it is efficient for many graph representations. Both Kruskal’s and Prim’s algorithms are correct because of the cut property: a minimum-weight edge crossing a cut is safe to include when it is strictly lighter than all alternatives, with tie cases potentially allowing multiple MSTs.

Worked Example 3: Minimum spanning tree

Consider vertices A, B, C and D with edges AB=1, AC=4, BC=2, BD=5 and CD=3. Kruskal’s algorithm orders them as AB=1, BC=2, CD=3, AC=4, BD=5. Add AB, BC and CD. These three edges connect all four vertices without a cycle, so the MST has total weight 1+2+3=6. Edge AC is rejected because it would create a cycle among A, B and C. Edge BD is unnecessary because all vertices are already connected.

8. A Detailed Applied Case: University Network Design

The following is an illustrative case, not a report of a particular institution.

Background

A university operates five buildings: Library (L), Science (S), Administration (A), Engineering (E) and Residence (R). Fibre links can be installed between selected buildings. The planning team wants every building connected while minimising installation cost.

Problem and data

Candidate links and costs, in thousands of currency units, are:

The cost is assumed additive, links are reliable enough for the planning horizon, and all candidate links are undirected. These assumptions should be tested before construction.

Analysis and solution

Kruskal’s algorithm orders the links by cost: E–R (1), S–A (2), L–A (3), L–S (4), S–E (5), A–E (6), A–R (7), S–R (8). Add E–R, S–A and L–A. The edge L–S is rejected because L and S are already connected through L–A–S. Add S–E, which connects the E–R component to the S–A–L component. Four edges now connect all five buildings, so the spanning tree is complete.

The total cost is 1+2+3+5 = 11 thousand currency units. The selected links are E–R, S–A, L–A and S–E. The result is cost-minimal among spanning trees under the stated weights.

Outcome and limitations

The design provides a connected backbone with no cycles. However, it has no link redundancy: failure of any selected link disconnects at least one part of the tree. A real design may deliberately pay more for resilience, capacity, security controls, diverse physical routes and low latency. Thus MST optimisation is a starting model, not an automatic final design.

Learning points

The case demonstrates the distinction between mathematical optimality and operational suitability. The objective function must reflect the actual decision: installation cost alone may be inadequate if downtime, congestion or safety is significant. A multi-criteria or constrained optimisation model may be more appropriate.

9. Network Models in IT Practice

Graphs support many IT applications:

• routing: routers are vertices and communication links are weighted edges;
• dependency analysis: software packages or services are vertices and dependency relations are directed edges;
• version control: commits form a directed acyclic graph in many workflows;
• databases: entity relationships and foreign-key connections can be represented as graphs;
• social networks: people or accounts are vertices, with follows, messages or collaborations as edges;
• cybersecurity: attack paths model movement between hosts, accounts and privileges;
• project planning: tasks and precedence relations form directed acyclic graphs; and
• knowledge graphs: entities and typed relationships support search and inference.

The meaning of a graph depends on its modelling choices. A social connection might be symmetric friendship, one-way following, or a weighted interaction frequency. A routing edge might represent physical connectivity, current availability or an average delay. Confusing these meanings can produce mathematically correct but operationally misleading conclusions.

10. Limitations, Governance and Contemporary Developments

Graph models simplify reality. Edge weights may be uncertain, time-dependent or correlated. A shortest route based on average delay may be poor during congestion. An apparently disconnected graph may be connected through an unrecorded wireless or administrative relationship. Large-scale graphs also create computational and storage challenges.

Graph data can contain personal information. Social, location and communication graphs may reveal relationships even when individual records are pseudonymised. Responsible practice requires data minimisation, access control, retention limits, lawful processing and evaluation of re-identification risk. Security teams should also recognise that graph analytics can expose attack paths and privileged accounts; such results must be protected.

Modern systems often use dynamic graphs, in which vertices, edges or weights change over time. Distributed systems use graph databases when relationship queries are central. Recommendation systems and fraud detection may use graph features, but models can reproduce social bias present in the data. AI-assisted graph analysis should therefore include validation, explainability appropriate to the risk, monitoring for drift and human review of high-impact decisions.

Best practice is to:

1. define precisely what vertices and edges mean;
2. record whether relationships are directed, weighted, temporal or probabilistic;
3. choose a representation suited to graph density and query patterns;
4. state algorithm assumptions, especially weight restrictions;
5. validate results against operational and domain knowledge;
6. test failure, attack and uncertainty scenarios; and
7. document privacy, governance and maintenance responsibilities.

Chapter Summary

Graphs model entities and relationships using vertices and edges. They may be directed or undirected, weighted or unweighted, simple or multigraphs. Degree measures local connection, while paths, cycles, components, bridges and articulation vertices describe structure and resilience. The handshaking theorem states that the sum of degrees in a finite undirected graph equals twice the number of edges.

Adjacency lists are efficient for sparse graphs, whereas adjacency matrices support rapid edge tests and suit dense graphs. Trees are connected acyclic graphs with n − 1 edges, making them fundamental for hierarchies, syntax structures and network backbones. BFS finds shortest paths by edge count in unweighted graphs; DFS supports systematic exploration and structural analysis. Dijkstra’s algorithm requires non-negative edge weights. Kruskal’s and Prim’s algorithms construct minimum spanning trees, which minimise total selected edge weight but do not automatically maximise resilience or minimise all pairwise distances.

Successful IT application depends on correct modelling. Costs, delay, reliability, privacy and security may require objectives beyond a simple graph algorithm. Graph analysis should therefore combine mathematical correctness with explicit assumptions, validation and responsible governance.

Key Terms

Vertex (node): An entity represented in a graph.

Edge: A relationship or connection between vertices.

Directed graph: A graph whose edges have orientation.

Weighted graph: A graph whose edges carry numerical values.

Degree: Number of incident edge ends at a vertex in an undirected graph.

Path: A sequence of vertices with no repeated vertices.

Cycle: A closed path with no repeated vertices except its first and last.

Connected graph: A graph in which every pair of vertices has a path between them.

Component: A maximal connected subgraph.

Bridge: An edge whose removal increases the number of components.

Tree: A connected undirected acyclic graph.

Rooted tree: A tree with one designated root vertex.

Leaf: A node with no children in a rooted tree.

Breadth-first search: A queue-based level-by-level graph traversal.

Depth-first search: A traversal that explores deeply before backtracking.

Shortest path: A minimum-weight path between specified vertices.

Spanning tree: A tree containing every vertex of a connected graph.

Minimum spanning tree: A spanning tree with minimum total edge weight.

Adjacency matrix: A matrix recording pairwise vertex adjacency or edge weight.

Adjacency list: A representation storing the neighbours of each vertex.

Review Questions

Short Answer Questions

1. What is the difference between a directed graph and an undirected graph?
2. State the handshaking theorem for a finite undirected graph.
3. Why does a tree with n vertices contain n − 1 edges?
4. What type of data structure does BFS use to manage discovered vertices?
5. State the edge-weight condition required by Dijkstra’s algorithm.

Long Answer Questions

1. Compare adjacency matrices and adjacency lists, including their storage characteristics and suitable applications.
2. Explain BFS and DFS, and compare their uses in IT systems.
3. Define a minimum spanning tree and distinguish it from a shortest-path tree.
4. Explain how bridges and articulation vertices can assist network resilience analysis.
5. Discuss why graph-modelling assumptions matter when designing an IT network.

Analytical / Application Questions

1. A network has edges A–B, A–C, B–D, C–D and D–E. Starting at A, use BFS to determine the shortest distance to E and give one shortest path.
2. Apply Kruskal’s algorithm to edges AB=2, AC=6, BC=3, BD=4 and CD=5. Identify an MST and calculate its total weight.
3. A software dependency graph contains a directed cycle. Explain why this may prevent a valid installation order and identify an appropriate graph-analysis approach.

Multiple Choice Questions with Answers

Question 1

For a finite undirected graph, what is the sum of all vertex degrees?

A. |E|

B. 2|E|

C. |V| + |E|

D. |V|²

Correct Answer: B. 2|E|

Question 2

Which representation is usually most space-efficient for a sparse graph?

A. Adjacency list

B. Adjacency matrix

C. Complete edge matrix

D. Distance table for every vertex pair

Correct Answer: A. Adjacency list

Question 3

Which traversal uses a queue and explores vertices level by level?

A. Depth-first search

B. Inorder traversal

C. Breadth-first search

D. Kruskal traversal

Correct Answer: C. Breadth-first search

Question 4

A tree with 12 vertices has how many edges?

A. 10

B. 11

C. 12

D. 24

Correct Answer: B. 11

Question 5

Dijkstra’s algorithm is guaranteed to work when edge weights are:

A. All negative

B. Non-negative

C. All equal to zero

D. Alternately positive and negative

Correct Answer: B. Non-negative

Question 6

What does a minimum spanning tree minimise?

A. The number of vertices

B. The maximum vertex degree in every case

C. The sum of selected edge weights

D. Every pairwise shortest-path distance

Correct Answer: C. The sum of selected edge weights

Question 7

Which algorithm repeatedly selects the least-weight edge that does not create a cycle?

A. Kruskal’s algorithm

B. Breadth-first search

C. Dijkstra’s algorithm

D. Inorder traversal

Correct Answer: A. Kruskal’s algorithm

Question 8

In a binary search tree, inorder traversal normally produces keys in what order?

A. Random order

B. Descending order only

C. Sorted order

D. Level order

Correct Answer: C. Sorted order

Question 9

An edge whose removal disconnects a connected graph is called a:

A. Leaf

B. Bridge

C. Root

D. Loop invariant

Correct Answer: B. Bridge

Question 10

A path contains edges with weights 3, 4 and 2. Assuming additive costs, what is its total weight?

A. 5

B. 7

C. 9

D. 24

Correct Answer: C. 9