In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |NG(W)| < |W|, where NG(W) is the set of neighbors of W in G. If W is a Hall violator, then there is no matching that saturates all vertices of W. Therefore, there is also no matching that saturates X. Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates X.
| Property |
Value |
|
| dbo:abstract |
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |NG(W) |
< |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Find-hall-violator.svg?width=300 |
|
| dbo:wikiPageExternalLink |
https://cs.stackexchange.com/q/30017/1342%7Ctitle=Finding |
|
| dbo:wikiPageID |
61725084 (xsd:integer) |
|
| dbo:wikiPageLength |
10299 (xsd:nonNegativeInteger) |
|
| dbo:wikiPageRevisionID |
1082270412 (xsd:integer) |
|
| dbo:wikiPageWikiLink |
dbr:Matching_(graph_theory) dbr:Clique_problem dbr:Constraint_programming dbr:Hall's_marriage_theorem dbr:Hopcroft–Karp_algorithm dbr:Breadth-first_search dbr:Graph_theory dbc:Graph_theory dbr:Bipartite_graph dbr:File:Find-hall-violator.svg |
|
| dbp:wikiPageUsesTemplate |
dbt:! dbt:Cite_web dbt:Math dbt:Reflist |
|
| dcterms:subject |
dbc:Graph_theory |
|
| rdfs:comment |
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph G = (X + Y, E), a Hall-violator in X is a subset W of X, for which |NG(W) |
< |
| rdfs:label |
Hall violator (en) |
|
| owl:sameAs |
wikidata:Hall violator https://global.dbpedia.org/id/CC3jt |
|
| prov:wasDerivedFrom |
wikipedia-en:Hall_violator?oldid=1082270412&ns=0 |
|
| foaf:depiction |
wiki-commons:Special:FilePath/Find-hall-violator.svg |
|
| foaf:isPrimaryTopicOf |
wikipedia-en:Hall_violator |
|
| is dbo:wikiPageWikiLink of |
dbr:House_allocation_problem |
|
| is foaf:primaryTopic of |
wikipedia-en:Hall_violator |
|
