## CS 535 Homework 2

### 1. Let G = (U; W; E) be a bipartite graph. Show that for any S; T ⊆ U, 算法分析作业代写

|N (S)| + |N (T)| ≥|N (S∩T)|+|N (S∪T)| .

2. Let G = (U; W; E) be a bipartite graph. Let I denote the collection of subsets of U which can be covered by some matching of G. Suppose that S,T ∈ I and |S|< |T|. Show that there exists v ∈ T \ S such that S ∪｛v｝∈I.

3. Let G = (U; W; E) be a bipartite graph. Given a maximum matching M of G, describe a linear -time algorithm to compute a set T ⊆ U satisfying that

#### (Hint: For each S ⊆ U, (U n S) [ N (S) is a vertex cover of G.)  算法分析作业代写

4. Let G = (U; W; E; w) be an edge-weighted bipartite graph with jUj = jV j. Suppose that the edge weight function w satisÖes that for w (e) 0 each e 2 E and the total weight of the edges incident to each vertex v 2 U [ W is exactly one. Show that G has a perfect matching.
(Hint: Use the Hallís condition.)

(a) Show that D has a negative circuit if and only if G has a perfect matching with negative weight.

QQ在线咨询

QQ:3554475127

QQ:3042439236