Math 2.0

definition

Perfect matching

Definition

Let GG be a graph. A perfect matching of GG is a matching MM such that every vertex of GG is an end of an edge of MM.

Remarks

In a perfect matching, each vertex is an end of exactly one edge of MM. Thus a finite graph with a perfect matching has an even number of vertices. Hall's theorem for bipartite graphs characterizes the bipartite graphs with a perfect matching. Tutte's theorem does this for all finite graphs. The complete graph K4K_4 has 33 perfect matchings.

Explanations

L1 human

A perfect matching pairs up all vertices of a graph along edges, with nobody left alone. For this, the number of vertices must be even.

What this node needs for W2
  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 2 nodes in this order. The foundations come first, and the list ends with this node.

Matching, definition, no evidence levelMatchingdefinitionPerfect matching, definition, no evidence levelPerfect matchingdefinition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Matching definition
  2. Perfect matching definition

What depends on this

1 node uses this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Perfect_matching, lead section

What links here

Used by