Matching
A Subset M of E is called Matching in G if its elements links and no two are adjacent in G.
The two ends of an edge in M are said to be Matched Under M.
A vertex V is said to be M- saturated if some edges of M is incident with V. Otherwise V is M- unsaturated.
For example
 |
| Graph G |
In the graph G, {AD, BC} is a matching
Maximum Matching
M is a maximum matching if G has no matching M' with\[\left | \mathbf{M'} \right |>\mathbf{M}\]
In the above example {AD, BC} is not maximum matching
Perfect Matching
If every vertex of G is M- saturated, then the matching M is perfect matching
In the graph G, {AD, BD, EF} is a perfect matching
 |
| Perfect matching |
Consider a graph
In the above graph, M={GH,IJ} is maximum matching. But not perfect. Since vertices, L and K are not saturated by the Matching M
In the above graph, M={GH,IJ} is maximum matching. But not perfect. Since vertices, L and K are not saturated by the Matching M
0 Comments