|
|
|
|
|
Let $G$ be a graph. A matching $M$ on $G$ is a subset of the edges of $G$ such that each vertex in $G$ is incident with no more than one edge in $M$
It is easy to find a matching on a graph; for example, the empty set will always be a matching. Typically, the most interesting matchings are maximal matchings. A maximal matching on a graph $G$ is simply a matching of the largest possible size.
A perfect matching is a matching that saturates every vertex.
|
"matching" is owned by Mathprof. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: saturates, size, empty set, incident, vertex, edges, subset, graph
There are 25 references to this entry.
This is version 4 of matching, born on 2002-05-26, modified 2006-09-27.
Object id is 2939, canonical name is Matching.
Accessed 11045 times total.
Classification:
| AMS MSC: | 05C70 (Combinatorics :: Graph theory :: Factorization, matching, covering and packing) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
