Jump to content

Talk:Median graph

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Examples: union of shortest tree paths

[edit]
Example tree

Section Median_graph#Examples says:

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.

However, for nodes Q, U, and X in the picture, the union of their shortest paths amounts to the subtree rooted at V (this node has degree 2). That is, the union is neither itself a path, nor a subtree formed by three paths meeting at a single central node with degree three. Did I misunderstand something, or are there some cases missing in the argument about trees being median graphs? - Jochen Burghardt (talk) 19:31, 3 October 2013 (UTC)[reply]

The sentence in question is about trees viewed as undirected graphs, rather than rooted trees viewed as directed graphs. In your example, the subtree formed by the union of paths for Q, U, and X consists of three paths meeting at the degree-three node S. —David Eppstein (talk) 20:14, 3 October 2013 (UTC)[reply]
Ah ok, now I see. Thank you for your explanation. - Jochen Burghardt (talk) 20:24, 3 October 2013 (UTC)[reply]

Etymology

[edit]

Lack of word derivations makes it hard for me to remember things. In the name 'median graph', I can see where 'graph' is coming from. I can't see where 'median' is coming from.

Does someone with access to the Nebeský paper, or a general grasp on the field, want to write something about that? ArthurDent006.5 (talk) 01:46, 26 November 2015 (UTC)[reply]

My guess is that it comes from long before Nebeský, in the work of Sholander on median algebras in the early 1950s. But it's really simple: the median of three numbers is the one whose value is in the middle of the other two, and the median operation on triples of vertices in graphs is a generalization of the same three-way median on numbers. —David Eppstein (talk) 02:23, 26 November 2015 (UTC)[reply]