Median graph
As Chung, Graham, and Saks write, "median graphs arise naturally in the study of ordered sets and discrete distributive lattices, and have an extensive literature".
[3] Additional surveys of median graphs are given by Klavžar & Mulder (1999), Bandelt & Chepoi (2008), and Knuth (2008).
[7] The simplex graph κ(G) of an arbitrary undirected graph G has a vertex for every clique (complete subgraph) of G; two vertices of κ(G) are linked by an edge if the corresponding cliques differ by one vertex of G .
In an arbitrary graph, for each two vertices a and b, the minimal number of edges between them is called their distance, denoted by d(x,y).
In a distributive lattice, Birkhoff's self-dual ternary median operation[9] satisfies certain key axioms, which it shares with the usual median of numbers in the range from 0 to 1 and with median algebras more generally: The distributive law may be replaced by an associative law:[10] The median operation may also be used to define a notion of intervals for distributive lattices: The graph of a finite distributive lattice has an edge between vertices a and b whenever I(a,b) = {a,b}.
[13] Duffus & Rival (1983) characterize graphs of distributive lattices directly as diameter-preserving retracts of hypercubes.
Every ternary operation on a finite set that satisfies these three properties (but that does not necessarily have 0 and 1 elements) gives rise in the same way to a median graph.
A particularly important family of convex sets in a median graph, playing a role similar to that of halfspaces in Euclidean space, are the sets defined for each edge uv of the graph.
The Helly property for the sets Wuv plays a key role in the characterization of median graphs as the solution of 2-satisfiability instances, below.
Conversely, every median graph G may be represented in this way as the solution set to a 2-satisfiability instance.
To find such a representation, create a 2-satisfiability instance in which each variable describes the orientation of one of the edges in the graph (an assignment of a direction to the edge causing the graph to become directed rather than undirected) and each constraint allows two edges to share a pair of orientations only when there exists a vertex v such that both orientations lie along shortest paths from other vertices to v. Each vertex v of G corresponds to a solution to this 2-satisfiability instance in which all edges are directed towards v. Each solution to the instance must come from some vertex v in this way, where v is the common intersection of the sets Wuw for edges directed from w to u; this common intersection exists due to the Helly property of the sets Wuw.
Therefore, the solutions to this 2-satisfiability instance correspond one-for-one with the vertices of G. A retraction of a graph G is an adjacency-preserving map from G to one of its subgraphs.
In other words, the family of median graphs is closed under the retraction operation.
This transformation preserves the computational complexity of the problem, for the size of H is proportional to that of G. The reduction in the other direction, from triangle detection to median graph testing, is more involved and depends on the previous median graph recognition algorithm of Hagauer, Imrich & Klavžar (1999), which tests several necessary conditions for median graphs in near-linear time.
The key new step involves using a breadth first search to partition the graph's vertices into levels according to their distances from some arbitrarily chosen root vertex, forming a graph from each level in which two vertices are adjacent if they share a common neighbor in the previous level, and searching for triangles in these graphs.
If a tree with perfect phylogeny is not possible, it is often desired to find one exhibiting maximum parsimony, or equivalently, minimizing the number of times the endpoints of a tree edge have different values for one of the characteristics, summed over all edges and all characteristics.
Buneman (1971) described a method for inferring perfect phylogenies for binary characteristics, when they exist.
His method generalizes naturally to the construction of a median graph for any set of species and binary characteristics, which has been called the median network or Buneman graph[24] and is a type of phylogenetic network.
