Hall violator

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 , a Hall-violator in is a subset of , for which , where is the set of neighbors of in . If is a Hall violator, then there is no matching that saturates all vertices of .

Therefore, there is also no matching that saturates . Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates .

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 , a Hall-violator in is a subset of , for which , where is the set of neighbors of in  . If is a Hall violator, then there is no matching that saturates all vertices of .

Therefore, there is also no matching that saturates . Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates  .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1285189811 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001285189811 · captured 1744429960.0 · version history

Cite this page as: encyclopegia.org, “Hall violator”, snapshot enwiki-001285189811. https://encyclopegia.org/a/hall-violator

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.