Content deleted Content added
Added free to read link in citations with OAbot #oabot |
|||
Line 112:
[[File:Graph-Cartesian-product.svg|thumb|upright=1.35|The [[Cartesian product of graphs]] forms a median graph from two smaller median graphs.]]
*The [[Cartesian product of graphs|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 [[Look-ahead (backtracking)|lookahead]] needed to optimally solve a problem in which one is given a sequence of graph vertices ''s<sub>i</sub>'', and must find as output another sequence of vertices ''t<sub>i</sub>'' minimizing the sum of the distances {{math|''d''(''s<sub>i</sub>, t<sub>i</sub>'')}} and {{math|''d''(''t''<sub>''i''
*The property of having a unique median is also called the ''unique Steiner point property''.<ref name="cgs"/> An optimal [[Steiner tree]] for three vertices ''a'', ''b'', and ''c'' in a median graph may be found as the union of three shortest paths, from ''a'', ''b'', and ''c'' to ''m''(''a'',''b'',''c''). {{harvtxt|Bandelt|Barthélémy|1984}} study more generally the problem of finding the vertex [[Geometric median|minimizing the sum of distances]] to each of a given set of vertices, and show that it has a unique solution for any odd number of vertices in a median graph. They also show that this median of a set ''S'' of vertices in a median graph satisfies the [[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) log<sub>2</sub> ''n'' edges. However, the number of edges cannot be too small: {{harvtxt|Klavžar|Mulder|Škrekovski|1998}} prove that in every median graph the inequality {{math|2''n''
*The only [[regular graph|regular]] median graphs are the hypercubes.<ref>{{harvtxt|Mulder|1980}}.</ref>
*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.<ref>[http://www.graphclasses.org/classes/gc_50.html Modular graphs], Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.</ref>
| |||