Other Definitions
matching (dict)
|
MatchingThis article is about mathematical 'matchings. For matching' in the field of electronics, see: Impedance matching and Impedance bridging
In mathematical discipline of graph theory a matching or edge independent set for a graph is a set of edges without common vertices. Definition Given a graph G = (V,E) a matching M for G is a set of non-adjacent edges. A maximum matching is the biggest matching possible. The matching number for a graph is size of the 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 definitions also allow graphs with an odd number of vertices to have a perfect matching. These 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. There is a polynomial time algorithm (sometimes called Hungarian algorithm) which, given a graph G, determines if G has a perfect matching and, if it has, finds a perfect matching. A related problem is, given a graph G, determine the number of perfect matchings in G. This problem is #P Complete. For bipartite graphs, it can be approximately solved in polynomial time. That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines the number of perfect matchings M with error at most εM, with high probability. Properties See also References - Gallai, Tibor "ber extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
|
 |