Interval graph
|
|
In graph theory, an interval graph is a graph that captures the intersections among a set of intervals on the real line.
Formally, let
- <math>I_1, I_2, \ldots I_n \in R<math>
be a set of intervals. Then the corresponding interval graph is G = (V, E) where
- <math>V = \{I_1, I_2, \ldots I_n\}<math>
and
- <math> (I_\alpha, I_\beta) \in E \iff I_\alpha \cap I_\beta \neq \phi. <math>
That is, the nodes of the graph are the intervals and there is an edge corresponding to each pair of intersecting intervals.
Interval graphs are useful in modeling resource allocation problems in operations research. Each interval represents a request for a resource for a specific period of time.
External link
- Interval graph -- from Mathworld (http://mathworld.wolfram.com/IntervalGraph.html)