Transversal - Maple Help

Hypergraphs

 Transversal
 Return the transversal of an hypergraph

 Calling Sequence Transversal(H)

Parameters

 H -

Description

 • The command Transversal(H) returns the transversal hypergraph of H.

Terminology

 • Transversal : If H :=(X, Y) is a hypergraph, then a subset S of X is transversal to H whenever S has a non-empty intersection with every hyperedge of H. If H :=(X, Y) is a hypergraph, then the transversal hypergraph of H is the hypergraph (X, Z) where Z consists of all transversals to H that are minimal w.r.t. inclusion.

Examples

 > $\mathrm{with}\left(\mathrm{Hypergraphs}\right):$$\mathrm{with}\left(\mathrm{ExampleHypergraphs}\right)$
 $\left[{\mathrm{Fan}}{,}{\mathrm{Kuratowski}}{,}{\mathrm{Lovasz}}{,}{\mathrm{NonEmptyPowerSet}}{,}{\mathrm{RandomHypergraph}}\right]$ (1)

Create a hypergraph from its vertices and edges.

 > $H≔\mathrm{Hypergraph}\left(\left[1,2,3,4,5,6,7\right],\left[\left\{1,2,3\right\},\left\{2,3\right\},\left\{4\right\},\left\{3,5,6\right\}\right]\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 7 vertices with 4 hyperedges >}}$ (2)

Print the vertices and edges of H.

 > $\mathrm{Vertices}\left(H\right);$$\mathrm{Hyperedges}\left(H\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$ (3)

Draw a graphical representation of this hypergraph.

 > $\mathrm{Draw}\left(H\right)$

Compute Max(H), print its vertices and edges, draw a graphical representation of it.

 > $M≔\mathrm{Max}\left(H\right);$$\mathrm{Vertices}\left(M\right);$$\mathrm{Hyperedges}\left(M\right);$$\mathrm{Draw}\left(M\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$

Compute Min(H), print its vertices and edges, draw a graphical representation of  it.

 > $M≔\mathrm{Min}\left(H\right);$$\mathrm{Vertices}\left(M\right);$$\mathrm{Hyperedges}\left(M\right);$$\mathrm{Draw}\left(M\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$

Compute the transversal hypergraph of H.

 > $T≔\mathrm{Transversal}\left(H\right);$$\mathrm{Vertices}\left(T\right);$$\mathrm{Hyperedges}\left(T\right);$$\mathrm{Draw}\left(T\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}\right]$
 $\left[\left\{{3}{,}{4}\right\}{,}\left\{{2}{,}{4}{,}{5}\right\}{,}\left\{{2}{,}{4}{,}{6}\right\}\right]$

Observe that Transversal(T) and Min(H) are equal.

 > $\mathrm{TT}≔\mathrm{Transversal}\left(T\right);$$\mathrm{Hyperedges}\left(\mathrm{TT}\right);$$\mathrm{AreEqual}\left(\mathrm{TT},\mathrm{Min}\left(H\right)\right)$
 ${\mathrm{TT}}{≔}{\mathrm{< a hypergraph on 7 vertices with 3 hyperedges >}}$
 $\left[\left\{{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{5}{,}{6}\right\}\right]$
 ${\mathrm{true}}$ (4)

Consider the following Kuratowski hypergraph.

 > $\mathrm{K3}≔\mathrm{Kuratowski}\left(\left\{1,2,3,4,5\right\},3\right)$
 ${\mathrm{K3}}{≔}{\mathrm{< a hypergraph on 5 vertices with 10 hyperedges >}}$ (5)

Observe that K3 is its own transversal.

 > $\mathrm{AreEqual}\left(\mathrm{Transversal}\left(\mathrm{K3}\right),\mathrm{K3}\right)$
 ${\mathrm{true}}$ (6)

Consider a random hypergraph on 5 points and 15 hyperedges.

 > $R≔\mathrm{RandomHypergraph}\left(5,15\right);$$\mathrm{Hyperedges}\left(R\right)$
 ${R}{≔}{\mathrm{< a hypergraph on 5 vertices with 15 hyperedges >}}$
 $\left[\left\{{5}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{4}\right\}{,}\left\{{1}{,}{5}\right\}{,}\left\{{2}{,}{5}\right\}{,}\left\{{3}{,}{5}\right\}{,}\left\{{1}{,}{3}{,}{4}\right\}{,}\left\{{1}{,}{3}{,}{5}\right\}{,}\left\{{2}{,}{3}{,}{5}\right\}{,}\left\{{1}{,}{4}{,}{5}\right\}{,}\left\{{3}{,}{4}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{3}{,}{5}\right\}{,}\left\{{1}{,}{2}{,}{4}{,}{5}\right\}\right]$ (7)

Compute its minimal hyperedges.

 > $M≔\mathrm{Min}\left(R\right);$$\mathrm{Hyperedges}\left(M\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[\left\{{5}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{4}\right\}\right]$ (8)

Compute the transversal hypergraph  T of  R and the transversal hypergraph TT of  T.

 > $T≔\mathrm{Transversal}\left(R\right);$$\mathrm{Hyperedges}\left(T\right)$
 ${T}{≔}{\mathrm{< a hypergraph on 5 vertices with 3 hyperedges >}}$
 $\left[\left\{{1}{,}{2}{,}{5}\right\}{,}\left\{{2}{,}{4}{,}{5}\right\}{,}\left\{{1}{,}{3}{,}{4}{,}{5}\right\}\right]$ (9)
 > $\mathrm{TT}≔\mathrm{Transversal}\left(T\right);$$\mathrm{Hyperedges}\left(\mathrm{TT}\right)$
 ${\mathrm{TT}}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[\left\{{5}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{4}\right\}\right]$ (10)

Observe that TT and M are equal.

 > $\mathrm{AreEqual}\left(\mathrm{TT},M\right)$
 ${\mathrm{true}}$ (11)

References

 Claude Berge. Hypergraphes. Combinatoires des ensembles finis. 1987,  Paris, Gauthier-Villars, translated to English.
 Claude Berge. Hypergraphs. Combinatorics of Finite Sets.  1989, Amsterdam, North-Holland Mathematical Library, Elsevier, translated from French.
 Charles Leiserson, Liyun Li, Marc Moreno Maza and Yuzhen Xie " Parallel computation of the minimal elements of a poset." Proceedings of the 4th International Workshop on Parallel Symbolic Computation (PASCO) 2010: 53-62, ACM.

Compatibility

 • The Hypergraphs[Transversal] command was introduced in Maple 2024.