
Calling Sequence


Hypergraph(V,E)
Hypergraph(E)
Hypergraph(V,B)


Parameters




Description


•

The command Hypergraph(V,E) returns the hypergraph H whose vertices are the members of V and whose hyperedges are the members of E.

•

The command Hypergraph(E) returns the hypergraph H whose hyperedges are the members of E and whose vertex set is the set V given as the union of the the members of E.

•

The command Hypergraph(V,B) returns the hypergraph H whose vertices are the members of V and whose hyperedges are encoded by the positive integer numbers of B. The encoding works as follows. If n is the number of vertices of H then each member of B is an integer b greater or equal to 1 and strictly less than 2^n encoding the subset of V containing its ith member if and only if the ith bit in the binary expansion of b is equal to 1.


Assumptions


•

The list V must not contain duplicates. If duplicates are present, then an error is raised.

•

The list E must contain nonempty sets only. If an empty set is found in E, then an error is raised. Moreover, the duplicates of E are ignored. Therefore, both V and E are regarded as sets.

•

For any member e of E that is not a subset of V, then the elements of e not belonging to V are added to V, so that each member of E can be seen as a subset of the augmented V.

•

The list B must contain positive integer numbers only. If a nonpositive integer number occurs, then an error is raised. Moreover, the duplicates of B are ignored.



Remarks


•

A hypergraph object encoding a hypergraph H records three attributes: a list of the vertices of H, a list of the hyperedges of H given as subsets of V and a list of the hyperedges of H given as positive integers (bit vector representations).

•

These latter two lists are sorted first by cardinality then by the colexicographical ordering induced by the order of the elements in Vertices(H).

•

The purpose of this ordering is to speedup certain computations such as those required by the commands Max, Min, Transversal.



Terminology


•

Hypergraph : mathematically, a hypergraph is a pair (X, Y) where X is a finite set and Y is a set of nonempty subsets of X.

•

Vertices : the members of X are called the vertices of the hypergraph (X, Y).

•

Hyperedges : the members of Y are called the hyperedges (or simply edges) of the hypergraph (X, Y).

•

Degree : the degree of a vertex v of a hypergraph H :=(X, Y) is the number elements of Y to which v belongs, that is, the number of hyperedges of H to which v belongs.

•

Rank : the rank of a hypergraph H :=(X, Y) is the maximum cardinality of a hyperedge of H.

•

Antirank : the antirank of a hypergraph H :=(X, Y) is the minimum cardinality of a hyperedge of H.

•

Regular : A hypergraph H is said regular whenever all its vertices have the same degree.

•

Uniform : A hypergraph H is said uniform whenever all its hyperedges have the same cardinality.

•

Connected : A hypergraph H is said connected whenever its line graph is connected.

•

Linear : A hypergraph H is said linear if the intersection of any two distinct hyperedges of H is either empty or consists of a single element.

•

Partial hypergraph : If H :=(X, Y) is a hypergraph and Z is a subset of Y, then (X, Z) is called the partial hypergraph of H induced by Z.

•

Subhypergraph : If H :=(X, Y) is a hypergraph, S is a subset of X and Z is the subset of Y consisting of the hyperedges of X contained in S, then (S, Z) is called the subhypergraph of H induced by S.

•

Vertex edge incidence graph : If H :=(X, Y) is a hypergraph, then the vertex edge incidence graph of H is the bipartite graph G from X to Y so that for any x of X and any y of Y, the set {x,y} is an edge of G if and only if x belongs to y.

•

Line graph : If H :=(X, Y) is a hypergraph, then the line graph of H is the graph G on Y such that any two hyperedges y1, y2 of H form an edge of G if and only if y1 and y2 have a nonempty intersection.

•

Equal hypergraphs : Two hypergraphs H1 :=(X1, Y1) and H2 :=(X2, Y2) are said equal whenever X1 = X2 and Y1 = Y2 both hold.

•

Isomorphic hypergraphs : Two hypergraphs H1 :=(X1, Y1) and H2 :=(X2, Y2) are said isomorphic whenever there exists a bijection f from X1 to X2 such that any nonempty subset x1 of X1 is a hyperedge of H1 if and only if f(x1) is a hyperedge of H2.

•

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.

•

Dual hypergraph : If H :=(X, Y) is a hypergraph, then the dual hypergraph of H is the hypergraph whose vertex set is Y and where {y1, y2, ...} is a hyperedge if y1, y2, ... intersect at a single vertex of H and {y1, y2, ...} is inclusionmaximal with that property.

•

Max : If H :=(X, Y) is a hypergraph, then Max(H) is the hypergraph (X, Z) where Z consists of all hyperedges of H that are maximal w.r.t. inclusion.

•

Min : If H :=(X, Y) is a hypergraph, then Min(H) is the hypergraph (X, Z) where Z consists of all hyperedges of H that are minimal w.r.t. inclusion.

•

Transversal : If H :=(X, Y) is a hypergraph, then a subset S of X is transversal to H whenever S has a nonempty 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.

•

Bit vector representation : given a totally ordered finite X and a subset S of X, a bit vector representation of S is a nonnegative integer b so that S contains the ith member of X if and only if the ith bit of b is equal to 1.

•

Colexicographical ordering : given a totally ordered finite X, a subset A of X is smaller (for the colexicographical ordering induced by X) than a subset B of X whenever A and B are different and the smallest element belonging to one set and not to the other belongs to A.




Examples


>

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

Create a hypergraph from its vertices and edges.
>

$H\u2254\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}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 7\; vertices\; with\; 4\; 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}\right]$
 
$\left[\left\{{4}\right\}{\,}\left\{{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}\right\}{\,}\left\{{3}{\,}{5}{\,}{6}\right\}\right]$
 (2) 
Draw a graphical representation of this hypergraph.
>

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

Create another hypergraph from its edges.
>

$H\u2254\mathrm{Hypergraph}\left(\left[\left\{1\,2\,3\right\}\,\left\{2\,3\right\}\,\left\{4\right\}\,\left\{3\,5\,6\right\}\right]\right)$

${H}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 6\; vertices\; with\; 4\; hyperedges\; >}}$
 (3) 
Print its vertices and edge.
>

$\mathrm{Vertices}\left(H\right)\;$$\mathrm{Hyperedges}\left(H\right)$

$\left[{1}{\,}{2}{\,}{3}{\,}{4}{\,}{5}{\,}{6}\right]$
 
$\left[\left\{{4}\right\}{\,}\left\{{2}{\,}{3}\right\}{\,}\left\{{1}{\,}{2}{\,}{3}\right\}{\,}\left\{{3}{\,}{5}{\,}{6}\right\}\right]$
 (4) 
Draw a graphical representation of this hypergraph.
>

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

Create a third hypergraph from its vertices and bit vector encdings of its edges.
>

$H\u2254\mathrm{Hypergraph}\left(\left[1\,2\,3\,4\,5\,6\,7\right]\,\left[8\,6\,7\,52\right]\right)$

${H}{\u2254}{\mathrm{<\; a\; hypergraph\; on\; 7\; vertices\; with\; 4\; hyperedges\; >}}$
 (5) 
Print its vertices and edges.
>

$\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]$
 (6) 
Draw a graphical representation of this hypergraph.
>

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



References



Claude Berge. Hypergraphes. Combinatoires des ensembles finis. 1987, Paris, GauthierVillars, translated to English.


Claude Berge. Hypergraphs. Combinatorics of Finite Sets. 1989, Amsterdam, NorthHolland 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: 5362, ACM.



Compatibility


•

The Hypergraphs[Hypergraph] command was introduced in Maple 2024.



