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

See also

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

Table Of Contents

Previous topic

Hypergraph generators

Next topic

Graph coloring

This Page