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

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

Обозрение медианных графов можно найти в книгах , и .

Примеры

Любое дерево является медианным графом., Утверждение 1.26, стр. 24. В дереве объединение трёх кратчайших путей между парами трёх вершин a, b и c либо само по себе путь, либо поддерево, образованное тремя путями, идущими из одной центральной вершины, имеющей степень три. Если объединение трёх путей является само по себе путём, медиана m(a,b,c) равна одной из вершин a, b или c, в зависимости от того, какая вершина окажется между двумя другими на пути. Если дерево, образованное объединением путей, не является путём, медианой будет центральная вершина поддерева.

Другим примером медианных графов являются решётки. В графе-решётке координаты медианы m(a,b,c) можно найти как медиану координат вершин a, b и c. И наоборот, оказывается, что можно расположить вершины на целочисленной решётке так, что медианы можно вычислить как медианы координат .Это следует немедленно из свойства медианных графов как редукции гиперкуба, как описано ниже.

Рамочные графы, планарные графы, в которых все внутренние грани являются четырёхугольниками и все внутренние вершины имеют четыре и более инцидентных ребра, — это ещё один подкласс медианных графов., , . Полимино — это специальный случай рамочных графов, а потому тоже образует медианный граф.

κ(G) произвольного неориентированного графа G имеет вершину для каждой клики (полный подграф) графа G, и две вершины соединены ребром, если соответствующие клики отличаются только одной вершиной. Медиану заданных трёх клик можно образовать при помощи мажоритарного правила, позволяющего определить, какие вершины клик включать. Симплекс-граф — это медианный граф, в котором это правило определяет медиану каждой тройки вершин.

Никакой цикл длины, отличной от четырёх, не может быть медианным графом, поскольку любой такой цикл имеет три вершины a, b и c, которые соединены тремя кратчайшими путями, не имеющими пересечений.

Эквивалентные определения В произвольном графе для любых двух вершин a и b минимальное число рёбер между ними называется расстоянием, которое обозначается как d(x,y). Интервал вершин, лежащих на кратчайшем пути между a и b, определяется как I(a,b) = {v | d(a,b) = d(a, v) + d(v, b)}. Медианный граф определяется как граф, для любых трёх вершин a, b и c которого эти интервалы пересекаются в одной точке: Для всех a, b и c |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.

Таким же образом, для любых трёх вершин a, b и c можно найти вершину m(a,b,c), такую, что невзвешенное расстояния в графе удовлетворяют равенствам 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) и m(a,b,c) является единственной вершиной, для которой это верно.

Можно также определить медианные графы как решения задач 2-выполнимости, как редукцию гиперкубов, как графы конечных медианных алгебр, как графы Бунемана систем разбиения Хэлли, и как графы с виндексом (windex) 2. Смотрите разделы ниже.

Распределённые решётки и медианные алгебры

В теории решёток граф конечной решётки имеет вершину для каждого элемента решётки и ребро для каждой пары элементов решётки. Решётки обычно представляются визуально как диаграммы Хассе, которые являются рисунками графов решёток. Эти графы, особенно для дистрибутивных решёток, оказываются тесно связанными с медианными графами.

В дистрибутивной решётке Биркхофа самодвойственная тернарная операция медианы приписывают определение этой операции статье . m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c), удовлетворяет некоторым ключевым аксиомам, которые свойственны обычным медианам чисел в отрезке от 0 до 1 и : Идемпотентность: m(a, a, b) = a для всех a и b. Коммутативность: m(a,b,c) = m(a, c, b) = m(b, a, c) = m(b, c, a) = m(c, a, b) = m(c, b, a) для всех a, b, и c. Дистрибутивность: m(a, m(b, c, d), e) = m(m(a, b, e), c, m(a, d, e)) для всех a, b, c, d, и e. Нейтральные элементы: m(0,a,1) = a для всех a.

Дистрибутивный закон можно заменить ассоциативным:, стр. 65, и упражнения 75, 76 на страницах 89—90. Кнут утверждает, что неизвестно простого доказательства, что из ассоциативности следует дистрибутивность. Ассоциативность: m(x,w,m(y,w,z)) = m(m(x,w,y),w,z) Операцию медианы можно использовать так же для определения понятия интервалов для распределённых решёток: I(a,b) = {x | m(a, x, b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.Эквивалентность двух выражений в этом равенстве, одного в терминах операции медианы и другого в терминах операций решётки и неравенств, — это теорема 1 в работе Биркгофа и Кисса . Граф конечной дистрибутивной решётки имеет ребро между вершинами a и b, когда I(a,b) = {a,b}. Для любых двух вершин a и b этого графа интервал I(a,b), определённый в терминах теории решёток, состоит из вершин кратчайшего пути из a в b, и это совпадает с интервалами из теории графов, определённых ранее. Для любых трёх элементов решётки a, b и c, m(a,b,c) — это единственное пересечение трёх интервалов I(a,b), I(a,c) и I(b,c)., Теорема 2. Таким образом, граф произвольной конечной распределённой решётки является медианным графом. И наоборот, если медианный граф G содержит две вершины 0 и 1, такие, что любые другие вершины лежат на кратчайшем пути между этими двумя (эквивалентно, m(0,a,1) = a для всех a), то мы можем определить распределённую решётку, в которой a ∧ b = m(a,0,b) и a ∨ b = m(a,1,b), и G будет графом этой решётки., стр. 751.

Дуффус и Райвел описывают графы дистрибутивных решёток как сохраняющие диаметр редукции гиперкубов. Обобщённо — любой медианный граф порождает тернарную операцию m, удовлетворяющую законам идемпотентности, коммутативности и дистрибутивности, но, возможно, без единичного элемента распределённой решётки. Любая тернарная операция на конечном множестве, удовлетворяющая этим трём свойствам (но не обязательно имеющая элементы 0 и 1) порождает медианный граф..

Выпуклые множества и семейства Хэлли Говорят, что в медианном графе множество вершин S является выпуклым, если для любых двух вершин a и b, принадлежащих S, весь интервал I(a,b) является подмножеством S. Эквивалентно, согласно двум определениям интервалов выше, S является выпуклым, если оно содержит любой кратчайший путь между двумя вершинами, или оно содержит медиану любых трёх точек, две из которых лежат в S. Заметим, что пересечение любой пары выпуклых множеств само выпукло. называет такое множество идеальным, но выпуклое множество в графе распределённой решётки — это не то же самое, что .

Выпуклые множества в медианном графе имеют : если F является произвольным семейством попарно пересекающихся выпуклых множеств, то все множества F имеют общую точку., теорема 2.40, стр. 77. Так, пусть F имеет только три выпуклых множества S, T и U. Пусть a — пересечения пары S и T, b — пересечения пары T и U, а c — пересечения пары S и U. Тогда любой кратчайший путь из a в b должен лежать внутри T ввиду выпуклости, и, таким же образом, любой кратчайший путь между любыми двумя парами вершин должен лежать внутри двух других множеств, но m(a,b,c) принадлежит путям между всеми тремя парами вершинами, так что оно лежит внутри всех трёх множеств. Если F содержит более чем три выпуклых множества, результат получаем по индукции по числу множеств, — можно заменить любую пару множеств в F их пересечением, что оставляет полученные множества попарно пересекающимися.

Особенно важным семейством выпуклых множеств в медианном графе, играющем роль, подобную полупространствам в евклидовом пространстве, являются множества Wuv = {w | d(w,u) < d(w,v)}, которые определены для каждого ребра uv графа. Простыми словами, Wuv состоит из вершин, которые ближе к u, чем к v, или, что эквивалентно, из вершин w, для которых кратчайший путь из v в w проходит через u. Чтобы показать, что Wuv выпукло, предположим, что w1w2…wk — произвольный кратчайший путь, начинающийся и кончающийся внутри Wuv. Тогда w2 должен также лежать внутри Wuv, в противном случае две точки m1 = m(u,w1,wk) и m2 = m(m1,w2…wk) будут двумя различными медианами u, w1, и wk, что противоречит определению медианного графа, в котором медиана единственна по определению. Таким образом, каждая вершина на кратчайшем пути между двумя вершинами Wuv также лежит в Wuv, так что Wuv содержит все кратчайшие пути между вершинами, что является одним из определений выпуклости.

Свойство Хэлли для множеств Wuv играет ключевую роль в описании медианных графов как задачи 2-выполнимости.

2-выполнимость Медианные графы имеют тесную связь с множествами решений задач , которые можно использовать для описания этих графов и с помощью которых можно показать связь с отображением гиперкубов, сохраняющих смежность., утверждение 2.5, стр.8; ; ; , теорема S, стр. 72.

Экземпляр 2-выполнимости состоит из набора булевских переменных и коллекции утверждений, на некоторых парах переменных, чтобы избежать некоторых комбинаций значений. Обычно такие задачи выражаются в конъюнктивной нормальной форме, в которой каждое утверждение выражается дизъюнкцией, а всё множество ограничений выражается конъюнкцией утверждений, например,

Решением такого экземпляра является назначение переменным, чтобы удовлетворить все утверждения, или, что эквивалентно, что утверждения конъюнктивной нормальной формы дают значения «истина» при подстановке значений. Семейство всех решений имеет естественную структуру медианной алгебры, где медиана трёх решений образуется выбором мажоритарного значения трёх значений. Легко проверить напрямую, что это медианное значение не может нарушать утверждения. Таким образом, эти решения образуют медианный граф, в котором соседи каждого решения образуются путём отрицания множества переменных, для всех из которых все значения внутри множеств либо равны, либо не равны.

И наоборот, любой медианный граф G можно представить в виде множества решений экземпляра задачи 2-выполнимости. Чтобы найти такое представление, создадим экземпляр задачи 2-выполнимости, в которой каждая переменная описывает направление одного из рёбер графа (назначение направления ребру приводит к ориентированным графам) и каждое ограничение включает две ориентированные дуги, только если существует вершина v, для которой обе дуги лежат на кратчайшем пути из других вершин в вершину v. Каждая вершина v графа G соответствует решению экземпляра задачи 2-выполнимости, в котором все дуги направлены в v. Каждое решение экземпляра должно получаться из некоторой вершины v этим способом, где v — общее пересечение множеств Wuw для дуг, направленных из w к u. Это общее пересечение существует ввиду свойства Хэлли множеств Wuw. Таким образом, решения экземпляра этой задачи 2-выполнимости соответствуют один к одному вершинам графа G.

Редукция гиперкубов

Редукция графа G — это отображение графа G в один из его подграфов с сохранением смежности.. Точнее, это гомоморфизм φ из G в себя, в котором φ(v) = v для каждой вершины v в подграфе φ(G). Образ редукции называется редукцией графа G.