In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices , , and have a unique median: a vertex that belongs to shortest paths between each pair of , , and .
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 a median graph. To see this, observe that in a tree, the union of the three shortest paths between pairs of the three vertices , , and is either itself a path, or a subtree formed by three paths meeting at a single central node with degree three. If the union of the three paths is itself a path, the median is equal to one of , , or , 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., Proposition 1.26, p. 24.
Additional examples of median graphs are provided by the grid graphs. In a grid graph, the coordinates of the median can be found as the median of the coordinates of , , and . 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.This follows immediately from the characterization of median graphs as retracts of hypercubes, described below.
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 of an arbitrary undirected graph has a vertex for every clique (complete subgraph) of ; two vertices of are linked by an edge if the corresponding cliques differ by one vertex of . 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., page 200.
No cycle graph of length other than four can be a median graph. Every such cycle has three vertices , , and 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 In an arbitrary graph, for each two vertices and , the minimal number of edges between them is called their distance, denoted by . The interval of vertices that lie on shortest paths between and is defined as
A median graph is defined by the property that, for every three vertices , , and , these intervals intersect in a single point: For all , , and ,
Equivalently, for every three vertices , , and one can find a vertex such that the unweighted distances in the graph satisfy the equalities
and 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, as the Buneman graphs of Helly split systems, and as the graphs of windex ; 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 drawings 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 credit the definition of this operation to .
satisfies certain key axioms, which it shares with the usual median of numbers in the range from to and with median algebras more generally: Idempotence: for all and . Commutativity: for all , , and . Distributivity: for all , , , , and . Identity elements: for all . The distributive law may be replaced by an associative law:, p. 65, and exercises 75 and 76 on pp. 89–90. Knuth states that a simple proof that associativity implies distributivity remains unknown. Associativity: The median operation may also be used to define a notion of intervals for distributive lattices:The equivalence between the two expressions in this equation, one in terms of the median operation and the other in terms of lattice operations and inequalities is Theorem 1 of .
The graph of a finite distributive lattice has an edge between vertices and whenever . For every two vertices and of this graph, the interval defined in lattice-theoretic terms above consists of the vertices on shortest paths from to , and thus coincides with the graph-theoretic intervals defined earlier. For every three lattice elements , , and , is the unique intersection of the three intervals , , and ., Theorem 2. Therefore, the graph of an arbitrary finite distributive lattice is a median graph. Conversely, if a median graph contains two vertices and such that every other vertex lies on a shortest path between the two (equivalently, for all ), then we may define a distributive lattice in which and , and will be the graph of this lattice., p. 751.
characterize graphs of distributive lattices directly as diameter-preserving retracts of hypercubes. More generally, every median graph gives rise to a ternary operation satisfying idempotence, commutativity, and distributivity, but possibly without the identity elements of a distributive lattice. Every ternary operation on a finite set that satisfies these three properties (but that does not necessarily have and elements) gives rise in the same way to a median graph..
Convex sets and Helly families In a median graph, a set of vertices is said to be convex if, for every two vertices and belonging to , the whole interval is a subset of . Equivalently, given the two definitions of intervals above, is convex if it contains every shortest path between two of its vertices, or if it contains the median of every set of three points at least two of which are from . Observe that the intersection of every pair of convex sets is itself convex. calls such a set an ideal, but a convex set in the graph of a distributive lattice is not the same thing as an ideal of the lattice.
The convex sets in a median graph have the Helly property: if is an arbitrary family of pairwise-intersecting convex sets, then all sets in have a common intersection., Theorem 2.40, p. 77. For, if has only three convex sets , , and in it, with in the intersection of the pair and , in the intersection of the pair and , and in the intersection of the pair and , then every shortest path from to must lie within by convexity, and similarly every shortest path between the other two pairs of vertices must lie within the other two sets; but belongs to paths between all three pairs of vertices, so it lies within all three sets, and forms part of their common intersection. If has more than three convex sets in it, the result follows by induction on the number of sets, for one may replace an arbitrary pair of sets in 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 halfspaces in Euclidean space, are the sets:
defined for each edge of the graph. In words, consists of the vertices closer to than to , or equivalently the vertices such that some shortest path from to goes through . To show that is convex, let be an arbitrary shortest path that starts and ends within ; then must also lie within , for otherwise the two points and could be shown (by considering the possible distances between the vertices) to be distinct medians of , , and , contradicting the definition of a median graph which requires medians to be unique. Thus, each successive vertex on a shortest path between two vertices of also lies within , so contains all shortest paths between its nodes, one of the definitions of convexity.
The Helly property for the sets 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., Proposition 2.5, p.8; ; ; , Theorem S, p. 72.
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.
Conversely, every median graph 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 such that both orientations lie along shortest paths from other vertices to . Each vertex of corresponds to a solution to this 2-satisfiability instance in which all edges are directed towards . Each solution to the instance must come from some vertex in this way, where is the common intersection of the sets for edges directed from to ; this common intersection exists due to the Helly property of the sets . Therefore, the solutions to this 2-satisfiability instance correspond one-for-one with the vertices of .
Retracts of hypercubes
A retraction of a graph is an adjacency-preserving map from to one of its subgraphs.. More precisely, it is a graph homomorphism from to itself such that for each vertex in the subgraph . The image of the retraction is called a retract of .
Retractions are examples of metric maps: the distance between and , for every and , is at most equal to the distance between and , and is equal whenever and both belong to . Therefore, a retract must be an isometric subgraph of : distances in the retract equal those in .