Hypergraphs¶

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


Hypergraph for information on the $$\LaTeX$$ output

Classes and methods¶

class sage.graphs.hypergraph.Hypergraph(sets)

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:

• sets – A list of hyperedges

EXAMPLES:

sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{6}]); H
Hypergraph on 6 vertices containing 4 sets


REFERENCES:

automorphism_group()

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

domain()

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])

edge_coloring()

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

to_bipartite_graph(with_partition=False)

Returns the associated bipartite graph

INPUT:

• with_partition – boolean (default: False)

OUTPUT:

• a graph or a pair (graph, partition)

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