Matching in hypergraphs

The red set of edges is a perfect matching, because it contains every vertex of the hypergraph. The yellow set is a maximum-cardinality matching, because it contains the most edges possible for a matching in this hypergraph, and the matching number is therefore 3. In a regular graph, if one has a perfect matching, that same matching is definitionally the maximum-cardinality matching for the graph, but in a hypergraph, where the number of vertices connected by an edge is variable, they can be 2 distinct matchings, as shown here.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.