Consider the following bipartite graph G.

(a) Apply the maximum matching algorithm to G with initial matching M = {x₂y₁, x₃y₃, x₅y₄, x₆y₅} to find a maximum matching.?

Key in the following info in the required formats:

When 1^st breakthrough is reached:

• The label of vertices in X bipartition is ? (Eg: (*,*,y1,N,y4,N) where "N" means no-label for the vertex)
• The label of vertices in?Y bipartition is ? (Eg: (x4,N,x2,N,x4,x1) where "N" means no-label.)

When 2^nd breakthrough or 'STOP' is reached:

• The label of vertices in X bipartition is .
• The label of vertices in Y bipartition is .

The maximum matching is: (Key-in the edges in alphabetical order, Eg. {x1y1, x2y5, ... , x6y3}.)

(b) Is your maximum matching a perfect matching? ? ? ("Y" for Yes, "N" for No)

(c) Is it true that a perfect matching is always a maximum matching? ("Y" for Yes, "N" for No)

(d) Is it true that a maximum matching is always a perfect matching? ?("Y" for Yes, "N" for No)