RandomHypergraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Hypergraphs[ExampleHypergraphs]

 RandomHypergraph
 Return a randomly generated hypergraph

 Calling Sequence RandomHypergraph(n,m) RandomHypergraph(n,m, mopt)

Parameters

 n - nonnegative integer m - nonnegative integer mopt - (optional) option of the form method = s, where s is one of auto (the default), acceptreject, saturated, or uniform

Description

 • The command RandomHypergraph(n,m) returns a randomly generated hypergraph with the positive integers up to n as vertices and  with m hyperedges.
 • The integer m must be less than 2^n, otherwise an error is raised.
 • The hyperedges of  RandomHypergraph(n,m)  are chosen at random among the non-empty subsets of V where V  is the set of the positive integers up to n. The probability distribution depends on the method option.
 • If the option method = uniform is passed, then the m hyperedges are chosen uniformly at random from all possible hyperedges.
 • The three other method values have the same probability distribution for the hyperedges: each hyperedge of cardinality k is chosen with probability proportional to binomial(n, k). They differ in the method of achieving this probability distribution: method = acceptreject is usually quite efficient, but less so if m is close to 2^n. On the other hand, method = saturated is usually a little less efficient than method = acceptreject, except if m is close to 2^n. The option method = auto (the default) selects between method = acceptreject and method = saturated according to which of the two is likely to be fastest.
 • The uniform sampling method is more likely to generate very small or very large hyperedges, so calling Min or Max on such a hypergraph often gives a hypergraph with relatively few hyperedges in it.

Examples

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

Create a random hypergraph with 8 vertices and 16 hyperedges.

 > $H≔\mathrm{RandomHypergraph}\left(8,16\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 8 vertices with 16 hyperedges >}}$ (1)

Print its vertices and edges.

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

Draw a graphical representation of this hypergraph.

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

Create another random hypergraph with 10 vertices and 500 hyperedges.

 > $H≔\mathrm{RandomHypergraph}\left(10,500\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 10 vertices with 500 hyperedges >}}$ (3)

Apply the Min operator to it.

 > $M≔\mathrm{Min}\left(H\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 10 vertices with 29 hyperedges >}}$ (4)

Print the cardinalities of the hyperedges of M.

 > $\mathrm{map}\left(\mathrm{numelems},\mathrm{Hyperedges}\left(M\right)\right)$
 $\left[{1}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{3}{,}{4}\right]$ (5)

Create another random hypergraph  with 10 vertices and 500 hyperedges using the uniform distribution method.

 > $H≔\mathrm{RandomHypergraph}\left(10,500,\mathrm{method}=\mathrm{uniform}\right)$
 ${H}{≔}{\mathrm{< a hypergraph on 10 vertices with 500 hyperedges >}}$ (6)

Apply the Min operator to it.

 > $M≔\mathrm{Min}\left(H\right)$
 ${M}{≔}{\mathrm{< a hypergraph on 10 vertices with 15 hyperedges >}}$ (7)

Print the cardinalities of the hyperedges of M.

 > $\mathrm{map}\left(\mathrm{numelems},\mathrm{Hyperedges}\left(M\right)\right)$
 $\left[{1}{,}{1}{,}{1}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{2}{,}{3}\right]$ (8)

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[ExampleHypergraphs][RandomHypergraph] command was introduced in Maple 2024.
 • For more information on Maple 2024 changes, see Updates in Maple 2024.