Chapter 26, Problem 6P

(a)

Program Plan Intro

To show that if $P1,P2,\mathrm{.....},Pk$ are vertex-disjoint augmenting path with respect to $M$ then the symmetric difference $M\oplus (P1\cup P2\cup \mathrm{.......}\cup Pk)$ is a matching with the cardinality $\left|M\right|+k$ .

(b)

Program Plan Intro

To describe that if $\left|M\right|\le |M*|$ then $M\oplus M*$ contains at least $|M*|-\left|M\right|$ vertex-disjoint augmenting paths with respect to $M$ .

(c)

Program Plan Intro

To explain the P has more than l edges if P is vertex-disjoint from $P1,P2,\mathrm{......}Pk$ .

(d)

Program Plan Intro

To explains that $A=(P1\cup P2\cup \mathrm{.......}\cup Pk)\oplus P$ where $\left|A\right|\ge (k+1)l$ so P has more than l edges.

(e)

Program Plan Intro

To prove the size of maximum matching is at most $\left|M\right|+\left|V\right|/(l+1)$ .

(f)

Program Plan Intro

To explain the number of repeat loop iterations is at most $2\sqrt{\left|V\right|}$ .

(g)

Program Plan Intro

To gives an algorithm of $O(E)$ time to find a maximal set of vertex-disjoint shortest augmenting paths $P1,P2,\mathrm{....},Pk$ for matching.