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.6-1.40.14 (TeX Live 2014/dev)
restricted \write18 enabled.
entering extended mode
(./math.tex
LaTeX2e <2011/06/27>
Babel <3.9h> 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
(
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.6-1.40.14 (TeX Live 2014/dev)
restricted \write18 enabled.
entering extended mode
(./math.tex
LaTeX2e <2011/06/27>
Babel <3.9h> 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
is a set of vertices
and a collection
of
sets of vertices called hyperedges or edges. In particular
. If all (hyper)edges contain exactly 2 vertices, then
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.6-1.40.14 (TeX Live 2014/dev)
restricted \write18 enabled.
entering extended mode
(./math.tex
LaTeX2e <2011/06/27>
Babel <3.9h> 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
is consists of the vertices set and a
set of closed curves. The set of vertices in each closed curve represents a
hyperedge of
. 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