ComplementHypergraph - Maple Help

Hypergraphs

 ComplementHypergraph
 Return the complement of an hypergraph

 Calling Sequence ComplementHypergraph(H)

Parameters

 H -

Description

 • The command ComplementHypergraph(H) returns the complement hypergraph of H.

Terminology

 • Complement hypergraph :  If H :=(X, Y) is a hypergraph, then the complement hypergraph of H is the hypergraph (X, Z) where Z is the set of the complements in X of the hyperedges of H.

Examples

 > $\mathrm{with}\left(\mathrm{Hypergraphs}\right):$$\mathrm{with}\left(\mathrm{ExampleHypergraphs}\right):$

Consider the Fan hypergraph of rank 4.

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

Draw a graphical representation of F4.

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

Compute the complement hypergraph C of of F4.

 > $C≔\mathrm{ComplementHypergraph}\left(\mathrm{F4}\right);$$\mathrm{Vertices}\left(C\right);$$\mathrm{Hyperedges}\left(C\right)$
 ${C}{≔}{\mathrm{< a hypergraph on 5 vertices with 5 hyperedges >}}$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}\right]$
 $\left[\left\{{5}\right\}{,}\left\{{1}{,}{2}{,}{3}\right\}{,}\left\{{1}{,}{2}{,}{4}\right\}{,}\left\{{1}{,}{3}{,}{4}\right\}{,}\left\{{2}{,}{3}{,}{4}\right\}\right]$ (2)

Draw a graphical representation of C.

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

Consider these two Kuratowski hypergraphs.

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

Draw a graphical representation of K2.

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

Draw a graphical representation of K3.

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

Observe that K3 is the complement hypergraph of K2.

 > $C≔\mathrm{ComplementHypergraph}\left(\mathrm{K2}\right);$$\mathrm{AreEqual}\left(C,\mathrm{K3}\right)$
 ${C}{≔}{\mathrm{< a hypergraph on 5 vertices with 10 hyperedges >}}$
 ${\mathrm{true}}$ (4)

Observe that K2 is the complement hypergraph of K3.

 > $C≔\mathrm{ComplementHypergraph}\left(\mathrm{K3}\right);$$\mathrm{AreEqual}\left(C,\mathrm{K2}\right)$
 ${C}{≔}{\mathrm{< a hypergraph on 5 vertices with 10 hyperedges >}}$
 ${\mathrm{true}}$ (5)

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[ComplementHypergraph] command was introduced in Maple 2024.