Metraipolis › archive › dc_f5e31a3db80d

Median graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Median_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-07T18:24:40.599Z
SHA-256 of the archived text
5bc9648216619aabb5a9b5f3d90cb42dbc6209f1c57a0408ce8b4c47a0a3d31b
Stable URL of this page
https://metraipolis.com/documento/dc_f5e31a3db80d

How to cite

Median graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Median_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f5e31a3db80d (Metraipolis archive dc_f5e31a3db80d, sha256 5bc9648216619aabb5a9b5f3d90cb42dbc6209f1c57a0408ce8b4c47a0a3d31b)
BibTeX
@misc{dcf5e31a3db80d,
  title = {Median graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Median_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f5e31a3db80d; sha256 5bc9648216619aabb5a9b5f3d90cb42dbc6209f1c57a0408ce8b4c47a0a3d31b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Median_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a {\displaystyle a} , b {\displaystyle b} , and c {\displaystyle c} have a unique median: a vertex m ( a , b , c ) {\displaystyle m(a,b,c)} that belongs to shortest paths between each pair of a {\displaystyle a} , b {\displaystyle b} , and c {\displaystyle c} . The concept of median graphs has long been studied, for instance by Birkhoff & Kiss (1947) or (more explicitly) by Avann (1961), but the first paper to call them "median graphs" appears to be Nebeský (1971). 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 Klavžar & Mulder (1999), Bandelt & Chepoi (2008), and Knuth (2008).

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Median graph» — https://en.wikipedia.org/wiki/Median_graph
Wikidata Q3115592: «graph with a unique median for each three vertices» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3115592
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Median_graph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1343824067, consultata il 2026-11-07T18:19:49.650Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a861314ec7da7ce7ae89b437411d181478ffed4527573a2cc545c236a3d9c381