Graph Matching, Coloring, and Advanced Paths

TAKEAWAYS:

• Matching pairs vertices optimally (e.g., assigning tasks to workers), with perfect matchings requiring even-sized graphs.
• Graph coloring minimizes colors for conflict-free assignments (e.g., exam scheduling, frequency allocation).
• Eulerian/Hamiltonian cycles solve route optimization (e.g., postal delivery, circuit design) but require specific degree conditions.
• Greedy algorithms provide fast (but not always optimal) colorings, while backtracking ensures correctness.
• Applications span logistics (Pathao routes), social networks (friend recommendations), and infrastructure (NTC network planning).

1. Graph Matching: Pairing Vertices

Definition: A matching in a graph $G=(V,E)$ is a set of edges $M\subseteq E$ where no two edges share a vertex. A perfect matching covers every vertex.

Key Concepts

• Maximum Matching: Largest possible matching in $G$.
• Perfect Matching: Every vertex is included (only possible if $|V|$ is even).
• Bipartite Matching: Matching in bipartite graphs (e.g., job assignments).

How It Works

1. Greedy Matching: Iteratively add edges, skipping vertices already matched.
2. Augmenting Paths: For bipartite graphs, use the Ford-Fulkerson method to find maximum matchings.

Worked Example: Job Assignments

Scenario: A company has 4 workers and 4 tasks. Assign tasks to maximize productivity (edges = compatibility).

graph LR
    A["Worker 1"] -- 5 --> B["Task 1"]
    A -- 3 --> C["Task 2"]
    B -- 4 --> D["Worker 2"]
    C -- 6 --> D
    D -- 2 --> E["Worker 3"]
    E -- 7 --> F["Task 3"]
    F -- 1 --> G["Worker 4"]
    G -- 8 --> H["Task 4"]

Solution:

• Maximum matching: $\{(A,B),(C,D),(E,F),(G,H)\}$ (score = 5 + 6 + 7 + 8 = 26).
• Perfect matching exists since $|V|$ is even.

Real-World Tie-In:

• Pathao Driver Assignments: Match drivers to ride requests (vertices = drivers/requests; edges = distance/time compatibility). A perfect matching ensures all requests are fulfilled without overlap.

2. Graph Coloring: Minimizing Conflicts

Definition: Assign colors to vertices so no adjacent vertices share a color. The chromatic number $\chi (G)$ is the smallest number of colors needed.

Key Concepts

• Greedy Coloring: Assign the lowest available color to each vertex in order.
• Chromatic Number:
  • $\chi (G)=1$ if $G$ has no edges.
  • $\chi (G)=2$ if $G$ is bipartite.
  • $\chi (G)\le \Delta (G)+1$ (Brooks’ Theorem, where $\Delta$ is the maximum degree).
• Planar Graphs: $\chi (G)\le 4$ (Four Color Theorem).

Worked Example: Exam Scheduling

Scenario: Schedule 4 exams (A, B, C, D) with conflicts:

graph TD
    A["Exam A"] --> B["Exam B"]
    A --> C["Exam C"]
    B --> D["Exam D"]
    C --> D

Greedy Coloring (order: A → B → C → D):

1. A: Color 1
2. B: Adjacent to A → Color 2
3. C: Adjacent to A → Color 2 (but conflicts with B’s color). Use Color 3.
4. D: Adjacent to B and C → Color 1. Result: 3 colors used ($\chi (G)=3$).

Real-World Tie-In:

• NTC Frequency Allocation: Assign radio frequencies to base stations so adjacent towers don’t interfere (color = frequency). Greedy coloring minimizes spectrum waste.
• Khalti Transaction Scheduling: Color transactions by time slots to avoid conflicts in ledger updates.

3. Eulerian and Hamiltonian Cycles

Eulerian Cycle

Definition: A cycle that visits every edge exactly once. Conditions:

• All vertices have even degree.
• Graph is connected.

Worked Example: Postal Delivery Scenario: Deliver mail to 5 houses (vertices) with roads (edges). Can the postman return to the start without retracing?

graph TD
    A["House 1"] -- 1 --> B["House 2"]
    A -- 1 --> C["House 3"]
    B -- 1 --> C
    B -- 1 --> D["House 4"]
    C -- 1 --> D
    D -- 1 --> E["House 5"]
    E -- 1 --> A

Analysis:

• Degrees: A(3), B(3), C(3), D(3), E(3). No Eulerian cycle (all degrees odd).
• Solution: Add a duplicate edge (e.g., A–B) to make degrees even. Now an Eulerian cycle exists.

Real-World Tie-In:

• Ncell Network Routing: Optimize signal tower paths for maintenance trucks to minimize backtracking.

Hamiltonian Cycle

Definition: A cycle that visits every vertex exactly once. Conditions: No simple necessary/sufficient conditions (NP-Hard to check). Worked Example: Traveling Salesman Scenario: Visit 4 cities (A, B, C, D) with distances:

graph TD
    A -- 10 --> B
    A -- 15 --> C
    A -- 20 --> D
    B -- 35 --> C
    B -- 25 --> D
    C -- 30 --> D

Possible Cycle: A → B → D → C → A (total distance = 10 + 25 + 30 + 15 = 80). Real-World Tie-In:

• Daraz Delivery Routes: Find the shortest cycle to deliver orders to 5 warehouses (Hamiltonian path ≈ TSP).

4. Advanced Applications

5. Algorithms Summary

In the Real World

1. Pathao’s Ride Matching:

   • Uses bipartite matching to pair drivers (one set) with ride requests (other set) based on location and time. The algorithm maximizes matches without overlaps, similar to the job assignment example above.
   • Key Idea: Maximum bipartite matching ensures no driver is idle while requests pile up.

2. NTC’s Network Planning:

   • Graph coloring assigns frequencies to base stations so adjacent towers (connected by edges) use different colors (frequencies). This avoids interference, directly applying the chromatic number concept.
   • Worked Example: If two towers are 10 km apart (edge exists), they must use different frequencies (colors). NTC uses greedy coloring for initial planning and backtracking to refine.

3. Daraz’s Warehouse Logistics:

   • Hamiltonian paths optimize delivery routes between warehouses. While exact solutions are NP-Hard, Daraz uses heuristic algorithms (e.g., nearest-neighbor) to approximate paths, reducing fuel costs.
   • Real Scenario: For 5 warehouses in Kathmandu, a Hamiltonian path might visit them in order: Thapathali → Bhotahiti → Kageshwori → Lagankhel → Chabahil → Thapathali, minimizing total distance.

Exam Tip

1. Matching Questions:

   • For perfect matchings, always check if $|V|$ is even.
   • For bipartite graphs, use the adjacency matrix and Ford-Fulkerson to find maximum matchings.
   • Common Pitfall: Forgetting to verify if a matching is perfect (all vertices included).

2. Graph Coloring:

   • Greedy coloring is easy to implement but may not give the chromatic number. Mention its $O(V^2)$ time complexity.
   • For planar graphs, recall the Four Color Theorem ($\chi (G)\le 4$) and use it to bound answers.
   • Exam Trick: If a graph is bipartite, $\chi (G)=2$. Check for odd cycles to confirm.

3. Eulerian/Hamiltonian:

   • Eulerian: Focus on degrees. If all are even, a cycle exists. If two are odd, a path exists.
   • Hamiltonian: No shortcut—state conditions (e.g., complete graphs have Hamiltonian cycles) and whether the problem is NP-Hard.
   • Worked Example: For the postal delivery problem, always draw the graph and count degrees first.

4. Applications:

   • Link abstract problems to real scenarios (e.g., "This is like Pathao’s driver assignment" or "Like NTC’s frequency planning").
   • Use Mermaid diagrams to visualize graphs in answers—examiners reward clarity.

5. Proofs and Counting:

   • For inductive proofs (e.g., Brooks’ Theorem), show the base case and assume for $n$ vertices, then prove for $n+1$.
   • For counting matchings, use the adjacency matrix and permanent (though this is advanced). Stick to small examples.