Content deleted Content added
Adding short description: "A line that intersects a system of lines." (Shortdesc helper) |
Erel Segal (talk | contribs) |
||
Line 18:
== Relation to matching and covering ==
One can construct a [[bipartite graph]] in which the vertices on one side are the sets, the vertices on the other side are the elements, and the edges connect a set to the elements it contains. Then, a transversal (defined as a system of ''distinct'' representatives) is equivalent to a '''[[perfect matching]]''' in this graph.
One can construct a [[hypergraph]] in which the vertices are the elements, and the hyperedges are the sets. Then, a transversal (defined as a system of ''not-necessarily-distinct'' representatives) is equivalent to a [[Vertex cover in hypergraphs|'''vertex cover''' in a hypergraph]].
==Examples==
| |||