Unit 6: Shortest Paths & Trees - Subjective Questions

Labelled Graph:

A labelled graph is a graph in which each vertex and/or edge is assigned a label (a name, symbol, or identifier). The labels are used to distinguish vertices and edges from one another.

• Labels may be alphabets, numbers, or any symbols.
• Example: A graph with vertices labelled and edges labelled .

Weighted Graph:

A weighted graph is a special type of labelled graph in which each edge is assigned a numerical value called a weight (or cost). This weight typically represents distance, cost, time, or capacity.

• Formally, a weighted graph is where assigns a weight to each edge.
• Example: A road network where vertices are cities and edge weights are distances between them.

Difference:

Thus, every weighted graph is a labelled graph, but not every labelled graph is weighted.

Shortest Path:

In a weighted graph, the shortest path between two vertices and is the path for which the sum of the weights of its constituent edges is minimized.

• If is a path, its total weight is:
  
• The shortest path is the path that minimizes .

Key Points:

• There may be multiple shortest paths between two vertices.
• Shortest path is defined only when the graph is connected (for the given pair).
• In graphs with negative weight cycles, the shortest path may not exist.

Importance / Applications:

• Navigation systems (GPS): finding the shortest driving route.
• Network routing: determining the fastest data transmission path.
• Transportation & logistics: minimizing delivery cost/time.
• Telecommunications: optimal signal routing.
• Robotics: path planning for movement.

Finding the shortest path helps optimize resources such as time, distance, and cost, making it fundamental in computer science and operations research.

Dijkstra's Algorithm:

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Basic Idea: It uses a greedy approach, repeatedly selecting the unvisited vertex with the smallest tentative distance and updating its neighbours.

Step-by-Step Procedure:

1. Initialization:

   • Assign distance to the source vertex and to all other vertices.
   • Mark all vertices as unvisited.

2. Set current vertex as the source.

3. Relaxation: For the current vertex, consider all unvisited neighbours. Calculate tentative distance:
   
   Update if a shorter path is found.

4. Mark visited: Once all neighbours are considered, mark the current vertex as visited. A visited vertex is never checked again.

5. Select next vertex: Choose the unvisited vertex with the smallest tentative distance as the new current vertex.

6. Repeat steps 3–5 until all vertices are visited (or the destination is reached).

Time Complexity:

• Using adjacency matrix:
• Using min-heap + adjacency list:

Limitation: Does not work correctly with negative edge weights.

Given Edges:

• , , , , , ,

Step 1 — Initialization:

Step 2 — Visit A (dist 0):

Step 3 — Visit C (dist 1, smallest):

Step 4 — Visit B (dist 3):

Step 5 — Visit D (dist 8):

Step 6 — Visit E (dist 11): All vertices visited.

Final Shortest Distances from A:

Definition:

A tree is a connected acyclic graph (a connected graph with no cycles). In other words, it is a graph in which any two vertices are connected by exactly one path.

Important Properties of a Tree:

• Connectivity: A tree is always connected.
• Acyclic: A tree contains no cycles.
• Edge count: A tree with vertices has exactly edges.
• Unique path: There is exactly one simple path between any two vertices.
• Minimally connected: Removing any edge disconnects the tree.
• Maximally acyclic: Adding any edge creates exactly one cycle.
• Leaves: A tree with at least two vertices has at least two leaf nodes (vertices of degree 1).

Example:

A graph with 5 vertices and 4 edges forming no cycle is a tree.

Note: A disconnected graph whose components are all trees is called a forest.

Rooted Tree:

A rooted tree is a tree in which one vertex is designated as the root, and every edge is implicitly directed away from the root. This establishes a hierarchical structure.

Terminology:

• Root: The topmost node with no parent; the starting point of the tree.
• Parent: A node that has one or more nodes directly below it (immediate predecessor).
• Child: A node directly connected below another node (immediate successor).
• Sibling: Nodes that share the same parent.
• Leaf (Terminal node): A node with no children.
• Internal node (Non-terminal): A node that has at least one child.
• Level: The distance (number of edges) from the root to a node. The root is at level .
• Height (Depth): The length of the longest path from the root to any leaf.
• Ancestor / Descendant: Nodes on the path towards the root / away from the root respectively.

Example:

If is the root with children and , and has children :

• = root, = children of and siblings, = children of (siblings), leaves = .
• Height = 2.

Definition:

A binary tree is a rooted tree in which every node has at most two children, referred to as the left child and the right child.

Types of Binary Trees:

• Full (Proper) Binary Tree: Every node has either or children.
• Complete Binary Tree: All levels are completely filled except possibly the last, which is filled from left to right.
• Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level.
• Skewed Binary Tree: Every node has only one child (left-skewed or right-skewed).
• Balanced Binary Tree: The height difference between left and right subtrees of every node is at most 1.

Important Properties:

• Maximum number of nodes at level is .
• Maximum number of nodes in a binary tree of height is .
• A binary tree with nodes has height at least .
• In a full binary tree with internal nodes, the number of leaves is .

Applications: Expression trees, binary search trees, heaps, Huffman coding.

Statement: A tree with vertices has exactly edges.

Proof (by Mathematical Induction on the number of vertices ):

Base Case ():
A tree with a single vertex has no edges. So the number of edges is . Hence the statement holds.

Inductive Hypothesis:
Assume that every tree with vertices has exactly edges, for all trees having up to vertices.

Inductive Step ():
Consider a tree with vertices.

• Since is a tree (connected and acyclic), it must contain at least one leaf vertex (a vertex of degree 1).
• Remove and its single incident edge from . The resulting graph has vertices.
• is still connected and acyclic (removing a leaf does not create disconnection or cycles), so is a tree with vertices.
• By the inductive hypothesis, has edges.
• Adding back vertex and its one edge gives:
  

Thus with vertices has edges.

Conclusion: By the principle of mathematical induction, a tree with vertices has exactly edges.

Definition:

A spanning tree of a connected graph is a subgraph that:

• Includes all the vertices of , and
• Is a tree (connected and acyclic).

In simple words, a spanning tree connects all vertices of the graph using the minimum number of edges without forming any cycle.

Properties:

• A spanning tree of a graph with vertices has exactly edges.
• A connected graph may have multiple spanning trees.
• Removing any one edge from a spanning tree disconnects it.
• Adding any one edge to a spanning tree creates exactly one cycle.
• A spanning tree is a maximal set of edges with no cycle and a minimal set of edges keeping the graph connected.
• The number of spanning trees of a complete graph is (Cayley's formula).

Example:

For a graph with vertices and edges (a triangle):

• Possible spanning trees: , , .
• Each has edges and covers all 3 vertices without a cycle.

Definition:

A Minimum Spanning Tree (MST) of a connected weighted graph is a spanning tree whose total edge weight is the minimum among all possible spanning trees of .

• If is a spanning tree, its weight is:
  
• The MST is the spanning tree that minimizes .

Key Points:

• An MST contains exactly edges for vertices.
• If all edge weights are distinct, the MST is unique.
• If some weights are equal, there may be multiple MSTs.
• Two popular algorithms to find MST are Kruskal's and Prim's algorithms.

Significance / Applications:

• Network design: laying minimum-cost cables, pipelines, or roads.
• Electrical circuits: minimizing wiring cost.
• Cluster analysis: in data mining and machine learning.
• Approximation algorithms: for problems like the Travelling Salesman Problem.
• Computer networks: designing efficient LAN/WAN topologies.

The MST helps connect all points at the least total cost, making it fundamental in optimization.

Kruskal's Algorithm:

Kruskal's algorithm builds the MST by selecting edges in increasing order of weight, ensuring no cycle is formed. It follows a greedy edge-based approach.

Step-by-Step Procedure:

1. Sort all the edges of the graph in non-decreasing order of their weights.
2. Initialize the MST as an empty set of edges.
3. Pick the smallest edge not yet considered.
4. Check for a cycle: If adding this edge to the MST forms a cycle, discard it; otherwise, include it.
   • Cycle detection is done efficiently using the Union-Find (Disjoint Set) data structure.
5. Repeat step 3–4 until the MST contains exactly edges (where = number of vertices).
6. The resulting set of edges forms the Minimum Spanning Tree.

Time Complexity:

• Sorting edges:
• Union-Find operations: nearly
• Overall: or equivalently .

Best suited for: Sparse graphs (fewer edges).

Prim's Algorithm:

Prim's algorithm builds the MST by growing it one vertex at a time, starting from an arbitrary vertex and always adding the minimum weight edge connecting the tree to a new vertex. It uses a greedy vertex-based approach.

Step-by-Step Procedure:

1. Select an arbitrary starting vertex and add it to the MST set.
2. Initialize the MST with this single vertex.
3. Find the minimum weight edge that connects a vertex in the MST to a vertex outside the MST.
4. Add that edge and the new vertex to the MST.
5. Repeat steps 3–4 until all vertices are included in the MST (i.e., edges are added).
6. The resulting tree is the Minimum Spanning Tree.

Time Complexity:

• Using adjacency matrix:
• Using binary heap + adjacency list:
• Using Fibonacci heap:

Best suited for: Dense graphs (many edges).

Comparison of Kruskal's and Prim's Algorithms:

Common Points:

• Both are greedy algorithms.
• Both produce an MST with exactly edges.
• Both give the same total minimum weight (though the trees may differ if weights repeat).

Given Edges (with weights):
, , , , , ,

Step 1 — Sort edges in increasing order:

Step 2 — Add edges avoiding cycles (need edges):

• Add → Tree: {A, B} ✓
• Add → Tree: {A,B}, {C,E} ✓
• Add → connects {A,B} and {C,E} ✓ → {A,B,C,E}
• → both in same set → cycle, discard ✗
• Add → adds D ✓ → {A,B,C,D,E}

Now we have 4 edges and all 5 vertices are connected.

Minimum Spanning Tree Edges:

Total Minimum Weight:

Given Edges:
, , , , , ,

Start from vertex A. MST = {A}

Step 1: Edges from {A}: , . Choose min = .

• MST = {A, B}, Edges:

Step 2: Edges from {A,B}: , , . Choose min = .

• MST = {A, B, C}, Edges: ,

Step 3: Edges from {A,B,C}: , , . Choose min = .

• MST = {A, B, C, D}, Edges: , ,

Step 4: Edges to new vertex E: , . Choose min = .

• MST = {A, B, C, D, E}, Edges: , , ,

Minimum Spanning Tree Edges:

Total Minimum Weight:

Shortest Path vs Minimum Spanning Tree:

Key Conceptual Difference:

• Dijkstra's algorithm optimizes individual path lengths from a source. The path from A to B is the cheapest route between those two points.
• MST algorithms optimize the overall network cost, ensuring every vertex is connected with least total weight — but the path between two vertices in an MST is not necessarily the shortest path.

Example Insight:

An edge that is part of an MST may not lie on the shortest path between two vertices, and vice versa. The two solve fundamentally different optimization problems.

Tree Traversal:

Traversal means visiting every node of a tree exactly once in a systematic order. For binary trees, three common depth-first traversals are used.

1. Preorder Traversal (Root → Left → Right):

• Visit the root node first.
• Traverse the left subtree.
• Traverse the right subtree.

2. Inorder Traversal (Left → Root → Right):

• Traverse the left subtree.
• Visit the root node.
• Traverse the right subtree.
• (For a BST, this gives nodes in sorted order.)

3. Postorder Traversal (Left → Right → Root):

• Traverse the left subtree.
• Traverse the right subtree.
• Visit the root node last.

Example:

Consider the binary tree:

    A
   / \
  B   C
 / \
D   E

• Preorder: A, B, D, E, C
• Inorder: D, B, E, A, C
• Postorder: D, E, B, C, A

Applications:

• Preorder → copying a tree, prefix expression.
• Inorder → retrieving sorted data from BST.
• Postorder → deleting a tree, postfix expression.

Reason for Failure:

Dijkstra's algorithm is based on a greedy assumption: once a vertex is marked as visited (with its shortest distance finalized), that distance is never updated again. This works only if edge weights are non-negative, because adding more edges can only increase the path length.

With negative edge weights, a later path through a negative edge could produce a shorter distance to an already-finalized vertex — but the algorithm never re-examines it, leading to an incorrect result.

Example:

Consider vertices with edges:

Applying Dijkstra from A:

1. , , .
2. Smallest unvisited is → B finalized as 5.
3. Visit → relaxes : .

The actual shortest distance to B is (via ), but Dijkstra had already finalized and does not correct it.

Conclusion:

Because Dijkstra finalizes vertices greedily, it produces wrong answers with negative weights. Algorithms like Bellman-Ford are used instead, as they can handle negative edges (and detect negative cycles).

Relationship between Graph and Spanning Tree:

• A spanning tree is a subgraph derived from a connected graph .
• It contains all vertices of but only a subset of edges ( edges) such that no cycle exists.
• A spanning tree is obtained by removing edges that form cycles while keeping the graph connected.

Number of Spanning Trees:

• A connected graph can have more than one spanning tree.
• The exact number depends on the structure of the graph.
• For a complete graph , the number of spanning trees is given by Cayley's Formula:
  

Example:

• For (triangle): spanning trees.
• For : spanning trees.
• For : spanning trees.

General Counting (Kirchhoff's Theorem / Matrix-Tree Theorem):

For an arbitrary connected graph, the number of spanning trees equals any cofactor of the Laplacian matrix , where is the degree matrix and is the adjacency matrix.

Key Point: More edges (and higher connectivity) generally lead to a larger number of possible spanning trees.

Statement: A graph with vertices is a tree if and only if it is connected and has exactly edges.

We prove both directions.

Part 1: If is a tree, then it is connected with edges.

• By definition, a tree is connected.
• It is a standard result (proved by induction) that a tree with vertices has exactly edges.
• Hence, a tree is connected and has edges. ✓

Part 2: If is connected with edges, then is a tree.

We must show is acyclic.

• Suppose, for contradiction, that contains a cycle.
• We can remove one edge from the cycle; the graph remains connected (since a cycle edge is not a bridge).
• Repeat this until no cycle remains. The resulting graph is connected and acyclic, i.e., a tree.
• A tree on vertices has exactly edges, so has edges.
• But we removed at least one edge, so the original had more than edges, contradicting our assumption that has exactly edges.
• Therefore, contains no cycle.

Since is connected and acyclic, is a tree. ✓

Conclusion: is a tree is connected and has edges.