CS535 Homework 4
北美计算机作业代写 A matching M is a maximal matching of G = (V, E) if for every e ∈ E \ M, M ∪｛e｝ is not a matching.
1. A matching M is a maximal matching of G = (V, E) if for every e ∈ E \ M, M ∪｛e｝ is not a matching.
(a) Show how to construct a maximal matching in O(|E|) time.
(b) Show that for any maximal matching M, |M| ≥a'(G) /2.
2. Give an instance of a graph G, a matching M, and an M-blossom B such that a maximum matching N in G=B does not lift to a maximum matching in G. 北美计算机作业代写
3. Let U be any minimizer in the Tutte-Berge formula, and V1; …; Vk be the connected components of G-U. Show that, for any maximum matching M, we must have that
(a) M contains exactly [Vi/2] edges from G [Vi] (the subgraph of G induced by the vertices in Vi), i.e., G [Vi] is perfectly matched for the even components Vi and near-perfectly matched for the odd components.
(b) Each vertex u 2 U is matched to a vertex v in an odd component Vi of G-U.
(c) The only unmatched vertices must be in odd components of G-U.
4. Prove that J is a T-join in a graph G if and only if J is the union of edge-disjoint circuits and |T| =2 paths connecting disjoint pairs of nodes in T.
5. [PhD Session only] Given an undirected graph G with non-negative edge weight function ` and two vertices s and t , we look for a shortest s-t path with an even number of edges. Reduce this to a Minimum-Cost Perfect Matching problem. Hint: Take two copies of G, connect each vertex with its copy by an edge of zero weight and delete s and t. 北美计算机作业代写
