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:
“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)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)