MATCHING AND FACTOR by faith
➢ Matching
➢ Factors
➢ Basic Equations
➢ Bipartite graphs
➢ Algorithms
➢ Applications
DEFINITION : MATCHING
• A Matching in a graph G is a set of non-loop edges with no shared endpoints.
• A matching of graph G is a subgraph of G such that every edge shares no vertex
with any other edge. That is, each vertex in matching M has degree one.
• The vertices incident to the edges of a matching M are saturated by M , the others
are unsaturated ( we say M - saturated and
M - unsaturated ).
• A Perfect Matching in a graph is a matching that saturates every vertex.
• The size of a matching is the number of edges in that matching.
MATCHING continued
• A maximal matching in a graph is a matching that cannot be enlarged by adding an
edge.
• A maximum matching is a matching of maximum size among all matchings in the
graph.
• NOTE. Maximal ≠ maximum.
• The matching number of a graph is the size of
• a maximum matching of that graph.
• A matching of a graph G is complete if it contains all of G’s vertices. Sometimes
this is also called a perfect matching. Thus no complete matching exists
An M-alternating path whose endpoints are
unsaturated by M is an M-augmenting path.
M-augmenting path. This starts and ends
with a un saturtated edge
FACTORS
• A factor of a graph G is a spanning sub of a graph G is a spanning subgraph
of G. graph of G.
• A k-factor is a spanning is a spanning k-regular regular sub-graph.
• An odd component odd component of a graph is a component of of a
graph is a component of odd order; the number of odd components of H
odd order; the number of odd components of H is o(H).
.
.
Bipartite Graphs.
• A bipartite graph is a graph whose vertices V(G) can be divided into two disjoint
sets, V1 and V2 such that no edge connects two vertices of the same set.
PROPERTIES OF BIPARTITE GRAPHS
• Partition of vertices
• Edge connection
• No odd cycles
• 2-colorability
• Complete bipartite graphs is given by Km,n
COMPLETE BIPARTITE GRAPH
COMPLETE BIPARTITE GRAPHS
Complete bipartite
• Km,n or Kp,q ..
• Cosinder a Complete bipartite graph G with two set of Vertices m and n or p and q.
• Total number of edges in G = m*n or p*q
• Total number of vertices in G = m+n or p+q
• The figure shows a k3,2 graph
APLICATION OF BIPARTITE GRAPHS
.
.
.
.
ALGORITHMS
• Edmond’s Blossom Algorithm
• Gale-Shapley Proposal Algorithm
• Hungarian Algorithm
• Augmenting Path Algorithm
• Greedy Algorithm
Greedy Algorithm
.
.
.
STEP 1 STEP 2
STEP 3-4 STEP 5
Original matrix STEP 6
STEP 7
.
.
APPLICATION FOR MATCHING AND
FACTORS
• Optimal Assignment problem
• Graph- complete bipartite graph with weights
• Edges -
• Goal –find min/maxmum weight perfect matching
• Algorithm- Hungarian algorithm
• This is applied in , Resource allocation, Scheduling(allocating time slots ), chemical
bonding and Transportation
• Example
Personel Assignment problem by Patrick O
• Graph- complete bipartite graph (works X jobs)
• Edges -Qualifications
• Goal –find minmum matching
• Algorithm- Augmenting paths algorithm
• Example
Applications cont…
1. Resource Allocation
• This is about assigning a limited set of resources (like machines, trucks, or
servers) to a set of tasks or jobs in the most efficient way possible.
• How Matching/Factors Apply: The problem is modeled as a bipartite graph.
One set of vertices represents the resources (e.g., taxis), and the other set
represents the tasks (e.g., customer pickups). Edges between them
represent a possible assignment, often with a "cost" or "weight" (like time or
distance).
• Goal: To find a perfect matching (each task gets one resource) that
minimizes the total cost or maximizes the total efficiency. The Hungarian
algorithm is a classic method to solve this.
[Link] Subgraphs
• A spanning subgraph is one that includes all the vertices of the original graph. A k-factor is a specific type of spanning subgraph where
every vertex has exactly k neighbors (it's k-regular).
• How Matching/Factors Apply:
• A 1-factor is another name for a perfect matching—a set of edges where every vertex is connected to exactly one edge. This is used in
problems like pairing roommates or scheduling games in a tournament.
• A 2-factor is a collection of cycles that together cover all vertices. This is useful in designing circular routes, such as for delivery trucks or
network design, where each node needs to be visited exactly once in a cycle.
• [Link] Flow
• Imagine a network of pipes with a source (where flow starts) and a sink (where flow ends). The goal is to find the maximum amount of
"flow" (e.g., water, data, traffic) that can be sent from the source to the sink without exceeding the capacity of any pipe.
• How Matching/Factors Apply: Matching in bipartite graphs is a special case of network flow. You can model a bipartite matching problem
as a flow network by connecting the source to one partition and the sink to the other. Finding the maximum matching is equivalent to
finding the maximum flow in this constructed network.
Stable Marriage Problem
The goal is to pair members of two groups (like "men" and "women" or "medical students" and "hospitals") such that there are no two pairs who would both
rather be with each other than their current partners. This "no-incentive-to-swap" state is called stability.
• How Matching/Factors Apply: It's a matching problem on a bipartite graph where each vertex has a preference list ranking the vertices on the other
side. The Gale-Shapley algorithm finds a stable matching, ensuring that no such "blocking pair" exists.
• Goal: To find a stable, one-to-one matching between the two sets.
• Let's use the traditional framing with men and women.
The Classic Example: Men and Women
• Groups: Set A (Men: A, B, C...), Set B (Women: X, Y, Z...)
• Preferences: Each man ranks all women, and each woman ranks all men.
• Goal: Create man-woman pairs so the marriage is stable.
How It Relates to Graph Theory & Matching
• Graph Model: It's a bipartite graph.
• One partition: Men
• Other partition: Women
• Edges: All possible marriage pairs.
• The Matching: The solution is a perfect matching—every man is paired with exactly one woman, and vice versa.