|
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 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
|
|
>
|
|
Create a hypergraph from its vertices and edges.
>
|
|
| (1) |
Print its vertices and edges.
>
|
|
| |
| (2) |
Draw a graphical representation of this hypergraph.
Create another hypergraph from its edges.
>
|
|
| (3) |
Print its vertices and edge.
>
|
|
| |
| (4) |
Draw a graphical representation of this hypergraph.
Create a third hypergraph from its vertices and bit vector encdings of its edges.
>
|
|
| (5) |
Print its vertices and edges.
>
|
|
| |
| (6) |
Draw a graphical representation of this hypergraph.
|
|
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.
|
|
|
|