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

Online Help

Hypergraphs[ExampleHypergraphs]

  

RandomHypergraph

  

Return a randomly generated hypergraph

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

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

Create a random hypergraph with 8 vertices and 16 hyperedges.

(1)

Print its vertices and edges.

(2)

Draw a graphical representation of this hypergraph.

Create another random hypergraph with 10 vertices and 500 hyperedges.

(3)

Apply the Min operator to it.

(4)

Print the cardinalities of the hyperedges of M.

(5)

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

(6)

Apply the Min operator to it.

(7)

Print the cardinalities of the hyperedges of M.

(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.

See Also

Hypergraphs[Hyperedges]

Hypergraphs[Hypergraph]

Hypergraphs[Vertices]

 


Download Help Document