Chapter Matchings Flashcards
Defn/ A matching M subset E(G) of undirected graph G is:
Matching M subet of E(G) is the edge set of a 1-regular subgraph of G.
Defn/ A matching saturates a vertex v if:
if v is incident to some edge in matching. Otherwise, unsaturated
Defn/ The matching is perfect if:
If every vertex is saturated
Defn/ M is a maximum matching if:
if for any matching M’, |M| >+ |M’|
Defn/ An m-alternating path in G is:
is one whose edges are alternately in M and E(G)/M.
Defn/ An M-augmenting path in G is:
is an M-alternating path s.t. first and last vertices are M-unsaturated.
Thm/ A matching is maximum IFF G contains no M-augmenting path.
Pf/ (max +> no M-aug): BWOC, assume M max and there is M-aug path. Then, you can form a new matching along that path by swapping M and not M edges. Contradiction.
(No aug path => max.) BWOC, suppose M is not a max. Let M’ be a max, s.t. |M’| > |M|
Let H be subgraph formed by M union M’ and removing overlapping edges.
If H has component C of order 2:
If C in M, M’ not maximal b/c you could add that to M’
If C in M’, then C is M-aug path, contradict. assumpt
So all components >2 order. Each vert incident to at most M and M’, so deg v <= 2, so components are even cycles or paths, alternating between M & M’. Since |M’| > |M|, there is path in H w/ edges start and end in M’, m-aug path. Contradicts assumption
Defn/ If C proper subset V(G), the neighbor set N(S) is:
is the set of all vertices adjacent to those in S.
Defn/ The deficiency of a subset S subset X (where X,Y are partitions) is:
deficiency of a subset S subset X is |S| - |N(S)|. AKA how many in the other partition that S cannot match to with a matching.
Note, if deficiency is positive, can’t match all vertices in S.
Thm/ Let G be bipartite w/ partitions X,Y. G has a matching which saturates all vertices in X IFF |N(S)| >= S for all S subset X
Pf/ (Sat X match => |N(S)| >= |S|)
Let M be a matching which saturates X (all v in X is matched).
For S subset X, each vertex in S is matched to one in Y, so |N(S)| >= |S|
(other way =>) BWOC, suppose |N(S)| >= |S| for all S subset X.
But, there is 1 vertex u in X which is not saturated by a maximum matching M’. If 2 unsat., aug. path, so M’ not max.
Let Z be set of vert. conn. to u by alt. paths.
Let S = Z intersect X, T = Z intersect Y.
Each vert. in S{u} matched to one in T (b.c alternating paths), |T| = |S|-1.
T subset N(S) b/c N(S) is everything conn.
If w in N(S) and w not in T, must be adj. to some v in S. Ultimately, N(S) = T, then |N(S)| <|S|
Defn/ A vertex covering of a graph is:
is a subset K subset V(G) s.t. each edge in G has an end in K
Defn/ K’ is a min cover if:
if |K’| <= |K| for any cover K
Thm/ Min cover for K.n is any subset of n-1 vertices
Pf/ BWOC, assume there is cover with <= n-2 vert. There exists vert u,v not in K. B/c complete, there is an edge e = uv that has no end in K. Contradict.
Lemma/ If M is a matching for G, K a vertex cover, then |M| <= |K|
Pf/ For any matching M, K contains at least 1 endpoint of each edge in M.
BTW, this is weak duality b/c Max(M) != Min(K) necessarily, but if they are equal then you know they’re max and min.
Lemma/ If there exists M, K s.t. |M| = |K|, then M is a max matching and K is a min. cover.
Pf/ Let M’ be max matching, K’ min cover.
|M| <=|M’| <= |K’| <= |K|. Since |K| = |M|, then these are all equal.
Thm/ In a bipartite graph, max|M| = min|K|.
Pf/ Look into if needed
Alg/ Max matching for bipartite w/ Hungarian method
Given X, Y, matching M, unsat. u in X.
Set S={U}, T= {}.
1. Build out search tree along alternating paths. Once you find an augmenting path, implement augment.
2. Eventually, you find no more augmenting path, you are at max. Since bipartite, max matching M can only be as big as the smaller partition.
