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

System Message: WARNING/2 (\LaTeX)

latex exited with error: [stderr] [stdout] This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?’ option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! You can’t use `\spacefactor’ in math mode. \@->\spacefactor \@m l.30 $\LaTeX $ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 324 bytes). Transcript written on math.log.
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

System Message: WARNING/2 (\LaTeX)

latex exited with error: [stderr] [stdout] This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?’ option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! You can’t use `\spacefactor’ in math mode. \@->\spacefactor \@m l.30 $\LaTeX $ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 324 bytes). Transcript written on math.log.
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

System Message: WARNING/2 (\LaTeX)

latex exited with error: [stderr] [stdout] This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?’ option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! You can’t use `\spacefactor’ in math mode. \@->\spacefactor \@m l.30 $\LaTeX $ [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 324 bytes). Transcript written on math.log.
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