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:
“The notion that one will not survive a particular catastrophe is, in general terms, a comfort since it is equivalent to abolishing the catastrophe.”
—Iris Murdoch (b. 1919)
“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)