📊Graph Theory Unit 11 – Matchings and Coverings

Key Concepts and Definitions

• Matching a set of edges in a graph where no two edges share a common vertex
• Maximal matching a matching where no additional edge can be added without violating the matching property
• Maximum matching a matching with the largest possible number of edges among all matchings in the graph
• Perfect matching a matching where every vertex in the graph is incident to exactly one edge in the matching
  • Also known as a 1-factor or a complete matching
• Bipartite graph a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set
• Alternating path a path in a graph where the edges alternate between being in the matching and not being in the matching
• Augmenting path an alternating path that starts and ends with unmatched vertices

Types of Matchings

• Maximal matching a matching where no additional edge can be added without violating the matching property
  • Not necessarily the largest possible matching in the graph
• Maximum matching a matching with the largest possible number of edges among all matchings in the graph
  • May not be unique, as there can be multiple maximum matchings in a graph
• Perfect matching a matching where every vertex in the graph is incident to exactly one edge in the matching
  • Only possible in graphs with an even number of vertices
• Near-perfect matching a matching where exactly one vertex is unmatched (in graphs with an odd number of vertices)
• Minimum maximal matching a maximal matching with the smallest possible number of edges
• Stable matching a matching in a bipartite graph where no two vertices would prefer to be matched with each other over their current partners (used in stable marriage problem)

Matching Algorithms

• Greedy algorithm iteratively selects edges to add to the matching, choosing the edge that maximizes the matching size at each step
  • Does not always produce a maximum matching
• Blossom algorithm finds a maximum matching in general graphs by identifying and contracting odd cycles (blossoms) in the graph
• Hungarian algorithm finds a maximum matching in a weighted bipartite graph by solving an equivalent minimum-cost flow problem
  • Also known as the Munkres algorithm or Kuhn-Munkres algorithm
• Hopcroft-Karp algorithm finds a maximum matching in a bipartite graph in $O(\sqrt{V}E)$ time by iteratively finding shortest augmenting paths
• Edmonds' algorithm finds a maximum matching in a general graph by recursively finding and contracting blossoms
  • Runs in $O(V^4)$ time

Coverings: Vertex and Edge

• Vertex cover a set of vertices such that every edge in the graph is incident to at least one vertex in the set
  • Minimum vertex cover a vertex cover with the smallest possible number of vertices
• Edge cover a set of edges such that every vertex in the graph is incident to at least one edge in the set
  • Minimum edge cover an edge cover with the smallest possible number of edges
• Relationship between vertex cover and matching in a bipartite graph, the size of a minimum vertex cover equals the size of a maximum matching (König's theorem)
• Relationship between edge cover and matching in a graph without isolated vertices, the size of a minimum edge cover equals the number of vertices minus the size of a maximum matching

Relationship Between Matchings and Coverings

• König's theorem in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover
  • Provides a way to find a minimum vertex cover by finding a maximum matching
• Gallai's theorem in a graph without isolated vertices, the sum of the size of a minimum vertex cover and the size of a maximum independent set equals the number of vertices
  • An independent set is a set of vertices where no two vertices are adjacent
• Tutte-Berge formula relates the size of a maximum matching in a graph to the number of vertices, the number of odd components, and the size of a maximum independent set
• Relationship between edge cover and matching in a graph without isolated vertices, the size of a minimum edge cover equals the number of vertices minus the size of a maximum matching
• Duality between vertex cover and independent set in a graph, a set of vertices is a vertex cover if and only if its complement is an independent set

Theorems and Proofs

• Hall's marriage theorem a bipartite graph has a perfect matching if and only if for every subset of vertices in one partite set, the number of neighbors in the other partite set is at least the size of the subset
  • Provides a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph
• Tutte's theorem a graph has a perfect matching if and only if for every subset of vertices, the number of odd components in the subgraph induced by removing the subset is at most the size of the subset
  • Generalizes Hall's theorem to non-bipartite graphs
• Berge's lemma an edge is in some maximum matching if and only if it is not in any minimum vertex cover
  • Establishes a relationship between maximum matchings and minimum vertex covers
• Petersen's theorem every cubic bridgeless graph has a perfect matching
  • A cubic graph is a graph where every vertex has degree 3, and a bridgeless graph is a graph that remains connected after removing any single edge

Applications in Real-World Problems

• Stable marriage problem matching individuals from two groups (e.g., men and women) based on their preferences, with the goal of creating stable matchings
  • Applications in college admissions, job assignments, and online dating platforms
• Job assignment problem assigning workers to jobs based on their qualifications and the job requirements, with the goal of maximizing the total quality of the assignments
• Network flow problems finding the maximum flow or minimum cut in a network, which can be reduced to finding a maximum matching in a bipartite graph
  • Applications in transportation networks, communication networks, and supply chain management
• Scheduling problems assigning tasks to time slots or resources, which can be modeled as finding a maximum matching in a bipartite graph
  • Applications in production planning, classroom assignments, and sports tournament scheduling
• Kidney exchange problem finding a set of compatible donor-recipient pairs for kidney transplants, which can be modeled as finding a maximum matching in a compatibility graph

Practice Problems and Examples

• Find a maximum matching in a bipartite graph
  • Example: Consider a bipartite graph with partite sets {A, B, C} and {1, 2, 3}, and edges {(A, 1), (A, 2), (B, 2), (C, 3)}. Find a maximum matching.
• Prove that a graph has a perfect matching using Hall's marriage theorem
  • Example: Prove that the complete bipartite graph $K_{n,n}$ has a perfect matching for any positive integer $n$.
• Find a minimum vertex cover in a graph by finding a maximum matching
  • Example: Given a graph with vertices {A, B, C, D} and edges {(A, B), (B, C), (C, D), (D, A)}, find a minimum vertex cover using the relationship between vertex covers and matchings.
• Solve a stable marriage problem using the Gale-Shapley algorithm
  • Example: Consider a set of men {M1, M2, M3} and a set of women {W1, W2, W3}, with the following preference lists:
    • M1: W1 > W2 > W3
    • M2: W2 > W1 > W3
    • M3: W1 > W2 > W3
    • W1: M2 > M1 > M3
    • W2: M1 > M2 > M3
    • W3: M1 > M2 > M3
  • Find a stable matching using the Gale-Shapley algorithm.