Special Graph Topics: Matching, Coloring, Flows & Cryptography

TAKEAWAYS:

• Matching pairs vertices optimally (e.g., stable marriage problems) and can be solved via augmenting paths in bipartite graphs.
• Graph coloring minimizes colors for vertex/edge coloring (e.g., map coloring, exam scheduling) using greedy or backtracking algorithms.
• Network flows model resource allocation (e.g., traffic, data packets) with max-flow/min-cut theorem as the core principle.
• Cryptography uses modular arithmetic (RSA) and graph theory (e.g., error-correcting codes) to secure digital communications.
• Planar graphs and Euler’s formula ($V-E+F=2$) solve real-world layout problems (e.g., circuit boards, city planning).
• Applications span logistics (Pathao’s route optimization), finance (NEPSE’s transaction networks), and tech (Google’s PageRank).

1. Matching in Graphs

Definition: A matching is a set of edges without common vertices. A perfect matching covers all vertices; a maximum matching is the largest possible.

Key Concepts

• Bipartite Graphs: Graphs with two disjoint vertex sets $U$ and $V$. Matching here is called bipartite matching.
• Augmenting Path: A path alternating between matched and unmatched edges, used to find larger matchings.
• Hall’s Marriage Theorem: A bipartite graph has a perfect matching iff for every subset $S\subseteq U$, $|N(S)|\ge |S|$, where $N(S)$ is the neighborhood of $S$.

Example: Stable Marriage Problem

Scenario: Match $n$ men to $n$ women based on preferences (e.g., Daraz’s order-pairing system). Algorithm: Gale-Shapley’s algorithm (propose-reject cycle). Visual:

graph LR
    M1["Man 1"] -->|"proposes"| W1["Woman 1"]
    M1 -->|"proposes"| W2["Woman 2"]
    W2 -->|"rejects"| M1
    M1 -->|"proposes"| W3["Woman 3"]
    W3 -->|"accepts"| M1

Worked Example: Given preferences:

• Men: $M_1>M_2>M_3$, $M_2>M_1>M_3$, $M_3>M_1>M_2$.
• Women: $W_1>W_2>W_3$, $W_2>W_3>W_1$, $W_3>W_1>W_2$. Steps:

1. $M_1$ proposes to $W_1$ → matched.
2. $M_2$ proposes to $W_2$ → matched.
3. $M_3$ proposes to $W_3$ → matched. Result: Perfect matching $(M_1,W_1),(M_2,W_2),(M_3,W_3)$.

2. Graph Coloring

Definition: Assign colors to vertices/edges so no adjacent vertices/edges share the same color. The chromatic number $\chi (G)$ is the minimum colors needed.

Types

Algorithms

• Greedy Coloring: Assign the smallest available color to each vertex in order. Pseudocode:

  def greedy_coloring(G):
      color = {}
      for u in sorted(G.vertices):
          used = {color[v] for v in G.adj[u] if color[v] is not None}
          color[u] = min(set(range(1, len(G.vertices)+1)) - used)
      return color
  

• Backtracking: Try all color assignments recursively (used for small graphs).

Real-World Example: Exam Scheduling (TU)

Problem: Schedule exams for 5 courses with 3 time slots, minimizing conflicts. Graph: Vertices = courses, edges = conflicts. Solution: $\chi (G)=3$ (minimum slots needed). Visual:

graph TD
    C1["Course 1"] --> C2["Course 2"]
    C1 --> C3["Course 3"]
    C2 --> C4["Course 4"]
    C3 --> C4
    C4 --> C5["Course 5"]

Coloring: Assign slots 1, 2, 3 to avoid conflicts.

3. Network Flows

Definition: A flow network is a directed graph $G=(V,E)$ with:

• Capacity $c_e$ for each edge $e$.
• Flow $f_e$ satisfying:
  1. $0\le f_e\le c_e$ (capacity constraint).
  2. Flow conservation: ${\sum }_{e\in \text{in}(v)}{f}_e={\sum }_{e\in \text{out}(v)}{f}_e$ for all $v\ne s,t$ (source/sink).

Key Theorems

1. Max-Flow Min-Cut Theorem: The maximum flow equals the capacity of the minimum cut.
2. Ford-Fulkerson Algorithm: Iteratively find augmenting paths to increase flow.

Example: Traffic Routing (NTC)

Scenario: Route data packets from source $s$ to sink $t$ with limited bandwidth. Graph:

graph LR
    s["Source"] -->|"10"| A["Router 1"]
    s -->|"5"| B["Router 2"]
    A -->|"8"| t["Sink"]
    B -->|"6"| t
    A -->|"4"| B

Max Flow Calculation:

1. Path $s\to A\to t$: flow = 8 (bottleneck).
2. Path $s\to B\to t$: flow = 5.
3. Path $s\to A\to B\to t$: flow = 4 (residual capacity). Total Max Flow: $8+5+4=17$.

4. Cryptography and Graph Theory

Graph-Based Ciphers:

• Error-Correcting Codes: Represented as graphs (e.g., Hamming codes for data transmission).
• RSA Encryption: Relies on modular arithmetic (graph of primes and Euler’s totient function $\varphi (n)$).

RSA Worked Example

Keys:

• Public: $(e,n)$, where $n=p\times q$ (primes), $e$ is coprime with $\varphi (n)$.
• Private: $d=e^{-1}\mathrm{mod}\varphi (n)$.

Encryption: $$c=m^e\mathrm{mod}n$$ Decryption: $$m=c^d\mathrm{mod}n$$

Example:

• $p=5$, $q=11$, $n=55$, $\varphi (n)=40$.
• Choose $e=3$ (coprime with 40), $d=27$ (since $3\times 27\equiv 1\mathrm{mod}40$).
• Encrypt $m=2$: $$c=2^3\mathrm{mod}55=8$$
• Decrypt: $$8^{27}\mathrm{mod}55=2$$

Visual:

graph TD
    M["Plaintext"] -->|"Encrypt"| C["Ciphertext"]
    C -->|"Decrypt"| M

5. Planar Graphs and Euler’s Formula

Definition: A graph is planar if it can be drawn without edge crossings. Euler’s Formula: For connected planar graphs, $$V-E+F=2$$ where $V$ = vertices, $E$ = edges, $F$ = faces.

Applications

• VLSI Design: Circuit layouts (e.g., NTC’s network topology).
• Map Coloring: Four Color Theorem (every planar graph is 4-colorable).

Example: Wheel Graph $W_3$

Vertices: 4 outer + 1 center. Edges: 4 outer + 4 spokes. Planarity Check: $V=5$, $E=8$, $F=5$ (satisfies $5-8+5=2$). Spanning Trees: Use Kirchhoff’s theorem (delete one edge, count trees in remaining graph).

In the Real World

1. Pathao’s Route Optimization:

   • Matching: Pairs drivers with passengers using bipartite matching (maximizing rides per hour).
   • Graph Coloring: Assigns time slots to drivers to avoid traffic overlaps (vertex coloring).

2. NEPSE’s Transaction Network:

   • Network Flows: Models share trading as flows between buyers/sellers, ensuring max transactions without overloading servers.

3. Khalti’s Fraud Detection:

   • Graph Theory: Builds transaction graphs to detect anomalies (e.g., sudden high-degree vertices = fraudulent activity).

4. Google’s PageRank:

   • Directed Graphs: Web pages as nodes, links as edges. PageRank uses eigenvectors to rank importance (similar to max-flow algorithms).

Exam Tip

1. Matching:

   • For bipartite graphs, always check Hall’s condition before applying algorithms.
   • In proofs, draw the graph and highlight augmenting paths.

2. Graph Coloring:

   • Greedy coloring is easy to implement but may not yield the chromatic number. Mention its limitation in exams.
   • For planar graphs, cite the Four Color Theorem if asked about coloring maps.

3. Network Flows:

   • Memorize the max-flow min-cut theorem—it’s the core of flow problems.
   • In exams, label residual capacities clearly when applying Ford-Fulkerson.

4. Cryptography:

   • RSA: Focus on the modular arithmetic steps (encryption/decryption formulas).
   • Graph-based codes: Link to error correction (e.g., "Hamming codes use graph distance to detect errors").

5. Planar Graphs:

   • Euler’s formula is tested often—derive it from a simple planar graph (e.g., a triangle) in proofs.
   • For spanning trees, use Kirchhoff’s theorem (delete edges, count trees) but show the matrix method if time permits.

Visual Summary:

mindmap
  root((Special Graph Topics))
    Matching
      Bipartite Graphs
      Augmenting Paths
      Hall's Theorem
    Coloring
      Vertex/Edge Coloring
      Greedy Algorithm
      Chromatic Number
    Network Flows
      Ford-Fulkerson
      Max-Flow Min-Cut
    Cryptography
      RSA
      Graph Codes
    Planar Graphs
      Euler's Formula
      Spanning Trees