Equivalent Definitions
In an arbitrary graph, for each two vertices a and b, define the interval of vertices that lie on shortest paths
- I(a,b) = {v | d(a,b) = d(a,v) + d(v,b)}.
A median graph is defined by the property that, for every three vertices a, b, and c, these intervals intersect in a single point:
- For all a, b, and c, |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.
Equivalently, for every three vertices a, b, and c one can find a vertex m(a,b,c) such that the unweighted distances in the graph satisfy the equalities
- d(a,b) = d(a,m(a,b,c)) + d(m(a,b,c),b)
- d(a,c) = d(a,m(a,b,c)) + d(m(a,b,c),c)
- d(b,c) = d(b,m(a,b,c)) + d(m(a,b,c),c)
and m(a,b,c) is the only vertex for which this is true.
It is also possible to define median graphs as the solution sets of 2-satisfiability problems, as the retracts of hypercubes, as the graphs of finite median algebras, as the Buneman graphs of Helly split systems, and as the graphs of windex 2; see the sections below.
Read more about this topic: Median Graph
Famous quotes containing the words equivalent and/or definitions:
“Nobody can deny but religion is a comfort to the distressed, a cordial to the sick, and sometimes a restraint on the wicked; therefore whoever would argue or laugh it out of the world without giving some equivalent for it ought to be treated as a common enemy.”
—Mary Wortley, Lady Montagu (1689–1762)
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)