Graph Theory Basics: Definitions, Traversals, Spanning Trees & Shortest Paths

TAKEAWAYS:

• Graphs model relationships: Vertices (nodes) and edges (connections) represent real-world pairs like roads (NTC network), friendships (Facebook), or dependencies (project tasks).
• Traversals matter: Eulerian circuits (no repeats) solve delivery routes (Pathao’s bike paths), while Hamiltonian paths (visit each once) optimize sales tours.
• Spanning trees minimize cost: Kruskal’s algorithm (sort edges by weight) builds the cheapest network (e.g., Ncell’s tower connections).
• Shortest paths = efficiency: Dijkstra’s algorithm (greedy + priority queue) powers Google Maps’ turn-by-turn directions.
• Matrix representations trade space for speed: Adjacency matrices (O(V²)) excel for dense graphs; adjacency lists (O(V+E)) save space for sparse ones.
• Connectivity defines reachability: A graph’s components (isolated subgraphs) reveal bottlenecks (e.g., Kathmandu traffic zones cut off by floods).

1. Graph Basics: Definitions and Types

Graphs are mathematical structures consisting of:

• Vertices (V): Objects (e.g., cities, users).
• Edges (E): Connections between objects (e.g., roads, friendships).
• Degree: Number of edges incident to a vertex (isolated vertices have degree 0).

Types of Graphs

Key Definitions:

• Simple Graph: No loops (edges from a vertex to itself) or multiple edges between the same pair.
• Pseudograph: Allows loops and multiple edges (e.g., a graph with parallel train tracks between stations).
• Directed Graph (Digraph): Edges have direction (e.g., Twitter follows).
• Weighted Graph: Edges have numerical values (e.g., road distances in km).

2. Graph Representations

Two primary ways to store graphs in memory:

A. Adjacency Matrix

• Definition: A $V\times V$ matrix where $A[i][j]=1$ if edge $(i,j)$ exists, else $0$.
• Space: $O(V^2)$ (inefficient for sparse graphs).
• Use Case: Dense graphs (e.g., social networks where most users know each other).

Example: For a graph with vertices $A,B,C$ and edges $AB,BC,CA$:

   A  B  C
A [0,1,1]
B [1,0,1]
C [1,1,0]

B. Adjacency List

• Definition: Each vertex stores a list of adjacent vertices.
• Space: $O(V+E)$ (efficient for sparse graphs).
• Use Case: Web graphs (few edges relative to vertices).

Example:

A → [B, C]
B → [A, C]
C → [A, B]

Comparison Table:

3. Graph Traversals: Eulerian and Hamiltonian Paths

A. Eulerian Path/Circuit

• Eulerian Path: Visits every edge exactly once (no repeats).
• Eulerian Circuit: Starts and ends at the same vertex.
• Conditions:
  • Eulerian Circuit: All vertices have even degree.
  • Eulerian Path (but not circuit): Exactly two vertices have odd degree.

Real-World Example:

• Pathao’s Bike Delivery Routes: Riders plan routes that cover every street (edge) once to minimize time.
• NTC’s Power Line Inspection: Technicians walk along power lines (edges) without retracing steps.

Worked Example: Does this graph have an Eulerian circuit?

graph TD
    A --> B
    A --> C
    B --> C
    B --> D
    C --> D
    D --> A

Solution:

• Degrees: $A(3),B(3),C(3),D(3)$.
• No Eulerian circuit (all degrees odd? No—wait, actually all are odd here. Correction: For an Eulerian circuit, all degrees must be even. Here, all are odd, so no Eulerian circuit or path exists.)

B. Hamiltonian Path/Circuit

• Hamiltonian Path: Visits every vertex exactly once.
• Hamiltonian Circuit: Starts and ends at the same vertex.
• No simple degree-based condition (NP-Hard problem!).

Real-World Example:

• Salesman Problem: A Daraz delivery agent must visit all warehouses (vertices) in Kathmandu without retracing routes.
• Nepal Tourism Itinerary: Planning a trip to visit all 75 districts (vertices) via roads (edges).

Worked Example: Find a Hamiltonian path in this graph:

Solution: One possible path: $A\to B\to C\to D$.

4. Spanning Trees and Minimum Spanning Trees (MST)

A. Spanning Tree

• A subgraph that:
  • Connects all vertices.
  • Has no cycles.
  • Has exactly $V-1$ edges.

Example: For a graph with 4 vertices, a spanning tree has 3 edges.

B. Minimum Spanning Tree (MST)

• A spanning tree with the minimum total edge weight.
• Applications:
  • Designing computer networks (Ncell’s tower connections).
  • Road construction (NTC’s rural electrification).

Algorithms:

1. Kruskal’s Algorithm:
   • Sort edges by weight.
   • Add edges one by one, skipping those that form cycles (use Union-Find).
2. Prim’s Algorithm:
   • Start from any vertex, grow the tree by adding the cheapest edge to the current tree.

Worked Example (Kruskal’s): Find the MST for this graph:

Steps:

1. Sort edges: $C-D(1),A-B(1),B-C(2),A-C(4),B-D(5)$.
2. Add $C-D$, then $A-B$ (no cycle).
3. Skip $B-C$ (forms cycle $A-B-C-D$).
4. Add $A-C$ (total weight = $1+1+4=6$).

5. Shortest Path Algorithms: Dijkstra’s

• Finds the shortest path from a source to all other vertices in a weighted graph with non-negative edges.
• Steps:
  1. Initialize distances: source = 0, others = ∞.
  2. Use a priority queue to pick the vertex with the smallest tentative distance.
  3. Relax edges: update distances if a shorter path is found.

Real-World Example:

• Google Maps: Uses Dijkstra’s (or A*) to calculate the fastest route from your location to Thamel.
• Pathao’s Ride Pricing: Estimates the shortest distance to charge dynamically.

Worked Example: Find the shortest path from $A$ to $D$:

Steps:

1. Start at $A$: distances = $\{A:0,B:1,C:4,D:\infty \}$.
2. Pick $B$, update $D$ via $B$ → $D(1+5=6)$.
3. Pick $C$, update $D$ via $C$ → $D(4+1=5)$.
4. Final path: $A\to C\to D$ (total weight = 5).

In the Real World

1. Pathao’s Bike Delivery Routes:

   • Graph Theory Idea: Eulerian Paths to minimize retracing.
   • How: Riders use algorithms to plan routes covering all delivery streets (edges) once, reducing fuel costs by 20%.

2. Ncell’s Mobile Network Expansion:

   • Graph Theory Idea: Minimum Spanning Trees (MST) for tower placement.
   • How: Kruskal’s algorithm helps place cell towers (vertices) with minimal cable (edge) cost, covering all villages (vertices).

3. Google Maps (Nepal):

   • Graph Theory Idea: Dijkstra’s Shortest Path for navigation.
   • How: The app treats Kathmandu roads as a weighted graph, calculating the fastest route from your home to the airport during traffic.

4. Nepal Electricity Authority (NEA) Power Grid:

   • Graph Theory Idea: Connectivity to avoid blackouts.
   • How: The grid is modeled as a graph; removing a critical edge (e.g., a damaged transmission line) can disconnect components, causing power outages.

5. Daraz’s Order Fulfillment:

   • Graph Theory Idea: Hamiltonian Path for warehouse tours.
   • How: Robots in Daraz’s Kathmandu warehouse follow paths that pick all orders (vertices) without retracing steps, speeding up deliveries.

Exam Tip

1. Definitions First:

   • Always define terms like spanning tree, Eulerian path, and MST with examples before solving problems.
   • Example: "A spanning tree of a graph $G$ is a subgraph that includes all vertices of $G$ and is a tree (no cycles, connected)."

2. Algorithm Steps:

   • For Kruskal’s/Prim’s/Dijkstra’s, write the steps clearly and show intermediate graphs/matrices.
   • Example:

     Kruskal’s Steps:
     1. Sort edges: [(C-D,1), (A-B,1), (B-C,2), ...]
     2. Add C-D → MST = {C-D}
     3. Add A-B → MST = {C-D, A-B}
     4. Skip B-C (cycle)
     5. Add A-C → Final MST weight = 6
     

3. Connectivity Questions:

   • If asked about connectivity, draw the graph and highlight components.
   • Example: "This graph has 2 components: {A,B,C} and {D,E}."

4. Pseudocode > Full Code:

   • For Dijkstra’s, write pseudocode (not full Python/Java) to save time:

     function Dijkstra(G, source):
         dist[source] = 0
         priority_queue = all vertices with dist[v]
         while queue not empty:
             u = extract_min(queue)
             for each neighbor v of u:
                 if dist[v] > dist[u] + weight(u,v):
                     dist[v] = dist[u] + weight(u,v)
                     update queue
     

5. Common Pitfalls:

   • Eulerian vs. Hamiltonian: Don’t confuse edge traversal (Eulerian) with vertex traversal (Hamiltonian).
   • MST vs. Shortest Path: MST connects all vertices with minimal total weight; shortest path finds the best route between two vertices.
   • Negative Weights: Dijkstra’s fails with negative weights (use Bellman-Ford instead).

6. Visual Proofs:

   • For problems like "Prove this graph has no Eulerian circuit," draw the graph and label degrees.
   • Example:

     Graph: A(3), B(3), C(2)
     Since A and B have odd degrees, no Eulerian circuit exists.
     

Practice Questions (Exam-Style)

1. Define:

   • Spanning tree with an example.
   • Pseudograph with an example.

2. Algorithm Application:

   • Use Kruskal’s to find the MST of the given graph (provide weights).

3. Proof:

   • Prove whether the following graph has an Eulerian path or circuit. Justify using degree conditions.

4. Shortest Path:

   • Apply Dijkstra’s to find the shortest path from vertex 1 to vertex 5 in the weighted graph below:

     1 --2--> 2 --3--> 3
     | \       /
     4   5    6
     

5. Connectivity:

   • Identify the connected components of the given graph and state its connectivity properties.