# Intersection graphs#

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

sage.graphs.generators.intersection.IntersectionGraph(S)[source]#

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

>>> from sage.all import *
>>> graphs.IntersectionGraph([(Integer(1),Integer(2),Integer(3)),(Integer(3),Integer(4),Integer(5)),(Integer(5),Integer(6),Integer(7))])
Intersection Graph: Graph on 3 vertices

sage.graphs.generators.intersection.IntervalGraph(intervals, points_ordered=False)[source]#

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

>>> from sage.all import *
>>> intervals = [(i,i+Integer(2)) for i in range(Integer(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)

>>> from sage.all import *
>>> g = graphs.IntervalGraph(intervals)
>>> g.get_vertex(Integer(3))
(3, 5)
>>> neigh = g.neighbors(Integer(3))
>>> 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

>>> from sage.all import *
>>> 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)}

>>> from sage.all import *
>>> intervals = [ (Integer(1),Integer(2)), (Integer(1),Integer(2)), (Integer(1),Integer(2)), (Integer(2),Integer(3)), (Integer(3),Integer(4)) ]
>>> g = graphs.IntervalGraph(intervals,True)
>>> g.clique_maximum()
[0, 1, 2, 3]
>>> 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

>>> from sage.all import *
>>> rev_intervals = [ (Integer(2),Integer(1)), (Integer(2),Integer(1)), (Integer(2),Integer(1)), (Integer(3),Integer(2)), (Integer(4),Integer(3)) ]
>>> h = graphs.IntervalGraph(rev_intervals,False)
>>> h.get_vertices()
{0: (2, 1), 1: (2, 1), 2: (2, 1), 3: (3, 2), 4: (4, 3)}
>>> g.edges(sort=True) == h.edges(sort=True)
True

sage.graphs.generators.intersection.OrthogonalArrayBlockGraph(k, n, OA=None)[source]#

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.

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)

>>> from sage.all import *
>>> # needs sage.modules
>>> G = graphs.OrthogonalArrayBlockGraph(Integer(5),Integer(5)); G                              # needs sage.schemes
OA(5,5): Graph on 25 vertices
>>> G.is_strongly_regular(parameters=True)                                    # needs sage.schemes
(25, 20, 15, 20)
>>> G = graphs.OrthogonalArrayBlockGraph(Integer(4),Integer(10)); G
OA(4,10): Graph on 100 vertices
>>> 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

>>> from sage.all import *
>>> # needs sage.modules
>>> k = Integer(4); n = Integer(10)
>>> OAa = designs.orthogonal_arrays.build(k,n)
>>> OAb = [[(x+Integer(1))%n for x in R] for R in OAa]
>>> set(map(tuple,OAa)) == set(map(tuple,OAb))
False
>>> Ga = graphs.OrthogonalArrayBlockGraph(k, n, OAa)
>>> Gb = graphs.OrthogonalArrayBlockGraph(k, n, OAb)
>>> 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

>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> oa0 = [[Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(3)], [Integer(0), Integer(2), Integer(0)], [Integer(0), Integer(3), Integer(2)],
...        [Integer(1), Integer(0), Integer(3)], [Integer(1), Integer(1), Integer(1)], [Integer(1), Integer(2), Integer(2)], [Integer(1), Integer(3), Integer(0)],
...        [Integer(2), Integer(0), Integer(0)], [Integer(2), Integer(1), Integer(2)], [Integer(2), Integer(2), Integer(1)], [Integer(2), Integer(3), Integer(3)],
...        [Integer(3), Integer(0), Integer(2)], [Integer(3), Integer(1), Integer(0)], [Integer(3), Integer(2), Integer(3)], [Integer(3), Integer(3), Integer(1)]]
>>> oa1 = [[Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(1), Integer(0)], [Integer(0), Integer(2), Integer(3)], [Integer(0), Integer(3), Integer(2)],
...        [Integer(1), Integer(0), Integer(3)], [Integer(1), Integer(1), Integer(2)], [Integer(1), Integer(2), Integer(0)], [Integer(1), Integer(3), Integer(1)],
...        [Integer(2), Integer(0), Integer(0)], [Integer(2), Integer(1), Integer(1)], [Integer(2), Integer(2), Integer(2)], [Integer(2), Integer(3), Integer(3)],
...        [Integer(3), Integer(0), Integer(2)], [Integer(3), Integer(1), Integer(3)], [Integer(3), Integer(2), Integer(1)], [Integer(3), Integer(3), Integer(0)]]
>>> g0 = graphs.OrthogonalArrayBlockGraph(Integer(3), Integer(4), oa0)                          # needs sage.modules
>>> g1 = graphs.OrthogonalArrayBlockGraph(Integer(3), Integer(4), oa1)                          # needs sage.modules
>>> 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]

>>> from sage.all import *
>>> 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]
>>> 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

>>> from sage.all import *
>>> graphs.AffineOrthogonalPolarGraph(Integer(4),Integer(2),'+').is_isomorphic(g0)              # needs sage.libs.gap sage.modules
True

sage.graphs.generators.intersection.PermutationGraph(second_permutation, first_permutation=None)[source]#

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.

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

>>> from sage.all import *
>>> p = Permutations(Integer(5)).random_element()
>>> PG = graphs.PermutationGraph(p)
>>> edges = PG.edges(sort=True, labels=False)
>>> set(edges) == set(p.inverse().inversions())
True

>>> PG = graphs.PermutationGraph([Integer(3),Integer(4),Integer(5),Integer(1),Integer(2)])
>>> sorted(PG.edges(sort=True))
[(1, 3, None),
(1, 4, None),
(1, 5, None),
(2, 3, None),
(2, 4, None),
(2, 5, None)]
>>> PG = graphs.PermutationGraph([Integer(3),Integer(4),Integer(5),Integer(1),Integer(2)], [Integer(1),Integer(4),Integer(2),Integer(5),Integer(3)])
>>> 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)]
>>> PG = graphs.PermutationGraph([Integer(1),Integer(4),Integer(2),Integer(5),Integer(3)], [Integer(3),Integer(4),Integer(5),Integer(1),Integer(2)])
>>> 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)]

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

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

>>> PG = graphs.PermutationGraph("graph", "phrag")
>>> 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)[source]#

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

>>> from sage.all import *
>>> tolrep = [(Integer(1),Integer(4),Integer(3)),(Integer(1),Integer(2),Integer(1)),(Integer(2),Integer(3),Integer(1)),(Integer(0),Integer(3),Integer(3))]
>>> g = graphs.ToleranceGraph(tolrep)
>>> g.get_vertex(Integer(3))
(0, 3, 3)
>>> neigh = g.neighbors(Integer(3))
>>> for v in neigh: print(g.get_vertex(v))
(1, 2, 1)
(2, 3, 1)
>>> g.is_interval()
False
>>> 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

>>> from sage.all import *
>>> tolrep2 = [(Integer(0),Integer(4),Integer(5)),(Integer(1),Integer(2),Integer(1)),(Integer(2),Integer(3),Integer(1)),(Integer(0),Integer(4),Integer(5))]
>>> g2 = graphs.ToleranceGraph(tolrep2)
>>> g2.get_vertices()
{0: (0, 4, 5), 1: (1, 2, 1), 2: (2, 3, 1), 3: (0, 4, 5)}
>>> 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

>>> from sage.all import *
>>> tolrep = [(RealNumber('0.1'),RealNumber('3.3'),RealNumber('4.4')),(RealNumber('1.1'),RealNumber('2.5'),RealNumber('1.1')),(RealNumber('1.4'),RealNumber('4.4'),RealNumber('3.3'))]
>>> g = graphs.ToleranceGraph(tolrep)
>>> g.is_isomorphic(graphs.PathGraph(Integer(3)))
True