In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices have a unique median that belongs to shortest paths.

The concept of median graphs has long been studied, for instance by or (more explicitly) by , but the first paper to call them "median graphs" appears to be . 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". In phylogenetics, the Buneman graph representing all maximum parsimony evolutionary trees is a median graph. Median graphs also arise in social choice theory: if a set of alternatives has the structure of a median graph, it is possible to derive in an unambiguous way a majority preference among them.

Additional surveys of median graphs are given by , , and .

Examples

Every tree is either itself a path, or a subtree formed by three paths meeting at a single central node with degree, whichever of these three vertices is between the other two in the path. If the subtree formed by the union of the three paths is not a path, the median of the three vertices is the central degree-three node of the subtree.

Additional examples of median graphs are provided by the grid graphs. Conversely, it turns out that, in every median graph, one may label the vertices by points in an integer lattice in such a way that medians can be calculated coordinatewise in this way.

Squaregraphs, planar graphs in which all interior faces are quadrilaterals and all interior vertices have four or more incident edges, are another subclass of the median graphs. A polyomino is a special case of a squaregraph and therefore also forms a median graph.

The simplex graph has a vertex for every clique . The simplex graph is always a median graph, in which the median of a given triple of cliques may be formed by using the majority rule to determine which vertices of the cliques to include.

No cycle graph such that the three shortest paths wrap all the way around the cycle without having a common intersection. For such a triple of vertices, there can be no median.

Equivalent definitions

, the minimal number of edges between them is called their distance. The interval

, these intervals intersect in a single point:

1. ,

such that the unweighted is the only vertex for which these equalities hold.

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; see the sections below.

Distributive lattices and median algebras

In lattice theory, the graph of a finite lattice has a vertex for each lattice element and an edge for each pair of elements in the covering relation of the lattice. Lattices are commonly presented visually via Hasse diagrams, which are drawingss of graphs of lattices. These graphs, especially in the case of distributive lattices, turn out to be closely related to median graphs.

In a distributive lattice, Birkhoff's self-dual ternary median operation satisfies certain key axioms, which it shares with the usual median and with median algebras more generally:

• Idempotence.

• Commutativity.

• Distributivity.

• Identity elements.

The distributive law may be replaced by an associative law:

• Associativity

The median operation may also be used to define a notion of intervals for distributive lattices:

. will be the graph of this lattice.

elements) gives rise in the same way to a median graph.

Convex sets and Helly families

of vertices is said to be convex. Observe that the intersection of every pair of convex sets is itself convex.

The convex sets in a median graph have the Helly property have a common intersection. by their intersection, using the result for triples of sets to show that the replaced family is still pairwise intersecting.

A particularly important family of convex sets in a median graph, playing a role similar to that of halfspacess in Euclidean space

contains all shortest paths between its nodes, one of the definitions of convexity.

plays a key role in the characterization of median graphs as the solution of 2-satisfiability instances, below.

2-satisfiability

Median graphs have a close connection to the solution sets of 2-satisfiability problems that can be used both to characterize these graphs and to relate them to adjacency-preserving maps of hypercubes.

A 2-satisfiability instance consists of a collection of Boolean variables and a collection of clauses, constraints on certain pairs of variables requiring those two variables to avoid certain combinations of values. Usually such problems are expressed in conjunctive normal form, in which each clause is expressed as a disjunction and the whole set of constraints is expressed as a conjunction of clauses, such as

A solution to such an instance is an assignment of truth values to the variables that satisfies all the clauses, or equivalently that causes the conjunctive normal form expression for the instance to become true when the variable values are substituted into it. The family of all solutions has a natural structure as a median algebra, where the median of three solutions is formed by choosing each truth value to be the majority function of the values in the three solutions; it is straightforward to verify that this median solution cannot violate any of the clauses. Thus, these solutions form a median graph, in which the neighbor of each solution is formed by negating a set of variables that are all constrained to be equal or unequal to each other.

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.

Retracts of hypercubes

A retraction to one of its subgraphs. More precisely, it is a graph homomorphism. The image of the retraction is called a retract.

Retractions are examples of metric maps. Therefore, a retract must be an isometric subgraph.

contains medians of all triples of its vertices, and must also be a median graph. In other words, the family of median graphs is closed under the retraction operation.

A hypercube graph-bit bitvectors may be calculated by computing, in each bit position, the majority function. Since median graphs are closed under retraction, and include the hypercubes, every retract of a hypercube is a median graph.

Conversely, every median graph must be the retract of a hypercube. be the graph of solutions to a 2-satisfiability instance; without loss of generality as the retract of a hypercube. In particular, median graphs are isometric subgraphs of hypercubes, and are therefore partial cubes. However, not all partial cubes are median graphs; for instance, a six-vertex cycle graph is a partial cube but is not a median graph.

As are the numbers of vertices and edges of the graph respectively.

Triangle-free graphs and recognition algorithms

The problems of testing whether a graph is a median graph, and whether a graph is triangle-free, both had been well studied when observed that, in some sense, they are computationally equivalent., applies as well to testing whether a graph is a median graph, and any improvement in median graph testing algorithms would also lead to an improvement in algorithms for detecting triangles in graphs.

is its simplex graph.

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 , which tests several necessary conditions for median graphs in near-linear time. The key new step involves using a breadth first search time, as some graphs have that many triangles, however Hagauer et al. show that the number of triangles arising in the level graphs of their reduction is near-linear, allowing the Alon et al. fast matrix multiplication based technique for finding triangles to be used.

Evolutionary trees, Buneman graphs, and Helly split systems

Phylogeny is the inference of evolutionary trees from observed characteristics of species; such a tree must place the species at distinct vertices, and may have additional latent vertices, but the latent vertices are required to have three or more incident edges and must also be labeled with characteristics. A characteristic is binary when it has only two possible values, and a set of species and their characteristics exhibit perfect phylogeny when there exists an evolutionary tree in which the vertices (species and latent vertices) labeled with any particular characteristic value form a contiguous subtree. 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.

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 and is a type of phylogenetic network. Every maximum parsimony evolutionary tree embeds into the Buneman graph, in the sense that tree edges follow paths in the graph and the number of characteristic value changes on the tree edge is the same as the number in the corresponding path. The Buneman graph will be a tree if and only if a perfect phylogeny exists; this happens when there are no two incompatible characteristics for which all four combinations of characteristic values are observed.

To form the Buneman graph for a set of species and characteristics, first, eliminate redundant species that are indistinguishable from some other species and redundant characteristics that are always the same as some other characteristic. Then, form a latent vertex for every combination of characteristic values such that every two of the values exist in some known species. In the example shown, there are small brown tailless mice, small silver tailless mice, small brown tailed mice, large brown tailed mice, and large silver tailed mice; the Buneman graph method would form a latent vertex corresponding to an unknown species of small silver tailed mice, because every pairwise combination (small and silver, small and tailed, and silver and tailed) is observed in some other known species. However, the method would not infer the existence of large brown tailless mice, because no mice are known to have both the large and tailless traits. Once the latent vertices are determined, form an edge between every pair of species or latent vertices that differ in a single characteristic.

One can equivalently describe a collection of binary characteristics as a split system, a family of sets having the property that the complement set of each set in the family is also in the family. This split system has a set for each characteristic value, consisting of the species that have that value. When the latent vertices are included, the resulting split system has the Helly property defined for each edge uv of a median graph form a Helly split system, so if one applies the Buneman graph construction to this system no latent vertices will be needed and the result will be the same as the starting graph.

and describe techniques for simplified hand calculation of the Buneman graph, and use this construction to visualize human genetic relationships.

Additional properties

• The Cartesian product of every two median graphs is another median graph. Medians in the product graph may be computed by independently finding the medians in the two factors, just as medians in grid graphs may be computed by independently finding the median in each linear dimension.

• The windex of a graph measures the amount of lookahead minimizing the sum of the distances and . Median graphs are exactly the graphs that have windex 2. In a median graph, the optimal choice is to set .

• The property of having a unique median is also called the unique Steiner point property. An optimal Steiner tree. study more generally the problem of finding the vertex minimizing the sum of distances of vertices in a median graph satisfies the Condorcet criterion for the winner of an election.

• edges. However, the number of edges cannot be too small: is the dimension of the hypercube that the graph is a retract of. This inequality is an equality if and only if the median graph contains no cubes. This is a consequence of another identity for median graphs: the Euler characteristic of the given median graph.

• The only regular median graphs are the hypercubes.

• Every median graph is a modular graph. The modular graphs are a class of graphs in which every triple of vertices has a median but the medians are not required to be unique.

Notes

References

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

External links

• Median graphs, Information System for Graph Class Inclusions.

• Network, Free Phylogenetic Network Software. Network generates evolutionary trees and networks from genetic, linguistic, and other data.

• PhyloMurka, open-source software for median network computations from biological data.