Graph Theory and Network Models

Introduction

Many systems studied in artificial intelligence and machine learning are relational rather than purely tabular. Social platforms connect users, communication systems connect devices, recommendation engines connect users to products, and knowledge graphs connect entities through semantic relations. Graph theory provides the mathematical language for representing, analyzing, and computing over such systems.

A graph consists of vertices (also called nodes) and edges (also called links) that represent relationships. Graph theory supplies concepts such as connectivity, paths, cycles, coloring, matching, planarity, and traversal. Algorithms based on these concepts support routing, community analysis, recommendation, fraud detection, dependency analysis, and knowledge representation.

This chapter develops the foundations required to model networks and select suitable graph algorithms. It emphasizes both formal definitions and practical interpretation. Although examples often use unweighted graphs, real applications may involve edge weights, directions, labels, timestamps, uncertainty, and dynamically changing relationships.

Learning Objectives

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

1. Represent a system using suitable graph models and data structures.

2. Distinguish directed, undirected, weighted, simple, multigraph, bipartite, and attributed graphs.

3. Analyze degree, connectivity, paths, cycles, and components.

4. Apply breadth-first search, depth-first search, and shortest-path algorithms.

5. Explain graph coloring, matching, and planarity and identify their applications.

6. Select graph algorithms for social, communication, recommendation, and knowledge-graph systems.

7. Evaluate computational, modeling, ethical, and operational limitations of graph-based analysis.

1. Fundamental Graph Concepts

A graph is commonly written as

\[

G=(V,E),

\]

where \(V\) is a set of vertices and \(E\) is a set of edges. In an undirected graph, an edge is an unordered pair \(\{u,v\}\), whereas in a directed graph it is an ordered pair \((u,v)\), meaning that the relation goes from \(u\) to \(v\).

The order of a graph is \(|V|\), its number of vertices. The size of an undirected graph is \(|E|\), its number of edges. A graph is simple if it has no loops and no parallel edges. A loop joins a vertex to itself; parallel edges are multiple edges joining the same pair of vertices.

Two vertices are adjacent if an edge connects them. An edge is incident with each endpoint. The degree of a vertex \(v\), written \(\deg(v)\), is the number of incident edges in an undirected graph. A loop contributes two to degree under the usual convention because it has two incidences at the same vertex. In a directed graph, the in-degree counts incoming edges and the out-degree counts outgoing edges.

For every finite undirected graph,

\[

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

\]

This is the handshaking theorem: every edge contributes exactly two to the total degree. Consequently, the number of odd-degree vertices is even. For a directed graph,

\[

\sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E|,

\]

because every directed edge has one tail and one head.

A graph is complete, denoted \(K_n\), when every pair of distinct vertices is adjacent. A simple undirected complete graph has

\[

|E|=\frac{n(n-1)}{2}

\]

edges. A subgraph is formed from subsets of vertices and edges of a graph. A spanning subgraph contains all original vertices, though possibly fewer edges.

2. Graph Models and Representations

2.1 Common graph types

An undirected graph models symmetric relations, such as mutual friendship or a physical cable that permits communication in both directions. A directed graph models asymmetric relations, such as following on a social platform, hyperlinks, citations, or prerequisite relationships.

A weighted graph assigns a numerical value to each edge. Weights may represent distance, latency, cost, risk, or similarity. The meaning of the weight is essential: a high similarity is desirable, while a high cost is undesirable. A labeled or attributed graph stores additional information on vertices or edges, such as user age, relation type, or confidence score.

A multigraph permits parallel edges and is useful when two entities can have several distinct relationships. For example, two airports may be connected by multiple airline services. A bipartite graph has a partition \(V=X\cup Y\), where \(X\) and \(Y\) are disjoint and every edge joins a vertex in \(X\) to one in \(Y\). User–item recommendation data naturally forms a bipartite graph.

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 means connectivity after directions are ignored.

2.2 Adjacency matrix

For a graph with vertices \(v_1,\ldots,v_n\), the adjacency matrix \(A\) is an \(n\times n\) matrix in which

\[

A_{ij}=\begin{cases}1,&\text{if an edge from }v_i\text{ to }v_j\text{ exists},\\0,&\text{otherwise.}\end{cases}

\]

For a weighted graph, the entries may contain edge weights, subject to a defined convention for absent edges. An undirected graph has a symmetric adjacency matrix. Matrix representation provides constant-time edge-existence lookup, but requires \(O(|V|^2)\) storage, making it expensive for sparse large networks.

2.3 Adjacency lists and edge lists

An adjacency list stores, for each vertex, the vertices reached by its incident or outgoing edges. It requires \(O(|V|+|E|)\) storage and is usually preferable for sparse graphs. An edge list simply stores all edges, for example \((u,v,w)\), and is convenient for algorithms such as Bellman–Ford and for importing data. The representation should match the task: matrices suit dense graphs and algebraic operations; lists suit traversal and sparse network computation.

3. Walks, Paths, Cycles, and Distance

A walk is a sequence of vertices in which consecutive vertices are joined by edges; vertices and edges may repeat. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A closed walk starts and ends at the same vertex. A cycle is a closed path with at least one edge and no repeated vertices except the first and last.

The length of an unweighted walk is its number of edges. In a weighted graph, the length or cost of a path is the sum of its edge weights. A shortest path between two vertices minimizes this length or cost. The distance \(d(u,v)\) is the length of a shortest path when one exists; it may be regarded as infinite when no path exists.

A graph containing a cycle is not necessarily difficult to traverse, but cycles matter in dependency systems. A directed cycle in a prerequisite graph can indicate an impossible circular dependency. In a knowledge graph, cycles may be meaningful, but in a workflow graph they may signal an error.

A connected graph has an Euler trail if it contains a trail using every edge exactly once. For a connected undirected graph, an Euler circuit exists exactly when every vertex has even degree; an Euler trail but not an Euler circuit exists exactly when exactly two vertices have odd degree. These conditions concern edges, not vertices.

A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle returns to its starting vertex. Unlike Euler problems, Hamiltonian problems concern vertices. Determining whether a general graph has a Hamiltonian cycle is computationally difficult (NP-complete), so practical systems often use heuristics or exploit special graph structure.

4. Connectivity and Structural Analysis

Removing a vertex or edge can change connectivity. An articulation vertex is a vertex whose removal increases the number of connected components. A bridge is an edge whose removal increases the number of components. In a communication network, articulation points and bridges identify vulnerabilities or single points of failure.

A graph is k-connected if at least \(k\) vertices must be removed to disconnect it, subject to standard definitions concerning graph order. Higher connectivity generally indicates greater structural resilience, although it does not guarantee operational resilience when capacities, geographic concentration, or correlated failures are considered.

A tree is a connected undirected graph with no cycles. If a tree has \(n\geq 1\) vertices, it has exactly \(n-1\) edges. Equivalent characterizations include: there is exactly one path between every pair of vertices; adding any new edge creates a cycle; and removing any edge disconnects the graph. A forest is an acyclic graph, possibly disconnected.

A spanning tree of a connected graph is a subgraph containing all vertices and forming a tree. Spanning trees are useful for network broadcast, infrastructure design, and routing. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight, where weights represent additive costs and are typically assumed to be nonnegative or, more generally, arbitrary real values for the MST problem. Kruskal’s algorithm repeatedly chooses the least-weight edge that does not create a cycle; Prim’s algorithm grows one tree by repeatedly adding the least-weight edge crossing from the current tree to an unvisited vertex. These algorithms solve the MST problem, not the shortest-path problem: an MST minimizes total cost of the tree, whereas shortest paths minimize routes from specified sources.

5. Traversal Algorithms

5.1 Breadth-first search

Breadth-first search (BFS) explores vertices in layers according to their number of edges from a source. It uses a queue. Starting with source \(s\), mark \(s\) visited, enqueue it, and repeatedly remove the front vertex and enqueue each unvisited neighbor.

For an adjacency-list graph, BFS runs in \(O(|V|+|E|)\) time and uses \(O(|V|)\) auxiliary space, excluding the graph representation. In an unweighted graph, the first discovery distance from \(s\) is a shortest-path distance because BFS processes all vertices at distance \(k\) before any at distance \(k+1\). Parent pointers can reconstruct a shortest path.

5.2 Depth-first search

Depth-first search (DFS) explores as far as possible along one branch before backtracking. It can be implemented recursively or with an explicit stack. DFS also runs in \(O(|V|+|E|)\) time with adjacency lists.

DFS supports cycle detection, connected-component computation, topological sorting, and identification of articulation points and bridges. In a directed graph, a topological ordering exists exactly when the graph is a directed acyclic graph (DAG). DFS-based topological sorting places each vertex after all vertices reachable through its outgoing dependencies; a directed cycle prevents a valid ordering.

Worked Example 1: BFS shortest path

Suppose an undirected communication graph has edges

\[

\{A,B\},\{A,C\},\{B,D\},\{C,D\},\{D,E\}.

\]

Starting at \(A\), BFS first visits \(A\), then \(B,C\), then \(D\), and finally \(E\). The distances are \(d(A,A)=0\), \(d(A,B)=d(A,C)=1\), \(d(A,D)=2\), and \(d(A,E)=3\). One shortest path from \(A\) to \(E\) is \(A-B-D-E\); another is \(A-C-D-E\). BFS is suitable because every communication link has been treated as having equal cost.

6. Shortest-Path Methods

The correct shortest-path algorithm depends on edge weights and the required output.

BFS solves single-source shortest paths in unweighted graphs. Dijkstra’s algorithm solves single-source shortest paths when all edge weights are nonnegative. It maintains a tentative distance and repeatedly finalizes the unvisited vertex with the smallest tentative value. With a binary heap and adjacency lists, a common implementation has time complexity \(O((|V|+|E|)\log |V|)\); with a simple array it is \(O(|V|^2)\). Dijkstra is invalid in the presence of reachable negative-weight edges because a distance previously finalized might later be improved.

Bellman–Ford handles directed graphs with negative edge weights and can detect reachable negative cycles. Its time complexity is \(O(|V||E|)\). A negative cycle makes the shortest-path value undefined for vertices reachable from that cycle, because repeatedly traversing the cycle can reduce the total without bound.

Floyd–Warshall computes all-pairs shortest paths using dynamic programming and runs in \(O(|V|^3)\) time and \(O(|V|^2)\) space. It is useful for relatively small, dense graphs. Its standard formulation can detect negative cycles by examining negative diagonal entries after computation.

In social and recommendation systems, edge weights may represent similarity or probability rather than cost. If a larger weight means a stronger relationship, it may be necessary to transform the value into a distance, for example \(1-s\) when similarity \(s\) is normalized to \([0,1]\). Such a transformation must be justified; arbitrary conversion can distort the intended meaning.

7. Coloring and Scheduling

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The smallest number of colors needed is the chromatic number, written \(\chi(G)\). Coloring can model frequency assignment, examination scheduling, register allocation, and conflict-free resource use.

A graph is bipartite if and only if it is 2-colorable, equivalently if and only if it contains no odd cycle. BFS or DFS can test bipartiteness by assigning alternating colors during traversal. A complete graph \(K_n\) has \(\chi(K_n)=n\), while a nonempty tree has chromatic number 2.

The general minimum-coloring problem is computationally hard. Greedy coloring is fast but does not always produce an optimal coloring. It processes vertices in an order and assigns each the smallest color not used by its already colored neighbors. Ordering heuristics, such as largest-degree-first, can improve results but do not remove the worst-case difficulty.

Edge coloring assigns colors to edges so that incident edges have different colors. It can model time slots for transmissions sharing an endpoint. Vertex and edge coloring solve different constraints and should not be confused.

8. Matching and Bipartite Allocation

A matching is a set of edges with no shared endpoints. A maximum matching has the greatest possible number of edges; a maximal matching cannot be extended by adding another edge, but need not be maximum. In a weighted graph, a maximum-weight matching maximizes the sum of selected edge weights.

Matching is central to assigning students to projects, users to recommendations, workers to jobs, and communication channels to requests. In a bipartite graph, maximum matching can be found efficiently using augmenting-path methods. An augmenting path alternates between edges outside and inside the current matching and begins and ends at unmatched vertices. Flipping membership along such a path increases the matching size by one.

The assignment problem is a weighted bipartite matching problem in which each agent is assigned to exactly one task, often solved by the Hungarian algorithm. Real recommendation systems may use matching as one stage, followed by ranking, fairness constraints, capacity constraints, and feedback monitoring.

9. Planarity

A graph is planar if it can be drawn in the plane so that edges intersect only at common endpoints. A particular drawing is a plane graph. Planarity matters in circuit layout, geographic network visualization, and printed circuit design.

For a connected planar graph with \(v\) vertices, \(e\) edges, and \(f\) faces, Euler’s formula is

\[

v-e+f=2.

\]

For a simple connected planar graph with \(v\geq3\),

\[

e\leq3v-6.

\]

Thus, a simple graph with too many edges cannot be planar. The complete graph \(K_5\) and complete bipartite graph \(K_{3,3}\) are standard nonplanar examples. A graph is nonplanar precisely when it contains a subdivision of \(K_5\) or \(K_{3,3}\) (Kuratowski’s theorem). Large network visualizations are often nonplanar; a crossing in a drawing does not itself prove that the abstract graph is nonplanar, because a different drawing may remove it.

10. Network Models for AI and Machine Learning

Social networks

Users can be vertices and interactions can be directed or undirected edges. Edge weights may count interactions or encode recency. Degree, component structure, shortest paths, and community methods help identify influential or central users. However, degree is not identical to influence: activity may be automated, popularity may be concentrated, and influence may depend on content and audience.

Communication networks

Devices, routers, or applications form vertices, while physical or logical connections form edges. Weights can represent latency, bandwidth cost, or failure probability. BFS supports hop-based routing; Dijkstra supports minimum-latency routes; articulation and bridge analysis exposes vulnerabilities. Operational models should include capacity and redundancy rather than relying only on topology.

Recommendation systems

A user–item graph is naturally bipartite. Collaborative filtering can infer preferences from paths and neighborhoods. Projection of a bipartite graph into user–user or item–item similarity graphs may be useful but can create spurious similarity when highly popular items connect many users. Weighted edges, normalization, temporal decay, and negative feedback must be handled carefully.

Knowledge graphs

Knowledge graphs use labeled, often directed edges such as \(\text{Paris}\xrightarrow{\text{capital-of}}\text{France}\). Paths can support explanations and multi-hop question answering. Unlike an ordinary unlabeled graph, relation type and direction are semantically essential. A path that is structurally short may be logically invalid if it combines incompatible predicates. Missing edges, uncertain facts, duplicated entities, and temporal changes are major concerns.

Graph neural networks (GNNs) extend learning to graph-structured data by aggregating information from neighboring vertices. A simplified message-passing layer can be written as

\[

h_v^{(l+1)}=\sigma\left(W_l h_v^{(l)}+\sum_{u\in N(v)}\alpha_{uv}W'_l h_u^{(l)}\right),

\]

where \(h_v^{(l)}\) is the representation of vertex \(v\) at layer \(l\), \(N(v)\) is its neighborhood, \(W_l,W'_l\) are learned matrices, \(\alpha_{uv}\) are optional normalization or attention coefficients, and \(\sigma\) is an activation function. This is a model template rather than one universal GNN definition. More layers increase the receptive field but may cause oversmoothing, in which node representations become insufficiently distinguishable.

11. Illustrative Case: Resilient Emergency Communication Routing

Background

Consider a fictional regional emergency communication network connecting hospitals, dispatch centers, and relay towers. Each site is a vertex, and each available communication link is an undirected edge. Edge weights represent measured latency in milliseconds. Some links have backup capacity; others are single physical connections.

Problem

The organization must identify a low-latency route between the dispatch center and each hospital, detect single points of failure, and determine whether the network remains connected if one link fails. A simple hop count is inadequate because a one-hop satellite link may have greater latency than a two-hop fiber route.

Analysis and approach

The network is represented with adjacency lists containing latency weights. Dijkstra’s algorithm is run from the dispatch center because all latency weights are nonnegative. Parent pointers produce the actual routes, not merely their costs. Separately, DFS is used to identify bridges and articulation vertices. An MST is computed only for a separate planning question: connecting all sites with minimum total infrastructure cost. It is not substituted for shortest-path routing.

Suppose the least-latency route to Hospital H is Dispatch–Relay 2–Relay 4–H, with link latencies 8 ms, 5 ms, and 7 ms. Its total latency is

\[

8+5+7=20\text{ ms}.

\]

A direct alternative of 25 ms is therefore slower under the stated additive-latency model. If the edge connecting Relay 4 to H is a bridge, the organization should add a backup connection or alternative technology. If traffic capacity is variable, the model must be extended: the shortest-latency route may become unsuitable under congestion.

Outcome and learning points

The analysis produces routes, vulnerability indicators, and infrastructure priorities. It also demonstrates the importance of aligning algorithm choice with the question: Dijkstra addresses weighted routing, DFS addresses structural vulnerability, and MST addresses minimum-cost network construction. The case is illustrative; operational deployment would require monitoring, failure probabilities, security controls, and service-level constraints.

12. Limitations, Governance, and Best Practices

Graph results depend on how entities and relationships are defined. Duplicate accounts can inflate degree; missing interactions can fragment a network; sampling can create misleading centrality; and changing relationships make a static graph obsolete. Correlation in a graph does not establish causation.

Privacy is especially important in social and recommendation graphs because relationships may reveal sensitive affiliations, health conditions, political preferences, or location patterns. Data collection should have a lawful basis, purpose limitation, access control, retention limits, and appropriate anonymization. Anonymized graphs may remain re-identifiable through structural patterns. Organizations should document provenance, consent, data quality, and model limitations.

Graph-based decisions can amplify popularity bias, marginalize poorly connected groups, or propagate incorrect knowledge-graph facts. Evaluation should include subgroup performance, exposure distribution, false positives, and the consequences of errors. Security threats include sybil accounts, link injection, adversarial perturbations, and poisoned graph data.

Best practices include:

• define node and edge semantics before selecting an algorithm;
• distinguish directedness, weight meaning, and time dependence;
• validate graph quality and document missing-data mechanisms;
• choose algorithms according to assumptions, especially weight restrictions;
• preserve parent paths and provenance when explanations are required;
• test sensitivity to sampling, thresholds, and edge perturbations;
• monitor dynamic networks rather than treating a historical snapshot as permanent;
• combine graph metrics with domain knowledge and human oversight.

Contemporary Developments

Modern graph analytics increasingly uses distributed graph processing, temporal graphs, heterogeneous graphs, and graph databases. Temporal graphs represent edges with time intervals or event timestamps. Heterogeneous graphs contain multiple node and edge types, as in knowledge graphs and recommender systems. Vector databases and graph databases are sometimes combined so that semantic similarity retrieval is followed by graph-based reasoning.

Graph foundation models and retrieval-augmented systems are active research areas, but their outputs can inherit incomplete or incorrect graph structure. Explainability remains challenging: a short path may be easy to display but not sufficient to justify a prediction. Responsible deployment therefore requires evaluation of both predictive performance and the quality of structural explanations.

Chapter Summary

Graph theory models relational systems through vertices and edges. Directedness, weights, labels, bipartitions, and temporal attributes determine which representation and algorithms are appropriate. Degree and the handshaking theorem describe local structure; paths, cycles, connectivity, bridges, articulation vertices, and trees describe global organization and resilience.

BFS finds shortest paths in unweighted graphs, DFS supports structural analysis and topological ordering, and Dijkstra solves nonnegative weighted single-source shortest paths. Bellman–Ford handles negative edges, while Floyd–Warshall addresses all-pairs computation. Coloring models conflict-free resource allocation, matching models exclusive allocation, and planarity describes whether a graph can be drawn without crossings. MST algorithms solve minimum-cost connectivity, not shortest-route problems.

Social, communication, recommendation, and knowledge-graph systems benefit from graph representations, but graph results depend on data quality, semantic definitions, privacy, fairness, security, and changing network conditions. Effective professional practice combines mathematical reasoning, algorithmic analysis, domain validation, and responsible governance.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An entity or node in a graph.

Edge: A relationship or link between vertices.

Directed graph: A graph whose edges have orientation.

Weighted graph: A graph whose edges carry numerical values.

Degree: Number of incident edges at a vertex.

Path: A walk with no repeated vertices.

Cycle: A closed path with no repeated vertices except its endpoints.

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

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

Articulation vertex: A vertex whose removal increases the number of components.

Tree: A connected acyclic undirected graph.

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

Depth-first search: Branch-oriented graph traversal using recursion or a stack.

Shortest path: A minimum-cost route between specified vertices.

Graph coloring: Assignment of colors so adjacent vertices differ.

Matching: A set of edges sharing no endpoints.

Bipartite graph: A graph whose vertices divide into two edge-separated parts.

Planar graph: A graph drawable without edge crossings.

Knowledge graph: A labeled graph representing entities and semantic relations.

Review Questions

Short Answer Questions

1. State the handshaking theorem for a finite undirected graph.

2. What is the difference between a path and a walk?

3. Why is BFS suitable for shortest paths in unweighted graphs?

4. Define a bridge and explain its significance in a communication network.

5. Distinguish a maximum matching from a maximal matching.

Long Answer Questions

1. Compare adjacency matrices, adjacency lists, and edge lists, including their storage and practical uses.

2. Explain BFS, DFS, Dijkstra’s algorithm, Bellman–Ford, and Floyd–Warshall, and state when each is appropriate.

3. Explain trees, spanning trees, minimum spanning trees, and shortest paths. Why are MST and shortest-path problems different?

4. Discuss vertex coloring, bipartite graphs, matching, and their applications in scheduling and recommendation systems.

5. Explain planarity, Euler’s formula, and the significance of \(K_5\) and \(K_{3,3}\).

Analytical / Application Questions

1. Design a graph model for a user–item recommendation system. Specify vertex types, edge meaning, weights, and one potential bias.

2. A weighted communication graph contains only nonnegative edge weights, but one route has fewer hops and another has lower latency. Which algorithm should be used, and why?

3. Propose a graph-based method for identifying single points of failure in a network, and discuss two limitations of the method in a real deployment.

Multiple Choice Questions with Answers

Question 1

Which representation usually requires O(|V| + |E|) storage for a sparse graph?

A. Adjacency matrix

B. Adjacency list

C. Distance matrix

D. Incidence table containing every vertex pair

Correct Answer: B. Adjacency list

Question 2

What is the total degree of all vertices in an undirected graph with 12 edges?

A. 12

B. 18

C. 24

D. 144

Correct Answer: C. 24

Question 3

Which algorithm finds shortest paths from one source in an unweighted graph?

A. Breadth-first search

B. Prim’s algorithm

C. Kruskal’s algorithm

D. Greedy coloring

Correct Answer: A. Breadth-first search

Question 4

Dijkstra’s algorithm requires which condition on edge weights?

A. All edge weights must be equal

B. All edge weights must be nonnegative

C. At least one edge must have negative weight

D. The graph must be planar

Correct Answer: B. All edge weights must be nonnegative

Question 5

A connected undirected graph has an Euler circuit exactly when:

A. Every vertex has degree 2

B. Exactly two vertices have odd degree

C. Every vertex has even degree

D. The graph is complete

Correct Answer: C. Every vertex has even degree

Question 6

Which statement about a tree with n vertices is correct, for n at least 1?

A. It has n edges and exactly one cycle

B. It has n − 1 edges and no cycles

C. It must be complete

D. It must be directed

Correct Answer: B. It has n − 1 edges and no cycles

Question 7

A graph is bipartite if and only if it:

A. Has no cycles of any kind

B. Contains no odd cycle

C. Has exactly two vertices

D. Is a complete graph

Correct Answer: B. Contains no odd cycle

Question 8

What is a matching?

A. A set of edges with no shared endpoints

B. A set containing every edge in the graph

C. A path visiting every vertex

D. A coloring using exactly two colors

Correct Answer: A. A set of edges with no shared endpoints

Question 9

For a connected planar graph, which equation is Euler’s formula?

A. v + e + f = 2

B. v − e + f = 2

C. v − e − f = 2

D. e − v + f = 0

Correct Answer: B. v − e + f = 2

Question 10

Which method is specifically intended to compute a minimum spanning tree?

A. BFS

B. Floyd–Warshall

C. Kruskal’s algorithm

D. Bellman–Ford

Correct Answer: C. Kruskal’s algorithm