patternMinor
Perfect matching in a graph and complete matching in bipartite graph
Viewed 0 times
graphperfectbipartitecompleteandmatching
Problem
When I google for complete matching, first link points to perfect matching on wolfram.
It defines perfect matching as follows:
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. A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.
However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - in which every vertex of of the graph is incident to exactly one edge. One of the matching can be $\{E_1,E_4,E_6\}$. However not every vertex (here, $\{V_5,V_6,V_9,V_{10}\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.
Q1. Is perfect matching possible with this graph?
I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:
In a bipartite graph having a vertex partition $V_1$ and $V_2$ a complete matching of vertices in set $V_1$ into those in $V_2$ is a matching in which there is one edge incident with every vertex in $V_1$. In other words, every vertex in $V_1$ is matched against some vertex in $V_2$.
I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.
By my understanding, according to Deo's definition, $V_2$ may contain more vertices than that in $V_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the complete matching of vertices in set $P_1$ into those in $P_2$ can be $\{E_1,E_4,E_6\}$ as one edge in this matching is inciden
It defines perfect matching as follows:
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. A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.
However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - in which every vertex of of the graph is incident to exactly one edge. One of the matching can be $\{E_1,E_4,E_6\}$. However not every vertex (here, $\{V_5,V_6,V_9,V_{10}\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.
Q1. Is perfect matching possible with this graph?
I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:
In a bipartite graph having a vertex partition $V_1$ and $V_2$ a complete matching of vertices in set $V_1$ into those in $V_2$ is a matching in which there is one edge incident with every vertex in $V_1$. In other words, every vertex in $V_1$ is matched against some vertex in $V_2$.
I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.
By my understanding, according to Deo's definition, $V_2$ may contain more vertices than that in $V_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the complete matching of vertices in set $P_1$ into those in $P_2$ can be $\{E_1,E_4,E_6\}$ as one edge in this matching is inciden
Solution
These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the concepts coincide.
The term bipartite perfect matching is not standard – in fact I just made it up. Usually perfect matching just means a matching involving all the vertices.
The term bipartite perfect matching is not standard – in fact I just made it up. Usually perfect matching just means a matching involving all the vertices.
Context
StackExchange Computer Science Q#50410, answer score: 7
Revisions (0)
No revisions yet.