Медианный граф

В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.

Концепция медианных графов изучалась с давних пор, например, Биргофом и Киссом (Birkhoff, Kiss 1947) или (более явно) Аванном (Avann 1961), но первая статья с именем «Медианные графы» появилась в 1971 (Nebesk'y 1971). Как пишут Чанг, Грэм и Сакс (Saks), «медианные графы возникают естественным образом при изучении упорядоченных множеств и дискретных дистрибутивных решёток и имеют обширную литературу». В филогенетике граф Бунемана, представляющий все максимально правдоподобные эволюционные деревья, является медианным графом. Медианные графы также появляются в теории социального выбора — если множество возможностей имеет структуру медианного графа, можно среди них определить недвусмысленно предпочтение большинства.

Обозрение медианных графов можно найти в книгах Klavžar, Mulder, 1999, Bandelt, Chepoi, 2008 и Knuth, 2008.