Dark Mode

251 views

4 votes

Let us first put lebels on the vertices :-

**Definition of matching :- **Given a graph $G(V,E) $ , a matching M in G is a set of pairwise set of non adjacent edges , that is no two edges shares common vertices .

**Definition of maximal matching :- ** A maximal matching is a matching of a graph G, that is not a subset of any other matching .

So the maximal matching possible for the given question is :-

- $\left \{ e_{1},e_{3},e_{5} \right \}$
- $\left \{ e_{2},e_{4}\right \}$
- $\left \{ e_{1},e_{4}\right \}$
- $\left \{ e_{2},e_{5}\right \}$

Maximum matching is a matching that contain maximum number of pairwise non adjacent edges .

So the given question maximum matching is $\left \{ e_{1},e_{3},e_{5} \right \}$ of size $3$ .

1 vote

Definition of matching :- Given a graph , a matching M in G is a set of pairwise set of non adjacent edges , that is no two edges shares common vertices .

Definition of maximal matching :- A maximal matching is a matching of a graph G, that is not a subset of any other matching .

Clearly see they have asked noof maximal matchings not the maximum matching.

From the above graph ,

Assume edges are e1,e2,e3,e4,e5( consecutive edges) .

The maximal matchings possible are

{ e1,e3,e5} , { e2,e4} , {e1,e4} , {e2,e5} .

So , noof maximal matchings are 4 .

If they have asked about maximum matching size then it is 3 as {e1,e3,e5} is maximum matching possible

Definition of maximal matching :- A maximal matching is a matching of a graph G, that is not a subset of any other matching .

Clearly see they have asked noof maximal matchings not the maximum matching.

From the above graph ,

Assume edges are e1,e2,e3,e4,e5( consecutive edges) .

The maximal matchings possible are

{ e1,e3,e5} , { e2,e4} , {e1,e4} , {e2,e5} .

So , noof maximal matchings are 4 .

If they have asked about maximum matching size then it is 3 as {e1,e3,e5} is maximum matching possible