Median graph
In
The concept of median graphs has long been studied, for instance by
Additional surveys of median graphs are given by Klavžar & Mulder (1999), Bandelt & Chepoi (2008), and Knuth (2008).
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 a, b, and c 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 m(a,b,c) is equal to one of a, b, or c, 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.[4]
Additional examples of median graphs are provided by the
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.[6] A polyomino is a special case of a squaregraph and therefore also forms a median graph.[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 . 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.[8]
No cycle graph of length other than four can be a median graph. Every such cycle has three vertices a, b, and c 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 a and b, the minimal number of edges between them is called their distance, denoted by d(x,y). The interval of vertices that lie on shortest paths between a and b is defined as
- 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
- 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.
Distributive lattices and median algebras
In
In a distributive lattice, Birkhoff's self-dual ternary median operation[9]
- m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c),
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:
- Idempotence: for all a and b.
- Commutativity: m(a, b, c) for all a, b, and c.
- Distributivity: for all a, b, c, d, and e.
- Identity elements: m(0,a,1) = a for all a.
The distributive law may be replaced by an associative law:[10]
- Associativity: m(x,w,m(y,w,z)) = m(m(x,w,y),w,z)
The median operation may also be used to define a notion of intervals for distributive lattices:
- I(a,b) = {x | m(a,x,b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.[11]
The graph of a finite distributive lattice has an edge between vertices a and b whenever I(a,b) = {a,b}. For every two vertices a and b of this graph, the interval I(a,b) defined in lattice-theoretic terms above consists of the vertices on shortest paths from a to b, and thus coincides with the graph-theoretic intervals defined earlier. For every three lattice elements a, b, and c, m(a,b,c) is the unique intersection of the three intervals I(a,b), I(a,c), and I(b,c).[12] Therefore, the graph of an arbitrary finite distributive lattice is a median graph. Conversely, if a median graph G contains two vertices 0 and 1 such that every other vertex lies on a shortest path between the two (equivalently, m(0,a,1) = a for all a), then we may define a distributive lattice in which a ∧ b = m(a,0,b) and a ∨ b = m(a,1,b), and G will be the graph of this lattice.[13]
Duffus & Rival (1983) characterize graphs of distributive lattices directly as diameter-preserving retracts of hypercubes. More generally, every median graph gives rise to a ternary operation m 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 0 and 1 elements) gives rise in the same way to a median graph.[14]
Convex sets and Helly families
In a median graph, a set S of vertices is said to be convex if, for every two vertices a and b belonging to S, the whole interval I(a,b) is a subset of S. Equivalently, given the two definitions of intervals above, S 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 S. Observe that the intersection of every pair of convex sets is itself convex.[15]
The convex sets in a median graph have the
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
- Wuv = {w | d(w,u) < d(w,v)}
defined for each edge uv of the graph. In words, Wuv consists of the vertices closer to u than to v, or equivalently the vertices w such that some shortest path from v to w goes through u. To show that Wuv is convex, let w1w2...wk be an arbitrary shortest path that starts and ends within Wuv; then w2 must also lie within Wuv, for otherwise the two points m1 = m(u,w1,wk) and m2 = m(m1,w2...wk) could be shown (by considering the possible distances between the vertices) to be distinct medians of u, w1, and wk, 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 Wuv also lies within Wuv, so Wuv contains all shortest paths between its nodes, one of the definitions of convexity.
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.
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.[17]
A 2-satisfiability instance consists of a collection of
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 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.
Retracts of hypercubes
A retraction of a graph G is an adjacency-preserving map from G to one of its subgraphs.[18] More precisely, it is graph homomorphism φ from G to itself such that φ(v) = v for each vertex v in the subgraph φ(G). The image of the retraction is called a retract of G. Retractions are examples of metric maps: the distance between φ(v) and φ(w), for every v and w, is at most equal to the distance between v and w, and is equal whenever v and w both belong to φ(G). Therefore, a retract must be an isometric subgraph of G: distances in the retract equal those in G.
If G is a median graph, and a, b, and c are an arbitrary three vertices of a retract φ(G), then φ(m(a,b,c)) must be a median of a, b, and c, and so must equal m(a,b,c). Therefore, φ(G) 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.[19]
A
Conversely, every median graph must be the retract of a hypercube.[20] This may be seen from the connection, described above, between median graphs and 2-satisfiability: let G be the graph of solutions to a 2-satisfiability instance; without loss of generality this instance can be formulated in such a way that no two variables are always equal or always unequal in every solution. Then the space of all truth assignments to the variables of this instance forms a hypercube. For each clause, formed as the disjunction of two variables or their complements, in the 2-satisfiability instance, one can form a retraction of the hypercube in which truth assignments violating this clause are mapped to truth assignments in which both variables satisfy the clause, without changing the other variables in the truth assignment. The composition of the retractions formed in this way for each of the clauses gives a retraction of the hypercube onto the solution space of the instance, and therefore gives a representation of G 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 Imrich & Klavžar (2000) describe, an isometric embedding of a median graph into a hypercube may be constructed in time O(m log n), where n and m are the numbers of vertices and edges of the graph respectively.[21]
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 Imrich, Klavžar & Mulder (1999) observed that, in some sense, they are computationally equivalent.[22] Therefore, the best known time bound for testing whether a graph is triangle-free, O(m1.41),[23] 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.
In one direction, suppose one is given as input a graph G, and must test whether G is triangle-free. From G, construct a new graph H having as vertices each set of zero, one, or two adjacent vertices of G. Two such sets are adjacent in H when they differ by exactly one vertex. An equivalent description of H is that it is formed by splitting each edge of G into a path of two edges, and adding a new vertex connected to all the original vertices of G. This graph H is by construction a partial cube, but it is a median graph only when G is triangle-free: if a, b, and c form a triangle in G, then {a,b}, {a,c}, and {b,c} have no median in H, for such a median would have to correspond to the set {a,b,c}, but sets of three or more vertices of G do not form vertices in H. Therefore, G is triangle-free if and only if H is a median graph. In the case that G is triangle-free, H is its simplex graph. An algorithm to test efficiently whether H is a median graph could by this construction also be used to test whether G is triangle-free. 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
Evolutionary trees, Buneman graphs, and Helly split systems
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. 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
Bandelt et al. (1995) and Bandelt, Macaulay & Richards (2000) 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 needed to optimally solve a problem in which one is given a sequence of graph vertices si, and must find as output another sequence of vertices ti minimizing the sum of the distances d(si, ti) and d(ti − 1, ti). Median graphs are exactly the graphs that have windex 2. In a median graph, the optimal choice is to set ti = m(ti − 1, si, si + 1).[1]
- The property of having a unique median is also called the unique Steiner point property.Condorcet criterion for the winner of an election: compared to any other vertex, it is closer to a majority of the vertices in S.
- As with partial cubes more generally, every median graph with n vertices has at most (n/2) log2 n edges. However, the number of edges cannot be too small: Klavžar, Mulder & Škrekovski (1998) prove that in every median graph the inequality 2n − m − k ≤ 2 holds, where m is the number of edges and k 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 Σ (-1)dim(Q) is always equal to one, where the sum is taken over all hypercube subgraphs Q of the given median graph.[26]
- The only regular median graphs are the hypercubes.[27]
- 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.[28]
Notes
- ^ a b c Chung, Graham & Saks (1987).
- ^ Buneman (1971); Dress et al. (1997); Dress, Huber & Moulton (1997).
- ^ Bandelt & Barthélémy (1984); Day & McMorris (2003).
- ^ Imrich & Klavžar (2000), Proposition 1.26, p. 24.
- ^ This follows immediately from the characterization of median graphs as retracts of hypercubes, described below.
- ^ Soltan, Zambitskii & Prisăcaru (1973); Chepoi, Dragan & Vaxès (2002); Chepoi, Fanciullini & Vaxès (2004).
- ^ Klavžar & Škrekovski (2000).
- ^ Barthélemy, Leclerc & Monjardet (1986), page 200.
- ^ Birkhoff & Kiss (1947) credit the definition of this operation to Birkhoff, G. (1940), Lattice Theory, American Mathematical Society, p. 74.
- ^ Knuth (2008), p. 65, and exercises 75 and 76 on pp. 89–90. Knuth states that a simple proof that associativity implies distributivity remains unknown.
- ^ 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 Birkhoff & Kiss (1947).
- ^ Birkhoff & Kiss (1947), Theorem 2.
- ^ Birkhoff & Kiss (1947), p. 751.
- ^ Avann (1961).
- ^ Knuth (2008) 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.
- ^ Imrich & Klavžar (2000), Theorem 2.40, p. 77.
- ^ Bandelt & Chepoi (2008), Proposition 2.5, p.8; Chung, Graham & Saks (1989); Feder (1995); Knuth (2008), Theorem S, p. 72.
- ^ Hell (1976).
- ^ Imrich & Klavžar (2000), Proposition 1.33, p. 27.
- ^ Bandelt (1984); Imrich & Klavžar (2000), Theorem 2.39, p.76; Knuth (2008), p. 74.
- ^ The technique, which culminates in Lemma 7.10 on p.218 of Imrich and Klavžar, consists of applying an algorithm of Chiba & Nishizeki (1985) to list all 4-cycles in the graph G, forming an undirected graph having as its vertices the edges of G and having as its edges the opposite sides of a 4-cycle, and using the connected components of this derived graph to form hypercube coordinates. An equivalent algorithm is Knuth (2008), Algorithm H, p. 69.
- ^ For previous median graph recognition algorithms, see Jha & Slutzki (1992), Imrich & Klavžar (1998), and Hagauer, Imrich & Klavžar (1999). For triangle detection algorithms, see Itai & Rodeh (1978), Chiba & Nishizeki (1985), and Alon, Yuster & Zwick (1995).
- ^ Alon, Yuster & Zwick (1995), based on fast matrix multiplication. Here m is the number of edges in the graph, and the big O notation hides a large constant factor; the best practical algorithms for triangle detection take time O(m3/2). For median graph recognition, the time bound can be expressed either in terms of m or n (the number of vertices), as m = O(n log n).
- ^ Mulder & Schrijver (1979) described a version of this method for systems of characteristics not requiring any latent vertices, and Barthélémy (1989) gives the full construction. The Buneman graph name is given in Dress et al. (1997) and Dress, Huber & Moulton (1997).
- ^ Mulder & Schrijver (1979).
- ^ Škrekovski (2001).
- ^ Mulder (1980).
- ^ Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
References
- S2CID 208936467.
- Avann, S. P. (1961), "Metric ternary distributive semi-lattices", MR 0125807.
- Bandelt, Hans-Jürgen (1984), "Retracts of hypercubes", MR 0766499.
- Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), "Medians in median graphs", MR 0743019.
- Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Metric graph theory and geometry: a survey" (PDF), Surveys on Discrete and Computational Geometry, Contemporary Mathematics, vol. 453, Providence, RI: American Mathematical Society, pp. 49–86, MR 2405677.
- Bandelt, Hans-Jürgen; Forster, P.; Sykes, B. C.; Richards, Martin B. (October 1, 1995), "Mitochondrial portraits of human populations using median networks", PMID 8647407.
- Bandelt, Hans-Jürgen; Forster, P.; Rohl, Arne (January 1, 1999), "Median-joining networks for inferring intraspecific phylogenies", PMID 10331250, archived from the originalon December 27, 2005.
- Bandelt, Hans-Jürgen; Macaulay, Vincent; Richards, Martin B. (2000), "Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA", PMID 10877936.
- Barthélémy, Jean-Pierre (1989), "From copair hypergraphs to median graphs with latent vertices", MR 1002234.
- Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, S2CID 6092438.
- MR 0021540.
- Buneman, P. (1971), "The recovery of trees from measures of dissimilarity", in Hodson, F. R.; Kendall, D. G.; Tautu, P. T. (eds.), Mathematics in the Archaeological and Historical Sciences, Edinburgh University Press, pp. 387–395.
- Chepoi, V.; Dragan, F.; Vaxès, Y. (2002), "Center and diameter problems in planar quadrangulations and triangulations", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, Soda '02, pp. 346–355, ISBN 9780898715132.
- Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004), "Median problem in some plane triangulations and quadrangulations", .
- Chiba, N.; MR 0774940.
- MR 0910939.
- S2CID 5419897.
- Day, William H. E.; McMorris, F. R. (2003), Axiomatic Consensus Theory in Group Choice and Bioinformatics, Society for Industrial and Applied Mathematics, pp. 91–94, ISBN 978-0-89871-551-4.
- Dress, A.; Hendy, M.; Huber, K.; Moulton, V. (1997), "On the number of vertices and edges of the Buneman graph", S2CID 120716928.
- Dress, A.; Huber, K.; Moulton, V. (1997), "Some variations on a theme by Buneman", S2CID 122966547.
- JSTOR 2044697.
- Feder, T. (1995), Stable Networks and Product Graphs, Memoirs of the American Mathematical Society, vol. 555.
- Hagauer, Johann; Imrich, Wilfried; Klavžar, Sandi (1999), "Recognizing median graphs in subquadratic time", MR 1678773.
- MR 0543779.
- Imrich, Wilfried; Klavžar, Sandi (1998), "A convexity lemma and expansion procedures for bipartite graphs", MR 1642702.
- Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, MR 0788124.
- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", MR 1666073.
- Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", MR 0508603.
- Jha, Pranava K.; Slutzki, Giora (1992), "Convex-expansion algorithms for recognizing and isometric embedding of median graphs", MR 1206551.
- Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs: characterizations, location theory and related structures", Journal of Combinatorial Mathematics and Combinatorial Computing, 30: 103–127, MR 1705337.
- Klavžar, Sandi; Mulder, Henry Martyn; Škrekovski, Riste (1998), "An Euler-type formula for median graphs", MR 1630736.
- Klavžar, Sandi; Škrekovski, Riste (2000), "On median graphs and median grid graphs", MR 1761732.
- ISBN 978-0-321-53496-5.
- Mulder, Henry Martyn (1980), "n-cubes and median graphs", MR 0558458.
- Mulder, Henry Martyn; MR 0522746.
- Nebeský, Ladislav (1971), "Median graphs", Commentationes Mathematicae Universitatis Carolinae, 12: 317–325, MR 0286705.
- Škrekovski, Riste (2001), "Two relations for median graphs", MR 1802603.
- Soltan, P.; Zambitskii, D.; Prisăcaru, C. (1973), Extremal problems on graphs and algorithms of their solution (in Russian), Chişinău: Ştiinţa.
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.