This HTML5 document contains 51 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
n11http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n5https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n10http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Perfect_matching
rdfs:label
Perfect matching
rdfs:comment
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs:
foaf:depiction
n10:Maximum-matching-labels.svg
dcterms:subject
dbc:Matching_(graph_theory)
dbo:wikiPageID
44031
dbo:wikiPageRevisionID
1095739491
dbo:wikiPageWikiLink
dbr:Graph_(discrete_mathematics) dbr:Biadjacency_matrix dbr:Maximum_cardinality_matching dbr:Pieter_Kasteleyn dbr:FKT_algorithm dbr:Perfect_matching_in_high-degree_hypergraphs dbr:Matching_(graph_theory) dbr:Permanent_(mathematics) dbr:Imaginary_number dbr:Edge_cover dbr:Eigenvalues dbr:Hall-type_theorems_for_hypergraphs dbr:Tutte_theorem dbr:Graph_factorization dbr:Complete_graph dbr:Odd_number n11:Maximum-matching-labels.svg dbr:Envy-free_matching dbr:Hall's_marriage_theorem dbr:Polynomial-time dbr:1-factor dbr:Double_factorial dbr:Vertex_(graph_theory) dbc:Matching_(graph_theory) dbr:Factor_(graph_theory) dbr:Bipartite_graph dbr:Skew-symmetric_matrix dbr:Planar_graph dbr:Regular_graph dbr:♯P-complete dbr:Factor-critical_graph dbr:Graph_theory dbr:Subset
owl:sameAs
n5:FX4kZ wikidata:Q99567093
dbp:wikiPageUsesTemplate
dbt:Abs dbt:Short_description dbt:Mvar dbt:Math dbt:Main
dbo:thumbnail
n10:Maximum-matching-labels.svg?width=300
dbo:abstract
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs: In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal |V| / 2. A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.
prov:wasDerivedFrom
wikipedia-en:Perfect_matching?oldid=1095739491&ns=0
dbo:wikiPageLength
4894
foaf:isPrimaryTopicOf
wikipedia-en:Perfect_matching