Hypergraph - Maple Help

Hypergraphs

 Hypergraph
 Construct an hypergraph from its vertices and hyperedges

 Calling Sequence Hypergraph(V,E) Hypergraph(E) Hypergraph(V,B)

Parameters

 V - E - list of sets B - list of positive integers

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 i-th member if and only if the i-th 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 non-empty 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 non-positive 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 non-empty 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.
 • Anti-rank : the anti-rank 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 non-empty 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 non-empty 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 inclusion-maximal 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 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.
 • Bit vector representation : given a totally ordered finite X and a subset S of X, a bit vector representation of S is a non-negative integer b so that S contains the i-th member of X if and only if the i-th 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≔\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 >}}$ (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≔\mathrm{Hypergraph}\left(\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 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≔\mathrm{Hypergraph}\left(\left[1,2,3,4,5,6,7\right],\left[8,6,7,52\right]\right)$
 ${H}{≔}{\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, 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[Hypergraph] command was introduced in Maple 2024.