Intersection graphs#

The methods defined here appear in sage.graphs.graph_generators.

sage.graphs.generators.intersection.IntersectionGraph(S)#

Return the intersection graph of the family \(S\)

The intersection graph of a family \(S\) is a graph \(G\) with \(V(G)=S\) such that two elements \(s_1,s_2\in S\) are adjacent in \(G\) if and only if \(s_1\cap s_2\neq \emptyset\).

INPUT:

  • S – a list of sets/tuples/iterables

    Note

    The elements of \(S\) must be finite, hashable, and the elements of any \(s\in S\) must be hashable too.

EXAMPLES:

sage: graphs.IntersectionGraph([(1,2,3),(3,4,5),(5,6,7)])
Intersection Graph: Graph on 3 vertices
sage.graphs.generators.intersection.IntervalGraph(intervals, points_ordered=False)#

Return the graph corresponding to the given intervals.

An interval graph is built from a list \((a_i,b_i)_{1\leq i \leq n}\) of intervals : to each interval of the list is associated one vertex, two vertices being adjacent if the two corresponding (closed) intervals intersect.

INPUT:

  • intervals – the list of pairs \((a_i,b_i)\) defining the graph.

  • points_ordered – states whether every interval \((a_i,b_i)\) of \(intervals\) satisfies \(a_i<b_i\). If satisfied then setting points_ordered to True will speed up the creation of the graph.

Note

  • The vertices are named 0, 1, 2, and so on. The intervals used to create the graph are saved with the graph and can be recovered using get_vertex() or get_vertices().

EXAMPLES:

The following line creates the sequence of intervals \((i, i+2)\) for i in \([0, ..., 8]\):

sage: intervals = [(i,i+2) for i in range(9)]

In the corresponding graph

sage: g = graphs.IntervalGraph(intervals)
sage: g.get_vertex(3)
(3, 5)
sage: neigh = g.neighbors(3)
sage: for v in neigh: print(g.get_vertex(v))
(1, 3)
(2, 4)
(4, 6)
(5, 7)

The is_interval() method verifies that this graph is an interval graph.

sage: g.is_interval()
True

The intervals in the list need not be distinct.

sage: intervals = [ (1,2), (1,2), (1,2), (2,3), (3,4) ]
sage: g = graphs.IntervalGraph(intervals,True)
sage: g.clique_maximum()
[0, 1, 2, 3]
sage: g.get_vertices()
{0: (1, 2), 1: (1, 2), 2: (1, 2), 3: (2, 3), 4: (3, 4)}

The endpoints of the intervals are not ordered we get the same graph (except for the vertex labels).

sage: rev_intervals = [ (2,1), (2,1), (2,1), (3,2), (4,3) ]
sage: h = graphs.IntervalGraph(rev_intervals,False)
sage: h.get_vertices()
{0: (2, 1), 1: (2, 1), 2: (2, 1), 3: (3, 2), 4: (4, 3)}
sage: g.edges(sort=True) == h.edges(sort=True)
True
sage.graphs.generators.intersection.OrthogonalArrayBlockGraph(k, n, OA=None)#

Return the graph of an \(OA(k,n)\).

The intersection graph of the blocks of a transversal design with parameters \((k,n)\), or \(TD(k,n)\) for short, is a strongly regular graph (unless it is a complete graph). Its parameters \((v,k',\lambda,\mu)\) are determined by the parameters \(k,n\) via:

\[v=n^2, k'=k(n-1), \lambda=(k-1)(k-2)+n-2, \mu=k(k-1)\]

As transversal designs and orthogonal arrays (OA for short) are equivalent objects, this graph can also be built from the blocks of an \(OA(k,n)\), two of them being adjacent if one of their coordinates match.

For more information on these graphs, see Andries Brouwer’s page on Orthogonal Array graphs.

Warning

  • Brouwer’s website uses the notation \(OA(n,k)\) instead of \(OA(k,n)\)

  • For given parameters \(k\) and \(n\) there can be many \(OA(k,n)\) : the graphs returned are not uniquely defined by their parameters (see the examples below).

  • If the function is called only with the parameter k and n the results might be different with two versions of Sage, or even worse : some could not be available anymore.

See also

sage.combinat.designs.orthogonal_arrays

INPUT:

  • k,n (integers)

  • OA – An orthogonal array. If set to None (default) then orthogonal_array() is called to compute an \(OA(k,n)\).

EXAMPLES:

sage: # needs sage.modules
sage: G = graphs.OrthogonalArrayBlockGraph(5,5); G                              # needs sage.schemes
OA(5,5): Graph on 25 vertices
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.schemes
(25, 20, 15, 20)
sage: G = graphs.OrthogonalArrayBlockGraph(4,10); G
OA(4,10): Graph on 100 vertices
sage: G.is_strongly_regular(parameters=True)
(100, 36, 14, 12)

Two graphs built from different orthogonal arrays are also different:

sage: # needs sage.modules
sage: k = 4; n = 10
sage: OAa = designs.orthogonal_arrays.build(k,n)
sage: OAb = [[(x+1)%n for x in R] for R in OAa]
sage: set(map(tuple,OAa)) == set(map(tuple,OAb))
False
sage: Ga = graphs.OrthogonalArrayBlockGraph(k, n, OAa)
sage: Gb = graphs.OrthogonalArrayBlockGraph(k, n, OAb)
sage: Ga == Gb
False

As OAb was obtained from OAa by a relabelling the two graphs are isomorphic:

sage: Ga.is_isomorphic(Gb)                                                      # needs sage.modules
True

But there are examples of \(OA(k,n)\) for which the resulting graphs are not isomorphic:

sage: oa0 = [[0, 0, 1], [0, 1, 3], [0, 2, 0], [0, 3, 2],
....:        [1, 0, 3], [1, 1, 1], [1, 2, 2], [1, 3, 0],
....:        [2, 0, 0], [2, 1, 2], [2, 2, 1], [2, 3, 3],
....:        [3, 0, 2], [3, 1, 0], [3, 2, 3], [3, 3, 1]]
sage: oa1 = [[0, 0, 1], [0, 1, 0], [0, 2, 3], [0, 3, 2],
....:        [1, 0, 3], [1, 1, 2], [1, 2, 0], [1, 3, 1],
....:        [2, 0, 0], [2, 1, 1], [2, 2, 2], [2, 3, 3],
....:        [3, 0, 2], [3, 1, 3], [3, 2, 1], [3, 3, 0]]
sage: g0 = graphs.OrthogonalArrayBlockGraph(3, 4, oa0)                          # needs sage.modules
sage: g1 = graphs.OrthogonalArrayBlockGraph(3, 4, oa1)                          # needs sage.modules
sage: g0.is_isomorphic(g1)                                                      # needs sage.modules
False

But nevertheless isospectral:

sage: g0.spectrum()                                                             # needs sage.modules sage.rings.number_field
[9, 1, 1, 1, 1, 1, 1, 1, 1, 1, -3, -3, -3, -3, -3, -3]
sage: g1.spectrum()                                                             # needs sage.modules sage.rings.number_field
[9, 1, 1, 1, 1, 1, 1, 1, 1, 1, -3, -3, -3, -3, -3, -3]

Note that the graph g0 is actually isomorphic to the affine polar graph \(VO^+(4,2)\):

sage: graphs.AffineOrthogonalPolarGraph(4,2,'+').is_isomorphic(g0)              # needs sage.libs.gap sage.modules
True
sage.graphs.generators.intersection.PermutationGraph(second_permutation, first_permutation=None)#

Build a permutation graph from one permutation or from two lists.

Definition:

If \(\sigma\) is a permutation of \(\{ 1, 2, \ldots, n \}\), then the permutation graph of \(\sigma\) is the graph on vertex set \(\{ 1, 2, \ldots, n \}\) in which two vertices \(i\) and \(j\) satisfying \(i < j\) are connected by an edge if and only if \(\sigma^{-1}(i) > \sigma^{-1}(j)\). A visual way to construct this graph is as follows:

Take two horizontal lines in the euclidean plane, and mark points \(1, ..., n\) from left to right on the first of them. On the second one, still from left to right, mark \(n\) points \(\sigma(1), \sigma(2), \ldots, \sigma(n)\). Now, link by a segment the two points marked with \(1\), then link together the points marked with \(2\), and so on. The permutation graph of \(\sigma\) is the intersection graph of those segments: there exists a vertex in this graph for each element from \(1\) to \(n\), two vertices \(i, j\) being adjacent if the segments \(i\) and \(j\) cross each other.

The set of edges of the permutation graph can thus be identified with the set of inversions of the inverse of the given permutation \(\sigma\).

A more general notion of permutation graph can be defined as follows: If \(S\) is a set, and \((a_1, a_2, \ldots, a_n)\) and \((b_1, b_2, \ldots, b_n)\) are two lists of elements of \(S\), each of which lists contains every element of \(S\) exactly once, then the permutation graph defined by these two lists is the graph on the vertex set \(S\) in which two vertices \(i\) and \(j\) are connected by an edge if and only if the order in which these vertices appear in the list \((a_1, a_2, \ldots, a_n)\) is the opposite of the order in which they appear in the list \((b_1, b_2, \ldots, b_n)\). When \((a_1, a_2, \ldots, a_n) = (1, 2, \ldots, n)\), this graph is the permutation graph of the permutation \((b_1, b_2, \ldots, b_n) \in S_n\). Notice that \(S\) does not have to be a set of integers here, but can be a set of strings, tuples, or anything else. We can still use the above visual description to construct the permutation graph, but now we have to mark points \(a_1, a_2, \ldots, a_n\) from left to right on the first horizontal line and points \(b_1, b_2, \ldots, b_n\) from left to right on the second horizontal line.

INPUT:

  • second_permutation – the unique permutation/list defining the graph, or the second of the two (if the graph is to be built from two permutations/lists).

  • first_permutation (optional) – the first of the two permutations/lists from which the graph should be built, if it is to be built from two permutations/lists.

    When first_permutation is None (default), it is set to be equal to sorted(second_permutation), which yields the expected ordering when the elements of the graph are integers.

See also

  • Recognition of Permutation graphs in the comparability module.

  • Drawings of permutation graphs as intersection graphs of segments is possible through the show() method of Permutation objects.

    The correct argument to use in this case is show(representation = "braid").

  • inversions()

EXAMPLES:

sage: p = Permutations(5).random_element()
sage: PG = graphs.PermutationGraph(p)
sage: edges = PG.edges(sort=True, labels=False)
sage: set(edges) == set(p.inverse().inversions())
True

sage: PG = graphs.PermutationGraph([3,4,5,1,2])
sage: sorted(PG.edges(sort=True))
[(1, 3, None),
 (1, 4, None),
 (1, 5, None),
 (2, 3, None),
 (2, 4, None),
 (2, 5, None)]
sage: PG = graphs.PermutationGraph([3,4,5,1,2], [1,4,2,5,3])
sage: sorted(PG.edges(sort=True))
[(1, 3, None),
 (1, 4, None),
 (1, 5, None),
 (2, 3, None),
 (2, 5, None),
 (3, 4, None),
 (3, 5, None)]
sage: PG = graphs.PermutationGraph([1,4,2,5,3], [3,4,5,1,2])
sage: sorted(PG.edges(sort=True))
[(1, 3, None),
 (1, 4, None),
 (1, 5, None),
 (2, 3, None),
 (2, 5, None),
 (3, 4, None),
 (3, 5, None)]

sage: PG = graphs.PermutationGraph(Permutation([1,3,2]), Permutation([1,2,3]))
sage: sorted(PG.edges(sort=True))
[(2, 3, None)]

sage: graphs.PermutationGraph([]).edges(sort=True)
[]
sage: graphs.PermutationGraph([], []).edges(sort=True)
[]

sage: PG = graphs.PermutationGraph("graph", "phrag")
sage: sorted(PG.edges(sort=True))
[('a', 'g', None),
 ('a', 'h', None),
 ('a', 'p', None),
 ('g', 'h', None),
 ('g', 'p', None),
 ('g', 'r', None),
 ('h', 'r', None),
 ('p', 'r', None)]
sage.graphs.generators.intersection.ToleranceGraph(tolrep)#

Return the graph generated by the tolerance representation tolrep.

The tolerance representation tolrep is described by the list \(((l_0,r_0,t_0), (l_1,r_1,t_1), \ldots, (l_k,r_k,t_k))\) where \(I_i = (l_i,r_i)\) denotes a closed interval on the real line with \(l_i < r_i\) and \(t_i\) a strictly positive value, called tolerance. This representation generates the tolerance graph with the vertex set \(\{0,1, \ldots, k\}\) and the edge set \(\{(i,j): |I_i \cap I_j| \ge \min\{t_i, t_j\}\}\) where \(|I_i \cap I_j|\) denotes the length of the intersection of \(I_i\) and \(I_j\).

INPUT:

  • tolrep – list of triples \((l_i,r_i,t_i)\) where \((l_i,r_i)\) denotes a closed interval on the real line and \(t_i\) a positive value.

Note

The vertices are named \(0, 1, \ldots, k\). The tolerance representation used to create the graph is saved with the graph and can be recovered using get_vertex() or get_vertices().

EXAMPLES:

The following code creates a tolerance representation tolrep, generates its tolerance graph g, and applies some checks:

sage: tolrep = [(1,4,3),(1,2,1),(2,3,1),(0,3,3)]
sage: g = graphs.ToleranceGraph(tolrep)
sage: g.get_vertex(3)
(0, 3, 3)
sage: neigh = g.neighbors(3)
sage: for v in neigh: print(g.get_vertex(v))
(1, 2, 1)
(2, 3, 1)
sage: g.is_interval()
False
sage: g.is_weakly_chordal()
True

The intervals in the list need not be distinct

sage: tolrep2 = [(0,4,5),(1,2,1),(2,3,1),(0,4,5)]
sage: g2 = graphs.ToleranceGraph(tolrep2)
sage: g2.get_vertices()
{0: (0, 4, 5), 1: (1, 2, 1), 2: (2, 3, 1), 3: (0, 4, 5)}
sage: g2.is_isomorphic(g)
True

Real values are also allowed

sage: tolrep = [(0.1,3.3,4.4),(1.1,2.5,1.1),(1.4,4.4,3.3)]
sage: g = graphs.ToleranceGraph(tolrep)
sage: g.is_isomorphic(graphs.PathGraph(3))
True