in Graph Theory
677 views
0 votes
0 votes
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd.
 

I don't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?
in Graph Theory
by
677 views

2 Comments

0
0

The confusing part.

Maximal Matching : A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M.

Maximum matching is defined as the maximal matching with maximum number of edges.

Note: Every maximum matching is maximal, but not every maximal matching is a maximum 

1
1

1 Answer

2 votes
2 votes

A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.

 an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.

maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, and denoted α(G)

----------------------------------------------------------------------------------------------------------------

Perfect matching exists for only graph with even number of vertices. No graph with odd number of vertices can contain perfect matching

here u get matching for complete graph

http://mathworld.wolfram.com/PerfectMatching.html

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

3 Comments

in which every vertex of the graph is incident to exactly one edge of the matching.

Mam, I didn't understood,what u mean by above line. Can you please explain in a more simpler way first please :)

0
0
mam please can u answer using an example. Will you? :)
0
0
In the reference you provided it is written that perfect matching can also be called as complete matching. But I have read that complete matching is different from perfect matching. Please clear my doubt
0
0