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
be a set of intervals. Then the corresponding interval graph is G = (V, E) where
and
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
Referenced By
List of graph theory topics
|
