Find a maximum matching and minimum vertex cover of the graph in Figure below, U

Question

Find a maximum matching and minimum vertex cover of the graph in Figure below, Using the M-Augmenting Path Algorithm, with the starting matching M = {A1B3, A4B2, A5B1}

please do it this format(just an example dont solve for rhe following)

starting with M = {x1y4, x4y2, x5y1, x6y3}.

Solution:Initialization:S := {x2, x3},T := , and all vertices start unmarked.

Choose x2.N(x2) = {y2, y3}.

T := T {y2, y3},S := S {x4, x6} = {x2, x3, x4, x6}.

Mark x2

ect......

Explanation / Answer

With initial matching set M, as:

A4B3, A4B2, A5B1

For the maximum matching, more edges which satisfies the condition that no two edges should share the vertex has to be added.

For M, as maximum matching, there should not be any M-augmenting path.

With above set M, for the path A1B3, augmenting paths are

A2B3, A1B1

For the path A4B2, augmenting paths are

A4B6, A3B2

For the path A5B1, augmenting paths are

A5B5 and A1B1

Last edge A6B4 is also added to get the maximum matching set M

Final maximum matching M =

{ A1B1, A2B3, A3B2, A4B6, A5B5, A6B4}

It is a perfect match, as it is a bipartite graph.

For a bipartite graph, Minimum vertex cover size is equal to the size of maximum matching, as atleast one vertex has to be picked for each edge in the maximum matching set M for the minimum vertex cover.

Minimum vertex cover = { B1, B2, B3, A4, A5, A6}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.