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:
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)
“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)