Definition
Let {I1, I2, ..., In} ⊂ P(R) be a set of intervals.
The corresponding interval graph is G = (V, E), where
- V = {I1, I2, ..., In}, and
- {Iα, Iβ} ∈ E if and only if Iα ∩ Iβ ≠ ∅.
From this construction one can verify a common property held by all interval graphs. That is, graph G is an interval graph if and only if the maximal cliques of G can be ordered M1, M2, ..., Mk such that for any v ∈ Mi ∩ Mk, where i < k, it is also the case that v ∈ Mj for any Mj, i ≤ j ≤ k.
Read more about this topic: Interval Graph
Famous quotes containing the word definition:
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)