IntervalGraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

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.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.
 • The GraphTheory[IntervalGraph] command was updated in Maple 2020.
 • The GraphTheory[IsIntervalGraph] command was introduced in Maple 2022.
 • For more information on Maple 2022 changes, see Updates in Maple 2022.