IntervalGraph - Maple Help

GraphTheory

 IntervalGraph
 construct an interval graph
 IsIntervalGraph
 test if graph is an interval graph

 Calling Sequence IntervalGraph(C) IsIntervalGraph(G)

Parameters

 C - a list, Vector, or 1-D Array of intervals G - an undirected graph

Description

 • IntervalGraph(c) returns an interval graph for the collection of intervals C.
 • Each element of the input C must be a range or a RealRange expression. A range a..b is interpreted as the closed real interval from a to b. To specify open or half-open intervals, you can use RealRange.
 • The vertices of the resulting graph correspond to the intervals given in C. An edge between vertices exists if the corresponding intervals have non-empty intersection.
 • IsIntervalGraph(G) tests whether the graph G could be expressed as an interval graph for some collection of intervals.

Definition

 • An interval graph is the intersection graph of a set of intervals on the real line. For any vertices $i$, $j$ in the graph, an edge between $i$ and $j$ exists if and only if the intervals $i$ and $j$ have non-empty intersection.

Examples

Compute the interval graph for {1..3, 2..4, 3..5}.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{IntervalGraph}\left(\left[1..3,2..4,3..5\right]\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 3 vertices and 3 edge\left(s\right)}}$ (1)

Construct a schedule to distribute a set of business meetings across several conference rooms.

 > $\mathrm{Meetings}≔\left[9..11.5,9.5..10,9.75..15,11.5..15,12.5..13.5,14.5..17,16.5..17.5\right]$
 ${\mathrm{Meetings}}{≔}\left[{9}{..}{11.5}{,}{9.5}{..}{10}{,}{9.75}{..}{15}{,}{11.5}{..}{15}{,}{12.5}{..}{13.5}{,}{14.5}{..}{17}{,}{16.5}{..}{17.5}\right]$ (2)
 > $\mathrm{RoomNames}≔\left["Suite Infinity","Geddes Suite","Taylor\text{'}s Suite"\right]$
 ${\mathrm{RoomNames}}{≔}\left[{"Suite Infinity"}{,}{"Geddes Suite"}{,}{"Taylor\text{'}s Suite"}\right]$ (3)
 > $\mathrm{Schedule}≔\mathrm{GreedyColor}\left(\mathrm{IntervalGraph}\left(\mathrm{Meetings}\right)\right)$
 ${\mathrm{Schedule}}{≔}{3}{,}\left[{1}{,}{2}{,}{0}{,}{2}{,}{1}{,}{1}{,}{0}\right]$ (4)
 > $\mathrm{Room}≔i→{\mathrm{RoomNames}}_{{{\mathrm{Schedule}}_{2}}_{\mathrm{ListTools}:-\mathrm{Search}\left(i,\mathrm{Meetings}\right)}+1}:$
 > $\mathrm{ListTools}:-\mathrm{Classify}\left(\mathrm{Room},\mathrm{Meetings}\right)$
 ${table}{}\left(\left[{"Geddes Suite"}{=}\left\{{9}{..}{11.5}{,}{12.5}{..}{13.5}{,}{14.5}{..}{17}\right\}{,}{"Suite Infinity"}{=}\left\{{9.75}{..}{15}{,}{16.5}{..}{17.5}\right\}{,}{"Taylor\text{'}s Suite"}{=}\left\{{9.5}{..}{10}{,}{11.5}{..}{15}\right\}\right]\right)$ (5)

The following interval graph has only one edge because the intervals 0..1 and 1..2 intersect at 1, but the half-open interval $\left[-1,0\right)$ does not intersect 0..1.

 > $\mathrm{IntervalGraph}\left(\left[\mathrm{RealRange}\left(-1,\mathrm{Open}\left(0\right)\right),0..1,1..2\right]\right)$
 ${\mathrm{Graph 2: an undirected graph with 3 vertices and 1 edge\left(s\right)}}$ (6)

Visualize the relationships within a set of intervals.

 > $G≔\mathrm{IntervalGraph}\left(\left[0..8,1..\mathrm{Pi},ⅇ..20,7..18,11..14,\mathrm{RealRange}\left(17,\mathrm{Open}\left(23\right)\right),23..25\right]\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected graph with 7 vertices and 9 edge\left(s\right)}}$ (7)
 > $\mathrm{DrawGraph}\left(G\right)$

Verify this is an interval graph

 > $\mathrm{IsIntervalGraph}\left(G\right)$
 ${\mathrm{true}}$ (8)

Compatibility

 • The GraphTheory[IntervalGraph] command was introduced in Maple 2016.