Information AboutMatching |
| CATEGORIES ABOUT MATCHING | |
| graph theory | |
|
In the Mathematical discipline of Graph Theory a matching or '''edge independent set''' in a Graph is a set of edges without common Vertices . DEFINITION Given a Graph ''G'' = (''V'',''E'') a matching ''M'' in ''G'' is a set of pairwise Non-adjacent edges. We say that a vertex is matched if it is incident to an edge in the matching. Otherwise the vertex is '''unmatched'''. A maximum matching is a matching that is as big (has as many edges) as possible. There may be many maximum matchings. An alternating path is a path in which the edges belong alternatively to the matching and not to the matching. An augmenting path is an alternating path that starts from and ends on free (unmatched) vertices. A matching is maximum if and only if it does not contain any augmenting path. The matching number of a graph is the size of a maximum matching. A perfect matching is a matching which covers all vertices of the graph. That is, every vertex of the graph is Incident to exactly one edge of the matching. EXAMPLES
NOTES Some people also allow graphs with an Odd Number of vertices to have a "perfect" matching. These matchings have exactly one unmatched vertex. The Marriage Theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte Theorem provides a characterization for arbitrary graphs. Hopcroft and Karp proposed an algorithm for computing maximum matchings on bipartite graphs that runs in where n is the number of vertices and m is the number of edges. There is a Polynomial Time algorithm (sometimes called the Hungarian Algorithm ) which, given a ''bipartite'' graph G, determines if G has a perfect matching and, if it has, finds a perfect matching. There is also a polynomial time algorithm to find a maximum matching in a graph that is not bipartite; it is due to Edmonds, is called the ''paths, trees, and flowers'' method, and uses Bidirected Edges . A related problem is, given a graph G, to determine the number of perfect matchings in G. This problem is #P Complete . For Bipartite Graph s, it can be Approximately solved in polynomial time. That is, for any ε>0, there is a Probabilistic polynomial time algorithm that determines, with high Probability , the number of perfect matchings ''M'' within an error of at most ε''M''. PROPERTIES
SEE ALSO REFERENCES
|
|
|