9. Graph Theory, Networks and Discrete Structures

Introduction and Context

Graph theory provides a mathematical language for representing relationships, interactions, routes, dependencies, and structures. A graph consists of entities, represented by vertices, and relationships between them, represented by edges. This apparently simple abstraction supports the analysis of computer networks, transportation systems, social communities, software dependencies, communication protocols, biological interactions, and knowledge graphs.

For computer science engineers, graph theory is not merely a collection of definitions and algorithms. It is a framework for modelling computational problems and reasoning about structure. Routing asks for suitable paths; distributed systems depend on connectivity and spanning trees; resource allocation can be formulated as matching; logistics and network capacity are studied through flows; register allocation and scheduling often involve coloring; and graph spectra reveal structural properties that may not be visible from local inspection.

This chapter develops the principal concepts, algorithms, measures, and applications of graph theory. It emphasizes both mathematical foundations and professional judgment: selecting an appropriate graph model, interpreting algorithmic results, understanding computational trade-offs, and recognizing limitations of graph-based representations.

Learning Objectives

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

1. Define graphs, directed graphs, weighted graphs, multigraphs, trees, and related structures.

2. Represent graphs using adjacency matrices, adjacency lists, and incidence structures.

3. Analyze paths, cycles, connectivity, components, and graph traversals.

4. Construct and apply spanning trees, shortest-path algorithms, matching methods, and maximum-flow models.

5. Explain graph coloring, planar structure, and the relationship between coloring and computational constraints.

6. Interpret degree-based, distance-based, centrality, and spectral measures.

7. Select appropriate graph models and algorithms for routing, social networks, distributed systems, and knowledge graphs.

8. Evaluate practical, ethical, scalability, and governance issues in graph-based systems.

1. Graphs as Models of Relationships

A graph is formally written as G = (V, E), where V is a nonempty set of vertices and E is a set of edges. In an undirected graph, an edge {u, v} represents a symmetric relationship. In a directed graph, an edge (u, v) represents an ordered relationship from u to v. Vertices may represent routers, users, documents, services, or states; edges may represent links, friendships, citations, dependencies, or transitions.

The degree of a vertex in an undirected graph is the number of incident edges. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges. The degree-sum theorem states that the sum of all vertex degrees equals twice the number of edges. Consequently, every undirected graph has an even number of odd-degree vertices. This result is useful in detecting modelling errors and in studying Euler trails.

Graphs may be simple, meaning that they have no loops or parallel edges, or they may be multigraphs, in which multiple edges can connect the same pair of vertices. A weighted graph assigns a numerical value to each edge. The weight may denote distance, cost, latency, risk, bandwidth, or probability. The meaning of a weight must be established before an algorithm is selected: minimizing latency is not equivalent to maximizing reliability, and negative values require special care.

A graph is complete if every pair of distinct vertices is adjacent. The complete graph on n vertices is denoted K_n. A bipartite graph has a partition V = X union Y such that every edge joins a vertex in X to one in Y. Bipartite graphs are central to matching and assignment problems. A graph is regular when all its vertices have the same degree.

Representations and Computational Consequences

An adjacency matrix is an n by n matrix A in which A_ij records whether an edge from i to j exists, or records its weight. It supports constant-time edge lookup but requires O(n^2) storage. An adjacency list stores the neighbors of each vertex and requires O(|V| + |E|) space. It is generally preferred for sparse graphs, which are common in web, social, and infrastructure networks. An edge list is simple and useful for algorithms that process edges sequentially, such as Kruskal's minimum spanning tree algorithm.

The choice of representation affects performance. Breadth-first search using adjacency lists runs in O(|V| + |E|), whereas scanning an adjacency matrix may require O(|V|^2). Dense graphs can justify matrix-based operations, while sparse graphs benefit from lists, compressed sparse-row structures, or distributed graph stores.

2. Paths, Cycles, and Connectivity

A walk is a sequence of vertices and edges in which repetition is allowed. A trail does not repeat edges, and 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 internal vertex. These distinctions matter because different problems impose different repetition constraints.

A graph is connected if every pair of vertices is joined by a path. A disconnected graph consists of connected components. In a directed graph, strong connectivity means that every vertex can reach every other vertex following edge directions. Weak connectivity ignores directions and examines the underlying undirected graph. Strongly connected components are important in dependency analysis, program control-flow graphs, and web-link analysis.

A bridge is an edge whose removal increases the number of connected components. An articulation vertex is a vertex whose removal does so. Bridges and articulation points identify single points of failure in communication or infrastructure networks. Algorithms based on depth-first search can identify them in linear time, O(|V| + |E|).

Euler and Hamilton concepts describe different kinds of traversal. An Euler trail uses every edge exactly once; an Euler circuit is a closed Euler trail. A connected undirected graph has an Euler circuit exactly when every vertex has even degree, and it has an Euler trail exactly when exactly zero or two vertices have odd degree. A Hamiltonian path visits each vertex exactly once. Unlike the Euler condition, the general Hamiltonian-cycle problem is computationally difficult, which illustrates an important distinction between apparently similar graph problems.

3. Trees and Hierarchical Structure

A tree is a connected undirected graph with no cycles. Equivalent characterizations include: a tree with n vertices has n - 1 edges; there is exactly one simple path between every pair of vertices; and adding any new edge creates a cycle. A forest is an acyclic graph that may be disconnected.

Rooted trees distinguish one vertex as the root and define parent-child relationships. They support file systems, XML and JSON structures, syntax trees, decision processes, indexing, and organization hierarchies. Binary search trees, heaps, tries, and balanced trees are specialized structures designed for particular operations.

A spanning tree of a connected graph contains all vertices and is itself a tree. A minimum spanning tree (MST) minimizes the total edge weight among all spanning trees. Kruskal's algorithm sorts edges and adds an edge when it does not create a cycle, using a disjoint-set data structure. Prim's algorithm grows one tree by repeatedly adding the least-weight edge crossing from the current tree to an unvisited vertex. With suitable priority queues, both are efficient for many sparse graphs.

An MST minimizes total infrastructure cost, not the distance between every pair of vertices. This distinction is significant in network design. A minimum-cost fiber layout may create long routes between some endpoints, whereas a shortest-path tree from a particular source optimizes distances from that source. Engineers must therefore align the objective with the operational requirement.

4. Traversal and Search

Depth-first search (DFS) explores a branch as far as possible before backtracking. It can be implemented recursively or with an explicit stack. DFS supports cycle detection, topological sorting, articulation-point detection, strongly connected components, and maze exploration.

Breadth-first search (BFS) explores vertices in layers using a queue. In an unweighted graph, BFS computes shortest path length in number of edges from a source. It is useful for minimum-hop routing, social-distance analysis, broadcasting, and discovering connected components.

For a directed acyclic graph (DAG), a topological ordering lists vertices so that every directed edge goes from an earlier to a later vertex. Such an ordering exists if and only if the graph has no directed cycle. Kahn's algorithm repeatedly removes zero-indegree vertices; a DFS-based method records reverse finishing order. Topological ordering supports build systems, course prerequisites, workflow management, and scheduling.

For weighted shortest paths, Dijkstra's algorithm is appropriate when all edge weights are nonnegative. It maintains a tentative distance and repeatedly settles the unsettled vertex with minimum distance. Bellman-Ford handles negative edge weights and can detect negative cycles, but is slower in general. Floyd-Warshall computes all-pairs shortest paths through dynamic programming and is attractive for relatively small dense graphs. In large systems, A* search can accelerate path finding when an admissible heuristic estimates the remaining cost.

5. Matching, Assignment, and Resource Allocation

A matching is a set of edges with no shared endpoint. A maximum matching has the largest possible number of matched edges; a perfect matching covers every vertex. In a bipartite graph, one part may represent workers and the other jobs, or applicants and positions. A matching then represents a feasible assignment.

Hall's theorem states that a bipartite graph has a matching covering every vertex in X if and only if, for every subset S of X, the neighborhood N(S) has at least |S| vertices. The theorem is conceptually important because it identifies the structural cause of assignment failure: a group of agents may collectively have too few eligible resources.

Weighted assignment problems seek a matching of minimum cost or maximum benefit. They can be solved through the Hungarian algorithm or formulated as minimum-cost flow. In distributed systems, matching can allocate tasks to machines subject to compatibility constraints. In cloud scheduling, however, capacity, affinity, fairness, and changing workloads may require extensions beyond a static matching model.

6. Flow Networks and Cut-Based Reasoning

A flow network is a directed graph with a source s, sink t, and nonnegative capacity c(u, v) on each edge. A feasible flow respects capacity constraints and flow conservation at intermediate vertices. The maximum-flow problem seeks the largest amount that can be sent from s to t.

The Ford-Fulkerson method repeatedly finds an augmenting path in a residual network and increases the flow along it. The Edmonds-Karp implementation uses BFS to select augmenting paths and has a polynomial worst-case bound. The max-flow min-cut theorem states that the value of a maximum flow equals the capacity of a minimum s-t cut. A cut identifies a bottleneck separating supply from demand.

Flow models apply to packet routing, water or energy distribution, production planning, evacuation, and data pipelines. A practical model may need multiple sources, multiple sinks, lower bounds, node capacities, or costs. Transformation techniques can convert some of these variants into standard flow problems. Nevertheless, a numerical maximum flow is meaningful only if capacities accurately represent operational limits and if simultaneous flows do not violate assumptions about time, interference, or failure.

7. Coloring, Scheduling, and Conflict Management

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number, chi(G), is the smallest number of colors required. Coloring models conflicts: vertices may be examinations, and edges may indicate students taking both; colors then represent time slots. In compiler design, an interference graph models variables whose live ranges overlap, and colors represent registers.

A graph is bipartite exactly when it is two-colorable, or equivalently, when it contains no odd cycle. This provides an efficient test using BFS or DFS. General coloring is computationally difficult, so practical systems use heuristics such as greedy ordering, largest-degree-first, saturation-based methods, or integer programming for smaller instances.

Edge coloring assigns colors to edges so that incident edges differ. It can model communication channels or matchings scheduled over time. Coloring solutions should be evaluated not only by the number of colors but also by stability, fairness, transition cost, and robustness when the graph changes.

8. Network Measures and Spectral Perspectives

Local degree measures immediate connectivity. Degree centrality identifies highly connected vertices, but it can overvalue hubs in networks where indirect influence matters. Betweenness centrality measures how frequently a vertex lies on shortest paths between other vertices and can reveal brokers or bottlenecks. Closeness centrality reflects average distance to other vertices, while eigenvector centrality assigns importance to vertices connected to important vertices. PageRank is a related prestige measure based on a random-surfer interpretation and damping.

Community detection seeks groups with comparatively dense internal connections and sparser external connections. Modularity is a widely used objective, although it has resolution limitations and may produce different results under different algorithms or random seeds. Communities are analytical hypotheses, not automatically real social or organizational categories.

The adjacency matrix A and degree matrix D support spectral analysis. The combinatorial Laplacian is L = D - A, and the normalized Laplacian scales this structure by vertex degrees. Laplacian eigenvalues relate to connectivity, diffusion, synchronization, and clustering. The second-smallest Laplacian eigenvalue, often called algebraic connectivity, is positive precisely for a connected graph and provides an indication of how well connected the graph is.

Spectral methods are useful in partitioning, anomaly detection, image segmentation, recommender systems, and graph machine learning. Their interpretation requires care: eigenvectors depend on modelling choices, normalization, weights, and data quality. Spectral evidence complements, rather than replaces, domain reasoning.

9. Graphs in Distributed Systems and Knowledge Engineering

Distributed systems frequently rely on graph structure. A communication topology determines routes and failure propagation. Spanning trees support broadcast and aggregation, while leader-election and consensus protocols depend on assumptions about connectivity, timing, and faults. A system may remain connected while still failing to satisfy the stronger conditions required for consensus or reliable coordination.

Knowledge graphs represent entities and typed relations, often using triples such as subject-predicate-object. They enable semantic search, recommendation, question answering, entity resolution, and data integration. Unlike a simple social graph, a knowledge graph may contain directed, labeled, weighted, temporal, and uncertain edges. Schema constraints, provenance, and identity resolution are therefore as important as traversal algorithms.

Graph databases commonly provide index-free adjacency, query languages, and support for pattern matching. Analytical graph processing frameworks distribute operations such as PageRank, connected components, and neighborhood aggregation. Large-scale processing must address partitioning: edges crossing machines create communication overhead, while highly skewed hubs can cause load imbalance.

Illustrative Case Study: Designing a Resilient Campus Network

Background

Consider a fictional university deploying a high-speed network connecting academic buildings, residence halls, a data center, and an emergency operations center. The university must control installation cost while maintaining acceptable connectivity and providing alternate routes for critical services.

Situation and Problem

The initial proposal connects every building to the data center through a separate link. This offers simple management but is expensive and creates a concentration of traffic and failure at the data center. The engineering team must determine a lower-cost topology, identify vulnerable locations, and allocate bandwidth for ordinary and emergency traffic.

Analysis

The network is represented as a weighted graph. Vertices are buildings and switching sites; edge weights are installation costs. Kruskal's algorithm produces a minimum spanning tree, showing the least-cost structure that connects all sites. However, the tree has no redundancy: failure of a bridge disconnects the network. Articulation-point analysis identifies switching locations whose failure partitions the campus.

A second graph is formed using latency as edge weight. Dijkstra's algorithm evaluates shortest routes from the data center, while a maximum-flow model examines whether the emergency center can receive sufficient capacity when several links are saturated. For selected critical edges, additional links are added to create cycles and remove important single points of failure.

Approach and Solution

The final design uses the minimum spanning tree as a cost baseline rather than as the final topology. Additional links are added around the emergency center and between two major switching sites. Traffic classes are separated logically, and routing policies prioritize emergency services. BFS-based reachability checks are automated after each simulated failure. The design is periodically recalculated as buildings, costs, and traffic patterns change.

Outcome

The resulting network costs more than the pure MST but provides alternate routes, better resilience, and adequate emergency capacity. The case demonstrates that graph algorithms do not make the design decision automatically. They expose trade-offs among cost, latency, capacity, and fault tolerance; engineering judgment determines which trade-off is acceptable.

Learning Points

1. A minimum-cost topology may not be a resilient topology.

2. Bridges and articulation points reveal structural vulnerabilities.

3. Shortest paths and maximum flows answer different operational questions.

4. Failure simulation is necessary because static connectivity can conceal weak points.

5. Graph models should represent the actual meaning of weights and constraints.

Challenges, Limitations, and Common Errors

A graph model can be mathematically correct yet operationally misleading. Common errors include treating a directed relationship as symmetric, confusing edge count with bandwidth, ignoring time variation, and collapsing multiple entities into one node. Data duplication and inaccurate identity resolution can create artificial hubs or false communities.

Algorithmic complexity is another constraint. Exact solutions to many optimization problems, including general graph coloring and Hamiltonian-cycle search, do not scale efficiently. Heuristics may produce useful solutions without proving optimality. Approximation guarantees, validation on realistic workloads, and sensitivity analysis should therefore accompany deployment.

Dynamic graphs introduce insertions, deletions, changing weights, and evolving communities. Recomputing from scratch may be too expensive, while incremental algorithms can be complex. Distributed graph processing also faces communication cost, inconsistent snapshots, skewed partitions, and fault recovery.

Graph analytics can expose sensitive relationships. Social, health, financial, and communication graphs may permit re-identification even after direct identifiers are removed. Organizations should apply data minimization, access control, purpose limitation, retention policies, provenance tracking, and appropriate privacy-preserving methods. Centrality scores or risk rankings should not be treated as neutral facts when they affect individuals or institutions; model assumptions and uncertainty must be disclosed.

Best Practices for Graph-Based Engineering

A sound graph project begins by defining entities, relationships, direction, multiplicity, weights, time, and uncertainty. The objective should be expressed explicitly: minimize cost, minimize delay, maximize throughput, identify vulnerable nodes, or detect communities. Representation and algorithm selection should follow from these definitions.

Engineers should validate graph data, test algorithms on small cases with known answers, measure time and memory, and compare results against baselines. For operational systems, monitoring should include graph drift, connectivity changes, anomalous degree growth, and failure patterns. Explainability is especially important when graph-derived scores influence allocation, security response, or access decisions.

Current Developments and Emerging Directions

Modern graph learning methods use neural message passing to learn representations from neighborhoods and structure. Graph embeddings support similarity search and recommendation, while graph neural networks address node classification, link prediction, and graph-level prediction. Their success depends on representative training data, suitable aggregation, and protection against noisy or adversarial edges.

Temporal and heterogeneous graphs increasingly model systems in which relations have types and validity intervals. Probabilistic graphs represent uncertainty rather than forcing every relationship to be binary. Research also continues on dynamic shortest paths, privacy-preserving graph analytics, quantum-inspired optimization, graph databases for multimodal data, and combining symbolic knowledge graphs with large language models. These developments expand capability but do not remove the need for clear semantics, reliable data, and accountable governance.

Chapter Summary

Graph theory models entities and relationships through vertices and edges. Fundamental ideas include degree, paths, cycles, connectivity, components, bridges, articulation points, trees, and spanning trees. BFS and DFS provide foundational traversal methods; topological sorting handles acyclic dependencies; shortest-path algorithms address routing; matching supports assignment; flow and cut theory models capacity; and coloring represents conflicts and scheduling.

Network measures such as centrality and community structure provide ways to interpret large relational systems, while spectral methods use matrix eigenvalues to study connectivity and partitioning. Graphs support routing, distributed coordination, infrastructure design, social analysis, knowledge representation, and graph-based machine learning. Effective use requires careful modelling, awareness of complexity and uncertainty, resilience analysis, privacy protection, and alignment between mathematical objectives and operational goals.

Key Terms

Graph: A structure consisting of vertices and edges representing entities and relationships.

Vertex: An entity or node in a graph.

Edge: A connection or relationship between vertices.

Directed graph: A graph whose edges have orientations.

Weighted graph: A graph whose edges carry numerical values such as cost or distance.

Degree: The number of edges incident to a vertex.

Path: A sequence of vertices connected without repeated vertices.

Cycle: A closed path with no repeated internal vertices.

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

Tree: A connected acyclic undirected graph.

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

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

Breadth-first search: A layer-by-layer graph traversal using a queue.

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

Matching: A set of edges sharing no endpoints.

Flow network: A directed capacitated graph with a source and sink.

Graph coloring: Assignment of labels to vertices so adjacent vertices differ.

Centrality: A measure of the structural importance of a vertex.

Laplacian matrix: A matrix commonly defined as degree matrix minus adjacency matrix.

Knowledge graph: A graph representing entities and semantically typed relationships.

Review Questions

Short Answer Questions

1. Distinguish between a path, a trail, and a walk.

2. Why is an adjacency list usually preferable for a sparse graph?

3. State the condition for an undirected graph to have an Euler circuit.

4. What does an articulation vertex indicate in a network?

5. What is the purpose of a residual network in maximum-flow computation?

Long Answer Questions

1. Explain trees and spanning trees, and compare the objectives of a minimum spanning tree and a shortest-path tree.

2. Describe BFS and DFS, including their data structures, complexity, and major applications.

3. Explain bipartite matching and Hall's theorem using an assignment example.

4. Discuss maximum flow, minimum cuts, and the practical interpretation of bottlenecks.

5. Explain centrality measures and spectral graph concepts, including the graph Laplacian.

Analytical / Application Questions

1. A communication graph has a low-cost spanning tree, but two edges are bridges. Analyze the risks and propose a topology-selection strategy.

2. Model a university examination timetable as a graph-coloring problem. Define vertices, edges, colors, constraints, and a suitable solution method.

3. A knowledge graph contains a highly connected entity created by merging several distinct organizations. Explain how this error could affect centrality, community detection, and recommendations, and propose validation measures.

22. Multiple Choice Questions with Answers

Question 1

Which graph representation is generally most space-efficient for a sparse graph with |V| vertices and |E| edges?

A. Adjacency matrix requiring O(|V|^2) space

B. Adjacency list requiring O(|V|+|E|) space

C. Complete-graph representation

D. Distance matrix requiring O(|V|^2) space

Correct Answer: B. Adjacency list requiring O(|V|+|E|) space

Question 2

A connected undirected graph has exactly two vertices of odd degree. What does this imply?

A. It has an Euler circuit

B. It has an Euler trail but not an Euler circuit

C. It must be a tree

D. It must be bipartite

Correct Answer: B. It has an Euler trail but not an Euler circuit

Question 3

Which algorithm is appropriate for shortest paths when all edge weights are nonnegative?

A. Dijkstra's algorithm

B. Topological sorting

C. Kruskal's algorithm

D. Ford-Fulkerson only

Correct Answer: A. Dijkstra's algorithm

Question 4

What does a minimum spanning tree optimize?

A. The shortest distance from one selected source to every vertex

B. The maximum flow between two vertices

C. The total weight of a tree connecting all vertices

D. The number of colors needed by the graph

Correct Answer: C. The total weight of a tree connecting all vertices

Question 5

In a bipartite assignment graph, Hall's theorem concerns whether:

A. Every cycle has even length

B. A matching can cover all vertices in one part

C. The graph has a minimum spanning tree

D. All edge weights are positive

Correct Answer: B. A matching can cover all vertices in one part

Question 6

According to the max-flow min-cut theorem, the value of a maximum flow equals:

A. The number of vertices in the network

B. The capacity of a minimum source-sink cut

C. The sum of all edge weights

D. The degree of the source

Correct Answer: B. The capacity of a minimum source-sink cut

Question 7

A graph is two-colorable exactly when it:

A. Has no odd cycle

B. Has no bridge

C. Is complete

D. Has equal numbers of vertices and edges

Correct Answer: A. Has no odd cycle

Question 8

Which measure is particularly associated with identifying vertices that frequently lie on shortest paths between other vertices?

A. Degree centrality

B. Betweenness centrality

C. Indegree only

D. Algebraic connectivity

Correct Answer: B. Betweenness centrality

Question 9

For a connected graph, a positive second-smallest eigenvalue of the Laplacian is associated with:

A. The graph being connected

B. The graph being complete

C. The graph having an Euler circuit

D. The graph being acyclic

Correct Answer: A. The graph being connected

Question 10

In the campus-network case, why was the minimum spanning tree not adopted as the complete final design?

A. An MST cannot contain all vertices

B. An MST always has negative edge weights

C. An MST may contain bridges and therefore lack redundancy

D. An MST cannot be computed for weighted graphs

Correct Answer: C. An MST may contain bridges and therefore lack redundancy