MATCHING GRAPH THEORY

GRAPH THEORY

1. Submitted by: Aman Sharma PRESENTATION ON MATCHING

2. MATCHING A matching or independent edge set in a graph is a set of edges without common vertices. A vertex is said to be a matched if it is incident to an edge otherwise unmatched. A matching ‘ m ’ that contains largest possible number of edges is called maximum matching .

3. MAXIMAL MATCHING A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M , it is no longer a matching A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M .

4. MAXIMUM MATCHING It is also known as maximum cardinality matching. It is a matching that contains the largest possible number of edges. The number of edges in the maximum matching of ‘ G ’ is called its matching number .

5. The matching number of this graph is 2

6. PERFECT MATCHING A matching (M) of graph (G) is said to be a perfect match, if every vertex of graph g (G) is incident to exactly one edge of the matching (M), i.e., deg(V ) = 1 ∀ V Every perfect matching of graph is also a maximum matching of graph, because there is no chance of adding one more edge in a perfect matching graph.

7. THANK YOU