GraphTheory
IntervalGraph
construct an interval graph
Calling Sequence
Parameters
Description
Examples
Compatibility
IntervalGraph( c )
c
-
a list, Vector, or 1-D Array of intervals
The IntervalGraph( c ) command 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.
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 intersect.
Compute the interval graph for {1..3, 2..4, 3..5}.
with⁡GraphTheory:
G≔IntervalGraph⁡1..3,2..4,3..5
G≔Graph 1: an undirected unweighted graph with 3 vertices and 3 edge(s)
Construct a schedule to distribute a set of business meetings across several conference rooms.
Meetings≔9..11.5,9.5..10,9.75..15,11.5..15,12.5..13.5,14.5..17,16.5..17.5
RoomNames≔Suite Infinity,Geddes Suite,Taylor's Suite
Schedule≔GreedyColor⁡IntervalGraph⁡Meetings
Schedule≔3,1,2,0,2,1,1,0
Room≔i↦RoomNamesSchedule2ListTools:−Search⁡i,Meetings+1:
ListTools:-Classify⁡Room,Meetings
table⁡Suite Infinity=9.75..15,16.5..17.5,Taylor's Suite=9.5..10,11.5..15,Geddes Suite=9..11.5,12.5..13.5,14.5..17
The following interval graph has only edge because the intervals 0..1 and 1..2 intersect at 1, but the half-open interval −1,0 does not intersect 0..1.
IntervalGraph( [ RealRange(-1,Open(0)), 0..1, 1..2 ] );
Visualize the relationships within a set of intervals.
G≔IntervalGraph⁡0..8,1..π,exp⁡1..20,7..18,11..14,RealRange⁡17,Open⁡23,23..25
G≔Graph 2: an undirected unweighted graph with 7 vertices and 9 edge(s)
DrawGraph⁡G
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.
See Also
Download Help Document
What kind of issue would you like to report? (Optional)