Graph Theory Basics: Definitions, Representations, and Paths

TAKEAWAYS:

• Graphs model relationships: Vertices (nodes) and edges (connections) represent real-world objects and their interactions (e.g., roads between cities, friendships in social networks).
• Representations matter: Adjacency matrices and incidence matrices encode graphs numerically for algorithmic processing (e.g., Google’s PageRank uses adjacency matrices).
• Paths and cycles solve problems: Eulerian paths optimize delivery routes (e.g., Daraz’s courier networks), while Hamiltonian paths schedule tasks (e.g., NTC’s signal tower checks).
• Planar graphs simplify layouts: Circuit boards and city maps use planar graphs to avoid wire/road crossings (e.g., Kathmandu’s traffic planning).
• Isomorphism checks structure: Two graphs are isomorphic if they have the same "shape," useful for comparing network topologies (e.g., Ncell’s base station layouts).
• Degree and connectivity: The degree of a vertex (number of edges) determines its role in the graph (e.g., a high-degree vertex in a social network like Pathao’s driver app is a "hub").

1. What is a Graph?

A graph $G$ is a pair $(V,E)$, where:

• $V$ is a set of vertices (or nodes).
• $E$ is a set of edges connecting pairs of vertices.

Types of Graphs:

classDiagram
    class Graph {
        +V: Set of vertices
        +E: Set of edges
    }
    class DirectedGraph {
        +Edges have direction (u → v)
    }
    class UndirectedGraph {
        +Edges are bidirectional (u ↔ v)
    }
    class WeightedGraph {
        +Edges have weights (e.g., distances)
    }
    class SimpleGraph {
        +No loops, no multiple edges
    }
    class Multigraph {
        +Multiple edges allowed
    }
    class Pseudograph {
        +Loops allowed
    }
    Graph <|-- DirectedGraph
    Graph <|-- UndirectedGraph
    UndirectedGraph <|-- SimpleGraph
    UndirectedGraph <|-- Multigraph
    UndirectedGraph <|-- Pseudograph
    Graph <|-- WeightedGraph

Key Definitions:

• Vertex (Node): A fundamental unit (e.g., a city in a road network).
• Edge: A connection between two vertices (e.g., a road between cities).
• Degree of a vertex: Number of edges incident to it.
  • In directed graphs, distinguish in-degree (edges coming in) and out-degree (edges going out).
• Loop: An edge connecting a vertex to itself (allowed in pseudographs).
• Multiple edges: Parallel edges between the same pair of vertices (allowed in multigraphs).

2. Real-World Applications of Graphs

In the Real World:

1. Pathao’s Ride-Matching:

   • Graph Type: Bipartite graph (drivers on one side, riders on the other).
   • Idea Used: Matching (assigning riders to drivers) maximizes efficiency using graph algorithms like the Hungarian algorithm.
   • Example: When you request a ride, Pathao’s system models drivers and riders as vertices and matches them via shortest-path edges (time/distance).

2. NTC’s Signal Tower Network:

   • Graph Type: Planar weighted graph (towers as vertices, signal ranges as weighted edges).
   • Idea Used: Minimum Spanning Tree (MST) ensures all towers are connected with minimal cable cost.
   • Example: NTC uses Kruskal’s algorithm to design signal coverage with the least fiber optic cable.

3. Daraz’s Order Fulfillment:

   • Graph Type: Directed weighted graph (warehouses as vertices, shipment routes as edges with delivery times).
   • Idea Used: Shortest path algorithms (Dijkstra’s) to route orders from warehouses to customers fastest.
   • Example: Your Daraz order from Pokhara to Kathmandu is routed via the quickest path, calculated using graph theory.

3. Representing Graphs

Graphs can be represented in three primary ways:

(A) Graphical Representation (Diagrams)

graph TD
    A["Vertex 1"] -- "Edge 1" --> B["Vertex 2"]
    A -- "Edge 2" --> C["Vertex 3"]
    B -- "Edge 3" --> C

Advantages:

• Intuitive for visualization (e.g., road maps, social networks).
• Easy to understand connections.

Disadvantages:

• Scalability issues for large graphs (e.g., Ncell’s nationwide base station network).

(B) Adjacency Matrix

For a graph $G=(V,E)$ with $n$ vertices, the adjacency matrix $A$ is an $n\times n$ matrix where:

• $A[i][j]=1$ if there’s an edge from vertex $i$ to $j$.
• $A[i][j]=0$ otherwise.
• For weighted graphs, $A[i][j]=\text{weight}$.

Example: Undirected graph with vertices $\{1,2,3\}$ and edges $(1,2),(2,3)$:

Adjacency Matrix:
|   | 1 | 2 | 3 |
|---|---|---|---|
|1 | 0 | 1 | 0 |
|2 | 1 | 0 | 1 |
|3 | 0 | 1 | 0 |

For Directed Graphs:

• $A[i][j]=1$ if edge $i\to j$ exists.
• In-degree of vertex $i$: Sum of column $i$.
• Out-degree of vertex $i$: Sum of row $i$.

Example: Directed graph with edges $(1\to 2),(2\to 3),(3\to 1)$:

|   | 1 | 2 | 3 |
|---|---|---|---|
|1 | 0 | 1 | 0 |
|2 | 0 | 0 | 1 |
|3 | 1 | 0 | 0 |

• In-degree of 1: 1 (edge from 3).
• Out-degree of 2: 1 (edge to 3).

Advantages:

• Easy to implement in code (e.g., Google’s PageRank uses adjacency matrices).
• Matrix operations (e.g., multiplication) can compute paths.

Disadvantages:

• Space-inefficient for sparse graphs (e.g., $1000\times 1000$ matrix for 10 edges).

(C) Incidence Matrix

For a graph $G=(V,E)$, the incidence matrix $M$ has rows for vertices and columns for edges:

• $M[i][j]=1$ if vertex $i$ is incident to edge $j$.
• $M[i][j]=0$ otherwise.

Example: Undirected graph with vertices $\{1,2,3\}$ and edges $e_1=(1,2),e_2=(2,3)$:

Incidence Matrix:
|   | e1 | e2 |
|---|----|----|
|1  |  1 |  0 |
|2  |  1 |  1 |
|3  |  0 |  1 |

For Directed Graphs:

• $M[i][j]=+1$ if edge $j$ leaves vertex $i$.
• $M[i][j]=-1$ if edge $j$ enters vertex $i$.

Example: Directed edges $e_1=(1\to 2),e_2=(2\to 3)$:

|   | e1 | e2 |
|---|----|----|
|1  | -1 |  0 |
|2  | +1 | -1 |
|3  |  0 | +1 |

Advantages:

• Useful for network flow problems (e.g., traffic routing in Kathmandu).
• Helps in detecting cycles (sum of rows/columns must be zero for Eulerian circuits).

Disadvantages:

• Less intuitive for pathfinding compared to adjacency matrices.

4. Special Types of Graphs

(A) Paths and Cycles

• Path: A sequence of vertices where each adjacent pair is connected by an edge (e.g., $1\to 2\to 3$).
• Cycle: A path that starts and ends at the same vertex (e.g., $1\to 2\to 3\to 1$).

Example: In a wheel graph $W_3$ (3 outer vertices + 1 center):

graph TD
    C["Center"] -- "Edge" --> A["Vertex 1"]
    C -- "Edge" --> B["Vertex 2"]
    C -- "Edge" --> D["Vertex 3"]
    A -- "Edge" --> B
    B -- "Edge" --> D
    D -- "Edge" --> A

(B) Eulerian and Hamiltonian Graphs

Worked Example: Eulerian Path in a Graph Problem: Does the following graph have an Eulerian path?

graph TD
    A["1"] -- "Edge" --> B["2"]
    A -- "Edge" --> C["3"]
    B -- "Edge" --> C
    B -- "Edge" --> D["4"]
    C -- "Edge" --> D

Solution:

1. Count degrees:
   • $\mathrm{deg}(1)=2$ (even)
   • $\mathrm{deg}(2)=3$ (odd)
   • $\mathrm{deg}(3)=3$ (odd)
   • $\mathrm{deg}(4)=2$ (even)
2. Two vertices (2 and 3) have odd degree → Eulerian path exists (but not a circuit).
3. Start at vertex 2 or 3 (the odd-degree vertices).

(C) Planar Graphs

A graph is planar if it can be drawn on a plane without edge crossings. Examples:

• Planar: $K_4$ (complete graph on 4 vertices), wheel graphs.
• Non-planar: $K_5$ (complete graph on 5 vertices), utility graphs.

Real-World Use: Circuit board design (e.g., smartphone motherboards avoid wire crossings). Test for Planarity: Kuratowski’s Theorem (if a graph contains $K_5$ or $K_{3,3}$ as a minor, it’s non-planar).

5. Graph Isomorphism

Two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there’s a bijection $f:V_1\to V_2$ such that:

• $(u,v)\in E_1$ iff $(f(u),f(v))\in E_2$.

Invariants for Isomorphism (if two graphs differ in these, they’re not isomorphic):

1. Degree sequence: Multiset of vertex degrees must match.
2. Number of vertices/edges.
3. Connectivity: Both must be connected or disconnected similarly.
4. Presence of subgraphs (e.g., triangles, bridges).

Example: Are these graphs isomorphic?

graph TD
    subgraph Graph 1
        A["1"] -- "Edge" --> B["2"]
        A -- "Edge" --> C["3"]
        B -- "Edge" --> C
    end
    subgraph Graph 2
        X["1"] -- "Edge" --> Y["2"]
        X -- "Edge" --> Z["3"]
        Y -- "Edge" --> Z
    end

Solution:

• Both have 3 vertices, 3 edges, and degree sequence [2, 2, 2].
• Yes, they are isomorphic (e.g., $f(1)=X,f(2)=Y,f(3)=Z$).

6. Worked Example: Spanning Trees in a Wheel Graph

Problem: How many spanning trees does $W_3$ (wheel graph with 3 outer vertices) have? Solution:

1. Wheel Graph $W_3$:

   graph TD
       C["Center"] -- "Edge" --> A["Vertex 1"]
       C -- "Edge" --> B["Vertex 2"]
       C -- "Edge" --> D["Vertex 3"]
       A -- "Edge" --> B
       B -- "Edge" --> D
       D -- "Edge" --> A

2. Spanning Tree: A subgraph with all vertices and no cycles.
3. Kirchhoff’s Theorem: Number of spanning trees $=$ any cofactor of the Laplacian matrix.
   • Laplacian Matrix $L=D-A$, where $D$ is the degree matrix, $A$ is the adjacency matrix.
   • For $W_3$:
     • Degrees: $\mathrm{deg}(C)=3$, $\mathrm{deg}(A)=\mathrm{deg}(B)=\mathrm{deg}(D)=3$.
     • Adjacency matrix $A$:

       |   | C | A | B | D |
       |---|---|---|---|---|
       |C  | 0 | 1 | 1 | 1 |
       |A  | 1 | 0 | 1 | 1 |
       |B  | 1 | 1 | 0 | 1 |
       |D  | 1 | 1 | 1 | 0 |
       

     • Degree matrix $D$:

       |   | C | A | B | D |
       |---|---|---|---|---|
       |C  | 3 | 0 | 0 | 0 |
       |A  | 0 | 3 | 0 | 0 |
       |B  | 0 | 0 | 3 | 0 |
       |D  | 0 | 0 | 0 | 3 |
       

     • Laplacian $L=D-A$:

       |   | C | A | B | D |
       |---|---|---|---|---|
       |C  | 3 |-1 |-1 |-1 |
       |A  |-1 | 3 |-1 |-1 |
       |B  |-1 |-1 | 3 |-1 |
       |D  |-1 |-1 |-1 | 3 |
       

4. Delete any row/column (e.g., row/column for $D$) and compute the determinant of the remaining $3\times 3$ matrix:

   | 3 |-1 |-1 |
   |-1 | 3 |-1 |
   |-1 |-1 | 3 |
   

   • Determinant $=3(9-1)-(-1)(-3+1)+(-1)(1+3)=24-2-4=18$.
5. Number of spanning trees = 18.

Real-World Tie-In: Ncell’s base station redundancy uses spanning trees to ensure backup paths if one tower fails.

Exam Tip

1. Definitions First: Always define terms precisely (e.g., "A graph is planar if..."). Examiners deduct marks for vague answers.
2. Graph Representations:
   • For adjacency matrices, practice converting between graphical and matrix forms.
   • For incidence matrices, remember directed graphs use $+1$ and $-1$.
3. Isomorphism Checks:
   • Compare degree sequences and number of edges first.
   • Draw the graphs to visualize bijections.
4. Special Graphs:
   • Eulerian/Hamiltonian: State conditions clearly (e.g., "All vertices must have even degree for an Eulerian circuit").
   • Planar graphs: Know $K_5$ and $K_{3,3}$ are non-planar.
5. Worked Examples:
   • For spanning trees, use Kirchhoff’s theorem but show the Laplacian matrix steps.
   • For paths/cycles, trace them explicitly (e.g., "Path: 1 → 2 → 3 → 4").
6. Real-World Links:
   • Connect Eulerian paths to delivery routes (Daraz, NTC).
   • Link Hamiltonian cycles to tourist itineraries or bank loan schedules.
   • Use planar graphs for circuit board or city map examples.

Visual Summary:

mindmap
  root((Graph Theory Basics))
    Representations
      Adjacency Matrix
      Incidence Matrix
      Graphical Diagram
    Special Graphs
      Eulerian
      Hamiltonian
      Planar
    Isomorphism
      Degree Sequence
      Bijection
    Applications
      Pathao (Matching)
      NTC (Signal Towers)
      Daraz (Routing)