Encyclopedia > Perfect matching

  Article Content

Perfect matching

A perfect matching for a connected graph is a matching[?], or subset of edges without common vertices, which touch all vertices exactly once. A graph with an odd number of vertices is allowed one unmatched vertex.

Note: Since an undirected, connected graph without self-loops has n(n-1)/2 edges, where n is the number of vertices, a perfect match consists of n/2 of the edges. The name of the term comes from matching each vertex with exactly one other vertex.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Bugatti

... Romano Artioli In 1987 the Bugatti name was sold to Romano Artioli, an Italian entrepreneur. He commissioned a car that was to become the world's fastest, ...

 
 
 
This page was created in 31.6 ms