Graph Theory Basics: Definitions, Types, and Representations

TAKEAWAYS:

• A graph is a mathematical structure consisting of vertices (nodes) and edges connecting pairs of vertices, used to model real-world relationships like social networks or transportation routes.
• Directed graphs (digraphs) and undirected graphs differ in edge orientation, with applications in routing (e.g., Pathao’s ride allocation) and dependency tracking (e.g., course prerequisites).
• Connectivity determines if a graph is fully traversable, critical for designing efficient networks like NTC’s fiber-optic backbone or Ncell’s mobile towers.
• Isomorphism checks if two graphs have identical structures, useful in cryptography (e.g., verifying network topologies) and game theory (e.g., puzzle symmetries).
• Adjacency matrices/lists encode graph data for algorithms, enabling pathfinding (e.g., Google Maps) and social media friend recommendations.
• Bipartite graphs model pairwise relationships (e.g., Daraz’s order-fulfillment queues), while trees optimize hierarchical data (e.g., file systems in computers).

1. Introduction to Graphs

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

• $V$ is a finite set of vertices (or nodes).
• $E$ is a set of edges, which are 2-element subsets of $V$ (for undirected graphs) or ordered pairs $(u,v)$ (for directed graphs).

Types of Graphs

A -- B
| \ |
|  \|
C --

1 → 2 → 3
 \      /
   \    /
     1

Key Definitions

• Degree of a Vertex: Number of edges incident to it.
  • In undirected graphs: $\mathrm{deg}(v)=$ number of edges connected to $v$.
  • In directed graphs:
    • In-degree: Number of edges entering $v$.
    • Out-degree: Number of edges leaving $v$.
• Path: A sequence of edges connecting a sequence of vertices (e.g., $v_1,v_2,\dots ,v_k$).
• Cycle: A path that starts and ends at the same vertex with no repeated edges/vertices (except the start/end).
• Connected Graph: There is a path between every pair of vertices.
• Complete Graph: Every pair of distinct vertices is connected by a unique edge (denoted $K_n$ for $n$ vertices).

Worked Example: Degrees and Edges Given an undirected graph $G$ with vertices $\{v_1,v_2,v_3,v_4\}$ and adjacency matrix:

0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Find:

1. The degree of each vertex.
2. The total number of edges.

Solution:

1. Degrees are the row/column sums (excluding diagonal zeros):
   • $\mathrm{deg}(v_1)=2$ (edges to $v_2,v_3$),
   • $\mathrm{deg}(v_2)=3$ (edges to $v_1,v_3,v_4$),
   • $\mathrm{deg}(v_3)=3$,
   • $\mathrm{deg}(v_4)=2$.
2. Total edges = $\frac{1}{2}\sum \mathrm{deg}(v)=\frac{2+3+3+2}{2}=5$.

2. Representations of Graphs

Graphs can be represented using:

1. Adjacency Matrix: A square matrix $A$ where $A_{ij}=1$ if $(i,j)\in E$, else $0$.
   • Useful for dense graphs (many edges).
   • Example for the graph above:

     [[0,1,1,0],
      [1,0,1,1],
      [1,1,0,1],
      [0,1,1,0]]
     

2. Adjacency List: A list of lists where each vertex points to its neighbors.
   • Example:

     v1: v2, v3
     v2: v1, v3, v4
     v3: v1, v2, v4
     v4: v2, v3
     

   • Space-efficient for sparse graphs.

Comparison Table: Adjacency Matrix vs. List

3. Special Graphs

Bipartite Graphs

• A graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$.
• Example:

  U: [A, B]
  V: [1, 2, 3]
  Edges: A-1, A-2, B-2, B-3
  

• Property: No odd-length cycles (e.g., 3-cycle $A-1-B-2-A$ is invalid).
• Proof that odd cycles imply non-bipartiteness: Assume a bipartite graph has an odd cycle. Alternate colors (say, red/blue) vertices. The cycle must end on the same color as it started, but odd-length cycles require alternating colors to mismatch. Contradiction.

A -- 1
| \  |
|  \ |
B -- 2 -- 3

Trees

• A connected acyclic graph.
• Properties:
  • Exactly $n-1$ edges for $n$ vertices.
  • No cycles; exactly one path between any two vertices.
• Applications:
  • File systems (directories as nodes, subdirectories as children).
  • Organizational hierarchies (e.g., company reporting structures).

      A
     / \
    B   C
   /
  D

Graph Isomorphism

• Two graphs $G$ and $H$ are isomorphic if there exists a bijection $f:V(G)\to V(H)$ such that $(u,v)\in E(G)$ iff $(f(u),f(v))\in E(H)$.
• Example: Let $G$ and $H$ be graphs with:
  • $V(G)=\{a,b,c,d\}$, $E(G)=\{\{a,b\},\{b,c\},\{c,d\},\{d,a\}\}$.
  • $V(H)=\{1,2,3,4\}$, $E(H)=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$.
  • Isomorphism: $f(a)=1,f(b)=2,f(c)=3,f(d)=4$. Both are 4-cycles, so they are isomorphic.

Mermaid Diagram: Graph Isomorphism Check

graph TD
    subgraph G["Graph G"]
        A["a"] --> B["b"]
        B --> C["c"]
        C --> D["d"]
        D --> A
    end
    subgraph H["Graph H"]
        1["1"] --> 2["2"]
        2 --> 3["3"]
        3 --> 4["4"]
        4 --> 1
    end
    G -->|"f(a)=1, f(b)=2, f(c)=3, f(d)=4"| H

4. Directed Graphs

• Source Vertex: A vertex with out-degree $>0$ and in-degree $=0$.
• Sink Vertex: A vertex with in-degree $>0$ and out-degree $=0$.
• Applications:
  • Pathao: Drivers (sources) allocate rides to passengers (sinks).
  • Course Prerequisites: Math 101 (source) → Math 102 (sink).

S → A → B → T

5. Connectedness

• Connected Graph: There is a path between every pair of vertices.
• Disconnected Graph: At least one pair of vertices has no path.
• Applications:
  • NTC’s Network: If two towers are not connected, calls drop (disconnected).
  • Social Networks: If two users have no mutual friends, they are disconnected.

Mermaid Diagram: Connected vs. Disconnected Graphs

In the Real World

1. Pathao’s Ride Allocation:

   • Idea: Directed graph where drivers (sources) allocate rides to passengers (sinks).
   • How: The app models supply (drivers) and demand (passengers) as a flow network, optimizing routes using shortest-path algorithms (e.g., Dijkstra’s) on weighted graphs.

2. Daraz’s Order Fulfillment:

   • Idea: Bipartite graph where one set is orders and the other is warehouses.
   • How: Orders are matched to the nearest warehouse (edges represent delivery routes), ensuring minimal transit time. Bipartite graphs help avoid conflicts where a single warehouse cannot fulfill multiple orders simultaneously.

3. NEPSE’s Stock Market Correlations:

   • Idea: Weighted graph where vertices are stocks and edges are correlation coefficients.
   • How: Traders use adjacency matrices to identify high-correlation stocks (e.g., Ncell and NTC shares often move together) for portfolio diversification or risk assessment.

Worked Example: Graph Isomorphism

Question: Determine if the following two graphs are isomorphic.

• $G$: Vertices $\{a,b,c,d\}$, edges $\{\{a,b\},\{b,c\},\{c,d\}\}$.
• $H$: Vertices $\{1,2,3,4\}$, edges $\{\{1,2\},\{2,3\},\{3,4\}\}$.

Solution:

1. Check Degrees:
   • $G$: $\mathrm{deg}(a)=1,\mathrm{deg}(b)=2,\mathrm{deg}(c)=2,\mathrm{deg}(d)=1$.
   • $H$: $\mathrm{deg}(1)=1,\mathrm{deg}(2)=2,\mathrm{deg}(3)=2,\mathrm{deg}(4)=1$. Degrees match, so isomorphism is possible.
2. Construct Bijection:
   • Map $a\to 1$, $b\to 2$, $c\to 3$, $d\to 4$.
   • Verify edges: $\{a,b\}\to \{1,2\}$, $\{b,c\}\to \{2,3\}$, $\{c,d\}\to \{3,4\}$.
   • Conclusion: $G$ and $H$ are isomorphic (both are "path graphs" of length 3).

Exam Tip

1. Definitions: Always recall definitions precisely (e.g., "a bipartite graph has no odd cycles"). Partial credit is lost for vague answers like "a graph with two parts."
2. Visualization: Draw graphs for isomorphism proofs. Even if the question doesn’t ask, sketching helps you see patterns (e.g., cycles, trees).
3. Adjacency Matrix/Lists: Practice converting between the two representations quickly. For example, given a matrix, list the edges; given a list, construct the matrix.
4. Proofs: For statements like "a graph with an odd cycle is not bipartite," use contradiction or coloring arguments. Show your steps clearly.
5. Real-World Tie-Ins: Relate graph concepts to apps you use daily (e.g., "Why is Pathao’s ride system a directed graph?").
6. Time Management: Spend 10 minutes per question. For isomorphism, start by checking degrees before attempting bijections.