Trees, Spanning Structures and Network Optimization

Introduction and Context

Many systems studied in artificial intelligence, logistics and management can be represented as networks. A computer file system contains folders and files arranged hierarchically; a transportation system connects locations through roads; a communication system links devices; and a supply chain connects suppliers, warehouses and customers. Discrete mathematics provides structures and algorithms for analyzing these systems.

A tree is a connected graph with no cycles. Trees are especially useful when a system has hierarchy, unique paths or a need to connect all components with minimal redundancy. Related structures include rooted trees, binary trees, binary search trees, decision trees and spanning trees. Network optimization extends these ideas to problems such as finding a least-cost communication infrastructure or determining the maximum quantity that can move through a distribution network.

This chapter develops the mathematical foundations and algorithms needed to analyze these structures. It also considers their practical use in AI, logistics and managerial decision support.

Learning Objectives

After studying this chapter, you should be able to:

1. Define trees, rooted trees, binary trees, search trees and spanning trees.

2. Prove and apply important properties of trees.

3. Perform preorder, inorder, postorder and breadth-first traversals.

4. Explain how binary search trees and decision trees support computation and decision-making.

5. Construct minimum spanning trees using Kruskal’s and Prim’s algorithms.

6. Analyze network-flow models using capacities, conservation and cuts.

7. Evaluate the strengths, limitations and professional implications of tree and network methods.

1. Trees and Their Fundamental Properties

A graph is a pair G = (V, E), where V is a set of vertices and E is a set of edges joining selected pairs of vertices. In an undirected graph, edges have no direction. A path is a sequence of vertices connected by edges. A cycle is a closed path whose starting and ending vertices are the same and whose internal vertices are distinct.

A tree is an undirected graph that is connected and acyclic. A graph consisting of several disconnected trees is called a forest.

For a tree with n vertices, the following properties are equivalent:

• The graph is connected and has no cycles.
• There is exactly one simple path between every pair of vertices.
• The graph is connected and has n − 1 edges.
• The graph has no cycles and has n − 1 edges.
• Adding any new edge creates exactly one cycle.
• Removing any edge disconnects the graph.

Thus, every tree with n vertices has exactly n − 1 edges. This identity is one of the most useful tests for recognizing a tree.

Proof of the edge-count property

A one-vertex graph is a tree and has 0 = 1 − 1 edges. Suppose a tree has n vertices. Every tree with at least two vertices has at least one leaf, a vertex of degree 1. Remove a leaf and its incident edge. The remaining graph is still a tree with n − 1 vertices, so by induction it has n − 2 edges. Restoring the removed edge gives n − 1 edges.

The edge-count result is valid for finite undirected trees. It should not be applied without modification to directed graphs, multigraphs or infinite graphs.

Terminology

The degree of a vertex is the number of edges incident to it. A vertex of degree 1 is a leaf, while a vertex of degree 0 is isolated. In a tree containing more than one vertex, every leaf has degree 1.

A subtree is a connected subgraph that is itself a tree. A path graph is a tree in which each vertex has degree at most 2. A star has one central vertex connected to all other vertices. Trees are minimally connected: they retain connectivity with the fewest possible edges.

2. Rooted Trees and Hierarchical Representation

A rooted tree is a tree in which one vertex is designated as the root. Once a root is selected, every other vertex has a unique parent, namely the previous vertex on the path toward the root. The vertices immediately below a vertex are its children.

The depth of a vertex is the number of edges on the path from the root to that vertex. The root has depth 0. The height of a rooted tree is the maximum depth of any vertex. A vertex with no children is a leaf. An internal vertex has at least one child.

Rooted trees model organizational charts, XML documents, file directories, game states, classification taxonomies and task decomposition. They are also used in AI search, where each node represents a state and each edge represents an action.

A rooted tree is sometimes described as an ordered tree when the children of each vertex have a specified left-to-right order. The ordering matters for traversal and for representing expressions or structured documents.

Full, complete and balanced binary trees

A binary tree is a rooted tree in which each vertex has at most two children, conventionally called the left and right child.

A full binary tree is one in which every internal vertex has exactly two children. If a full binary tree has I internal vertices and L leaves, then

L = I + 1.

Therefore, the total number of vertices is 2I + 1. This result follows because the tree has 2I child edges, and also has (I + L) − 1 edges. Equating these expressions gives L = I + 1.

A complete binary tree has every level completely filled except possibly the final level, which is filled from left to right. Complete trees can be stored efficiently in arrays. With zero-based indexing, the left child of position i is at 2i + 1 and the right child is at 2i + 2, when those positions exist.

A perfect binary tree has every internal vertex with two children and all leaves at the same depth. If its height is h, then it has 2^h leaves and 2^(h+1) − 1 total vertices.

A balanced binary tree has height that remains proportional to log n, where n is the number of vertices. Balance is important because many search operations take time proportional to the height rather than directly to the number of vertices.

3. Tree Traversals

A traversal visits every vertex of a tree according to a systematic order. Traversals are central to compilers, database indexing, symbolic expression processing and AI search.

Depth-first traversals

In a preorder traversal, visit the current vertex first, then recursively traverse the left subtree and the right subtree:

Preorder(T):

1. Visit the root.

2. Traverse the left subtree in preorder.

3. Traverse the right subtree in preorder.

In an inorder traversal, recursively traverse the left subtree, visit the current vertex, and then traverse the right subtree:

Inorder(T):

1. Traverse the left subtree in inorder.

2. Visit the root.

3. Traverse the right subtree in inorder.

In a postorder traversal, process the subtrees before the current vertex:

Postorder(T):

1. Traverse the left subtree in postorder.

2. Traverse the right subtree in postorder.

3. Visit the root.

For a binary expression tree, preorder corresponds approximately to prefix notation, inorder to infix notation, and postorder to postfix notation. Postorder is useful when deleting a tree or evaluating an expression because children are processed before their parent.

Breadth-first traversal

A breadth-first traversal visits vertices level by level. It uses a queue:

1. Insert the root into a queue.

2. Remove the front vertex and visit it.

3. Insert its unvisited children.

4. Repeat until the queue is empty.

For a tree with n vertices, both depth-first and breadth-first traversals take O(n) time because each vertex and edge is processed a constant number of times. Their memory requirements differ. Depth-first search uses storage related to tree height, while breadth-first search may store an entire level.

Worked example: traversal

Consider the binary tree with root A; A’s left and right children are B and C; B has children D and E; and C has right child F.

• Preorder: A, B, D, E, C, F
• Inorder: D, B, E, A, C, F
• Postorder: D, E, B, F, C, A
• Breadth-first: A, B, C, D, E, F

The inorder sequence is not automatically sorted. It becomes sorted only when the tree satisfies the binary-search-tree ordering property described next.

4. Binary Search Trees

A binary search tree (BST) is a binary tree in which, for every vertex containing key k, all keys in the left subtree are smaller than k and all keys in the right subtree are larger than k. A convention for duplicate keys must be specified; common choices place duplicates consistently on one side or store a count at the vertex.

Searching begins at the root. If the target equals the current key, the search succeeds. If it is smaller, the search continues in the left subtree; if larger, it continues in the right subtree. Insertion follows the same comparisons and places the new key at an appropriate leaf position.

If the tree height is h, search, insertion and deletion take O(h) time. A balanced BST has h = O(log n), producing O(log n) operations. In the worst case, inserting already sorted keys into an ordinary BST produces a chain, with h = n − 1 and O(n) operations.

Self-balancing trees, such as AVL trees and red-black trees, use rotations to maintain height proportional to log n. These structures are important in symbol tables, indexing systems and scheduling applications.

Deletion in a BST

Deletion has three cases:

1. A leaf is removed directly.

2. A vertex with one child is replaced by its child.

3. A vertex with two children is replaced by its inorder successor or inorder predecessor, after which the replacement vertex is removed from its original position.

The ordering property must remain true after deletion.

5. Decision Trees in AI and Management

A decision tree is a rooted tree used to represent a sequence of tests leading to outcomes. Internal vertices represent tests, branches represent test results, and leaves represent classifications, actions or predictions.

In supervised machine learning, a decision-tree classifier recursively partitions data according to feature tests. A split may be selected using measures such as entropy reduction or the Gini criterion. For a class distribution with probabilities p1, p2, ..., pk, entropy is

H(S) = −Σ pi log2(pi),

where the sum is over classes with nonzero probability. Entropy is measured in bits when the logarithm has base 2. A pure node, containing examples from only one class, has entropy 0. A weighted average of child entropies is compared with the parent entropy to evaluate the split.

The information gain of a split is

Gain(S, split) = H(S) − Σv (|Sv|/|S|) H(Sv),

where S is the parent data set, Sv is the subset produced by branch v, and |S| denotes the number of observations. The formula assumes categorical or discretized outcomes and uses the child proportions as weights.

Decision trees are interpretable and can handle nonlinear relationships and mixed feature types. However, deep trees can overfit. Appropriate practices include limiting maximum depth, requiring a minimum number of observations per leaf, pruning weak branches and evaluating performance on unseen validation data.

In managerial decision support, a decision tree may represent choices under uncertainty. Expected monetary value can be calculated as

EMV = Σ pi Vi,

where pi is the probability of outcome i, Vi is its value, and the probabilities sum to 1. This calculation assumes that outcomes are mutually exclusive and collectively exhaustive and that the values and probabilities are comparable.

6. Spanning Trees and Minimum Spanning Trees

Let G be a connected, weighted, undirected graph. A spanning tree is a subgraph that contains every vertex of G and is a tree. Therefore, a spanning tree of a graph with n vertices always contains exactly n − 1 edges.

A graph may have many spanning trees. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Edge weights may represent distance, construction cost, latency, risk or energy consumption. An MST is not a shortest-path tree: an MST minimizes the total cost of connecting all vertices, whereas a shortest-path algorithm minimizes distance from a specified source to other vertices.

If all edge weights are distinct, the MST is unique. With equal weights, multiple MSTs may exist, although their total weight is the same under the usual definition.

Kruskal’s algorithm

Kruskal’s algorithm is a greedy method:

1. Sort all edges in nondecreasing order of weight.

2. Start with no selected edges.

3. Consider each edge in sorted order.

4. Add an edge if it does not create a cycle among selected edges.

5. Stop after n − 1 edges have been selected.

The cycle test is efficiently implemented with a disjoint-set union structure. With efficient sorting and union-find operations, the running time is O(m log m) for m edges, dominated by sorting.

Prim’s algorithm

Prim’s algorithm begins with any vertex and repeatedly adds the cheapest edge connecting the current tree to a vertex outside it. With an adjacency list and binary heap, the running time is commonly O(m log n), where n is the number of vertices and m is the number of edges.

Both algorithms are correct because of the cut property: for any cut dividing the vertices into two sets, a minimum-weight edge crossing that cut is safe to include in some MST. The cycle property also states that a heaviest edge on a cycle cannot be necessary in an MST when it is uniquely heaviest.

Worked example: Kruskal’s algorithm

Suppose four sites A, B, C and D have edges with costs:

AB = 1, AC = 4, AD = 3, BC = 2, BD = 5, CD = 6.

Sorted edges are AB(1), BC(2), AD(3), AC(4), BD(5), CD(6). Select AB and BC. Select AD; the selected edges now connect all four vertices and contain 3 = 4 − 1 edges. The total cost is

1 + 2 + 3 = 6.

The edges AC, BD and CD are rejected because the required spanning tree is already complete. The result is an MST. It is not necessary that every selected edge be part of a shortest path from A to another site; the objective is total connection cost.

7. Network Flow Optimization

A flow network is a directed graph with a source s and sink t. Each directed edge has a nonnegative capacity c(u,v). A flow f(u,v) must satisfy:

• Capacity constraint: 0 ≤ f(u,v) ≤ c(u,v).
• Conservation: for every intermediate vertex, inflow equals outflow.

The value of a flow is the total flow leaving s, equivalently the total flow entering t, provided conservation holds at all other vertices.

The maximum-flow problem seeks a feasible flow of greatest value. The Ford–Fulkerson method repeatedly finds an augmenting path in the residual network and increases the flow by the smallest residual capacity on that path. If capacities are integers and augmenting paths are selected appropriately, the method terminates with an integral maximum flow. The Edmonds–Karp implementation uses breadth-first search to find augmenting paths and has polynomial worst-case time O(VE²), where V is the number of vertices and E is the number of directed edges.

A cut divides the vertices into a source side containing s and a sink side containing t. Its capacity is the sum of capacities of directed edges from the source side to the sink side. The max-flow min-cut theorem states that the maximum flow value equals the minimum cut capacity. This theorem provides both an optimization result and a diagnostic explanation: a minimum cut identifies a bottleneck in the network.

Flows can model production, transportation, communication bandwidth, evacuation and assignment. A basic model may require additional constraints, such as lower bounds, costs, multiple commodities, time periods or capacities at vertices. In such cases, a standard maximum-flow model may be insufficient and a more advanced network-optimization formulation is needed.

8. Integrated Application: Regional Vaccine Distribution

Background

Consider an illustrative case in which a public-health agency must connect four cold-storage facilities and determine how many vaccine shipments can reach hospitals each day. Roads have construction costs, while transportation lanes have daily capacities.

Problem

The agency wants to build a low-cost communication and monitoring network linking facilities A, B, C and D. It also wants to estimate the maximum number of shipment units that can move from a central depot to hospitals through a directed logistics network.

Analysis and approach

For the monitoring network, the available road costs are the same as in the previous example. Kruskal’s algorithm selects AB, BC and AD, with total installation cost 6 cost units. The result connects all facilities while avoiding redundant construction. A manager should not interpret this as a recommendation to eliminate every alternative road: operational resilience may justify adding extra edges even though they are not part of the MST.

For shipment capacity, suppose the directed network has capacities:

• Depot → A: 20
• Depot → B: 10
• A → C: 10
• A → Hospital 1: 10
• B → C: 5
• B → Hospital 2: 5
• C → Hospital 1: 10
• C → Hospital 2: 10

The total capacity leaving the depot is 30 units, and the total capacity entering the hospitals is also 30 units. A feasible flow of 30 exists by sending 10 units through Depot–A–Hospital 1, 10 through Depot–A–C–Hospital 2, 5 through Depot–B–C–Hospital 1, and 5 through Depot–B–Hospital 2. Intermediate conservation holds: A receives 20 and sends 20; B receives 10 and sends 10; C receives 15 and sends 15. Since a source cut has capacity 30, no flow can exceed 30. Therefore, the maximum flow is 30 units per day.

Outcome and learning points

The MST identifies a least-cost baseline infrastructure, while maximum flow identifies a throughput limit. These are different objectives and require different models. If the agency adds reliability requirements, it may build backup links. If transportation costs vary, it may use minimum-cost flow rather than maximum flow. If demand is uncertain, scenario analysis and robust optimization may be appropriate.

9. Challenges, Limitations and Governance

Tree and network models simplify reality. A tree assumes a hierarchical or acyclic structure, whereas many real systems contain feedback, redundancy and multiple relationships. An MST ignores reliability, maintenance, congestion and direction unless these are explicitly modeled. A maximum-flow model may ignore travel time, cost, perishability and fairness.

In AI decision trees, interpretability does not guarantee fairness or causal validity. A tree may reproduce historical discrimination if training data reflect unequal treatment. Feature selection can create privacy risks, and apparently neutral variables may act as proxies for protected characteristics. Models used in high-impact decisions should be audited for disparate impact, documented, monitored and subject to human oversight.

Operational models also raise governance questions. Who owns the data? Are edge weights current and auditable? What happens when a road fails or a demand forecast changes? Decisions should include sensitivity analysis, contingency planning and clear accountability. In regulated environments, records of assumptions, model versions and decision rationales are important.

10. Best Practices and Contemporary Developments

Good practice begins by defining the system boundary, vertices, edges, direction, weights and objective. Analysts should distinguish construction cost from operating cost, shortest path from minimum spanning tree, and maximum throughput from minimum cost. They should verify connectivity, check units, test boundary cases and validate results against operational knowledge.

For software implementation, adjacency lists are usually preferable for sparse graphs, while adjacency matrices can be convenient for dense graphs or direct edge lookup. Traversal algorithms should record visited vertices to prevent repeated processing. MST implementations should handle disconnected graphs explicitly: if Kruskal’s algorithm finishes with fewer than n − 1 edges, the input graph is disconnected and the result is a minimum spanning forest rather than an MST.

Contemporary applications combine graph algorithms with geographic information systems, real-time sensor data, cloud infrastructure and machine learning. Dynamic network optimization can update routes as capacities change. Graph neural networks learn from network structure, but they do not replace classical graph algorithms when exact connectivity, capacity or cost guarantees are required. Hybrid systems use learned predictions for demand or travel time and optimization algorithms for final allocation.

Chapter Summary

Trees are connected acyclic graphs with n − 1 edges and a unique path between every pair of vertices. Rooted trees represent hierarchy through parents, children, depth and height. Binary trees support expression processing and efficient organization; binary search trees provide ordered search, although their performance depends on height. Preorder, inorder, postorder and breadth-first traversals visit tree vertices in different useful sequences.

Decision trees represent tests and outcomes in AI and managerial analysis. Entropy and information gain can guide machine-learning splits, while expected monetary value supports decisions under uncertainty. Spanning trees connect every vertex with no cycles, and minimum spanning trees minimize total edge weight. Kruskal’s and Prim’s algorithms use greedy principles justified by cut and cycle properties.

Network-flow models represent directed capacity systems. Feasible flows obey capacity and conservation constraints, and the max-flow min-cut theorem links maximum throughput to a bottleneck cut. In practice, tree and network models must be combined with reliability, fairness, uncertainty, cost, privacy and governance considerations.

Key Terms

Tree: A connected undirected graph with no cycles.

Forest: A disjoint collection of trees.

Rooted tree: A tree with one designated root vertex.

Parent: The vertex immediately closer to the root.

Child: A vertex directly below a parent.

Leaf: A vertex with no children, or a degree-one vertex in a nontrivial undirected tree.

Depth: The number of edges from the root to a vertex.

Height: The greatest depth in a rooted tree.

Binary tree: A rooted tree with at most two children per vertex.

Binary search tree: A binary tree ordered so smaller keys lie left and larger keys lie right.

Traversal: A systematic process for visiting tree vertices.

Decision tree: A tree representing tests, branches and outcomes.

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

Minimum spanning tree: A spanning tree of least total edge weight.

Cut: A division of network vertices into two sets.

Capacity: The maximum permitted flow on a directed edge.

Flow conservation: Equality of inflow and outflow at intermediate vertices.

Maximum flow: The greatest feasible flow from a source to a sink.

Residual network: A network showing remaining and reversible flow capacities.

Bottleneck: A capacity limitation restricting total network throughput.

Review Questions

Short Answer Questions

1. What distinguishes a tree from a general connected graph?

2. Why does a tree with n vertices contain exactly n − 1 edges?

3. State the ordering property of a binary search tree.

4. What is the difference between a spanning tree and a minimum spanning tree?

5. What two fundamental constraints must a feasible network flow satisfy?

Long Answer Questions

1. Explain preorder, inorder, postorder and breadth-first traversal, including one practical use of each.

2. Describe binary-search-tree insertion, searching and deletion, and explain why an unbalanced tree can be inefficient.

3. Explain entropy and information gain in decision-tree learning, including the role of weighted child impurity.

4. Compare Kruskal’s and Prim’s minimum-spanning-tree algorithms in terms of method, data structures and typical use.

5. Explain the max-flow min-cut theorem and discuss its interpretation in a logistics network.

Analytical / Application Questions

1. Construct a minimum spanning tree for a weighted network of your choice, show the edge-selection process and justify why rejected edges are not needed.

2. Design a flow network for a supply chain with one source, two intermediate warehouses and two customer groups. Assign capacities, calculate a feasible flow and identify a possible bottleneck cut.

3. A decision tree used for loan approval has high accuracy but rejects applicants from one demographic group at a much higher rate. Analyze the technical, ethical and governance steps required before deployment.

Multiple Choice Questions with Answers

Question 1

A tree with 12 vertices has how many edges?

A. 10

B. 11

C. 12

D. 13

Correct Answer: B. 11

Question 2

Which traversal visits the root between the left and right subtrees?

A. Preorder

B. Breadth-first

C. Inorder

D. Postorder

Correct Answer: C. Inorder

Question 3

What is the worst-case search time in an ordinary unbalanced binary search tree with n vertices?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 4

Which structure is most directly used to test whether adding an edge in Kruskal’s algorithm creates a cycle?

A. Stack

B. Queue

C. Hash table

D. Disjoint-set union

Correct Answer: D. Disjoint-set union

Question 5

A spanning tree of a connected graph with 8 vertices contains how many edges?

A. 7

B. 8

C. 14

D. 16

Correct Answer: A. 7

Question 6

What objective does a minimum spanning tree optimize?

A. The shortest path from one source

B. The total weight connecting all vertices

C. The maximum flow between two vertices

D. The number of graph vertices

Correct Answer: B. The total weight connecting all vertices

Question 7

At an intermediate vertex in a feasible flow network, what must hold?

A. Inflow equals outflow

B. Inflow is always zero

C. Outflow must exceed inflow

D. All incident capacities must be equal

Correct Answer: A. Inflow equals outflow

Question 8

The max-flow min-cut theorem states that the maximum flow equals the:

A. Number of vertices in the network

B. Largest individual edge capacity

C. Capacity of the minimum source-sink cut

D. Total number of directed edges

Correct Answer: C. Capacity of the minimum source-sink cut

Question 9

A pure classification node has entropy:

A. 0

B. 1

C. Equal to the number of classes

D. Undefined in every case

Correct Answer: A. 0

Question 10

In the illustrative MST example with selected edge costs 1, 2 and 3, what is the total cost?

A. 3

B. 5

C. 6

D. 9

Correct Answer: C. 6