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:
“Perhaps basketball and poetry have just a few things in common, but the most important is the possibility of transcendence. The opposite is labor. In writing, every writer knows when he or she is laboring to achieve an effect. You want to get from here to there, but find yourself willing it, forcing it. The equivalent in basketball is aiming your shot, a kind of strained and usually ineffective purposefulness. What you want is to be in some kind of flow, each next moment a discovery.”
—Stephen Dunn (b. 1939)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)