This module consists in a very basic implementation of Hypergraph, whose only current purpose is to observe them: it can be used to compute automorphism groups and to draw them. The latter is done at the moment through \(\LaTeX\) and TikZ, and can be obtained from Sage through the view command:
sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
Hypergraph on 6 vertices containing 4 sets
sage: view(H) # not tested
Note that hypergraphs are very hard to visualize, and unless it is very small (\(\leq 10\) sets) or has a very specific structure (like the following one), Sage’s drawing will only bring more confusion:
sage: g = graphs.Grid2dGraph(5,5)
sage: sets = Set(map(Set,list(g.subgraph_search_iterator(graphs.CycleGraph(4)))))
sage: H = Hypergraph(sets)
sage: view(H) # not tested
See also
Hypergraph for information on the \(\LaTeX\) output
A hypergraph.
A hypergraph \(H = (V, E)\) is a set of vertices \(V\) and a collection \(E\) of sets of vertices called hyperedges or edges. In particular \(E \subseteq \mathcal{P}(V)\). If all (hyper)edges contain exactly 2 vertices, then \(H\) is a graph in the usual sense.
Latex output
The \(\LaTeX\) for a hypergraph \(H\) is consists of the vertices set and a set of closed curves. The set of vertices in each closed curve represents a hyperedge of \(H\). A vertex which is encircled by a curve but is not located on its boundary is NOT included in the corresponding set.
The colors are picked for readability and have no other meaning.
INPUT:
EXAMPLES:
sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{6}]); H
Hypergraph on 6 vertices containing 4 sets
REFERENCES:
Returns the automorphism group.
For more information on the automorphism group of a hypergraph, see the Wikipedia article Hypergraph.
EXAMPLE:
sage: H = designs.steiner_triple_system(7).blocks()
sage: H = Hypergraph(H)
sage: g = H.automorphism_group(); g
Permutation Group with generators [(2,4)(5,6), (2,5)(4,6), (1,2)(3,4), (1,3)(5,6), (0,1)(2,5)]
sage: g.is_isomorphic(groups.permutation.PGL(3,2))
True
Return the set of vertices.
EXAMPLES:
sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
Hypergraph on 6 vertices containing 4 sets
sage: H.domain()
set([1, 2, 3, 4, 5, 6])
Compute a proper edge-coloring.
A proper edge-coloring is an assignment of colors to the sets of the hypergraph such that two sets with non-empty intersection receive different colors. The coloring returned minimizes the number of colors.
OUTPUT:
A partition of the sets into color classes.
EXAMPLES:
sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
Hypergraph on 6 vertices containing 4 sets
sage: C = H.edge_coloring()
sage: C # random
[[{3, 4, 5}], [{4, 5, 6}, {1, 2, 3}], [{2, 3, 4}]]
sage: Set(sum(C,[])) == Set(H._sets)
True
Returns the associated bipartite graph
INPUT:
OUTPUT:
EXAMPLES:
sage: H = designs.steiner_triple_system(7).blocks()
sage: H = Hypergraph(H)
sage: g = H.to_bipartite_graph(); g
Graph on 14 vertices
sage: g.is_regular()
True