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

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

Концепция медианных графов давно изучалась, например, Биркгоффом и Кисом (1947) или (более явно) Аванном (1961), но первая статья, в которой они были названы «медианными графами», была, по-видимому, Nebeský (1971). Как пишут Чанг , Грэхем и Сакс, «медианные графы возникают естественным образом при изучении упорядоченных множеств и дискретных дистрибутивных решеток и имеют обширную литературу». ^[1] В филогенетике граф Бунемана, представляющий все эволюционные деревья максимальной экономии, является медианным графом. ^[2] Медианные графы также возникают в теории общественного выбора : если набор альтернатив имеет структуру медианного графа, можно вывести недвусмысленным образом большинство предпочтений среди них. ^[3]

Дополнительные обзоры медианных графиков приведены Клавжаром и Малдером (1999), Бандельтом и Чепои (2008) и Кнутом (2008).

Примеры

Каждое дерево является медианным графом. Чтобы увидеть это, заметьте, что в дереве объединение трех кратчайших путей между парами трех вершин a , b , и c является либо само путем, либо поддеревом, образованным тремя путями, встречающимися в одном центральном узле со степенью три. Если объединение трех путей само является путем, медиана m ( a , b , c ) равна одной из вершин a , b , или c , в зависимости от того, какая из этих трех вершин находится между двумя другими в пути. Если поддерево, образованное объединением трех путей, не является путем, медиана трех вершин является центральным узлом степени три поддерева. ^[4]

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

Квадратные графы , планарные графы, в которых все внутренние грани являются четырехугольниками, а все внутренние вершины имеют четыре или более инцидентных ребер, являются еще одним подклассом медианных графов. [ ^6] Полимино является частным случаем квадратного графа и, следовательно, также образует медианный граф. ^[7]

Симплексный граф κ( G ) произвольного неориентированного графа G имеет вершину для каждой клики (полного подграфа) G ; две вершины κ( G ) связаны ребром, если соответствующие клики отличаются на одну вершину G . Симплексный граф всегда является медианным графом, в котором медиана заданной тройки клик может быть сформирована с использованием правила большинства для определения того, какие вершины клик следует включить. ^[8]

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

Эквивалентные определения

В произвольном графе для каждых двух вершин a и b минимальное число ребер между ними называется их расстоянием и обозначается d ( x , y ). Интервал вершин, которые лежат на кратчайших путях между a и b, определяется как

Я (а, б) = {v | d (а, б) = d (а, в) + d (v, б)}.

Медианный граф определяется тем свойством, что для каждых трех вершин a , b и c эти интервалы пересекаются в одной точке:

Для всех a , b и c ,

| I (a, b)\capI (a, c) \capI (b, c) | = 1.

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

д ( а , б ) = д ( а , м ( а , б , в )) + д ( м ( а , б , в ), б )
д ( а , в ) = д ( а , м ( а , б , в )) + д ( м ( а , б , в ), в )
д ( б , в ) = д ( б , м ( а , б , в )) + д ( м ( а , б , в ), в )

и m ( a , b , c ) — единственная вершина, для которой это верно.

Также возможно определить медианные графы как множества решений задач 2-выполнимости , как ретракции гиперкубов , как графы конечных медианных алгебр , как графы Бунемана систем разделения Хелли и как графы windex 2; см. разделы ниже.

Дистрибутивные решетки и медианные алгебры

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

В дистрибутивной решетке самодвойственная тернарная медианная операция Биркгофа ^[9]

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 .
Коммутативность : для всех a , b и c . $m(a,b,c)=m(a,c,b)=m(b,a,c)=m(b,c,a)=m(c,a,b)=m(c,b,a)$
Распределимость : ⁠ ⁠ $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 .

Распределительный закон может быть заменен ассоциативным законом: ^[10]

Ассоциативность : 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 \land b \leq x \leq a \lor b}.

^[11]

Граф конечной дистрибутивной решетки имеет ребро между вершинами 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)$ . ^[12] Следовательно, граф произвольной конечной дистрибутивной решетки является медианным графом. Наоборот, если медианный граф G содержит две вершины 0 и 1, такие, что каждая другая вершина лежит на кратчайшем пути между ними (эквивалентно, m (0, a ,1) = a для всех a ), то мы можем определить дистрибутивную решетку, в которой a ∧ b = m ( a ,0, b ) и a ∨ b = m ( a ,1, b ), и G будет графом этой решетки. ^[13]

Duffus & Rival (1983) характеризуют графы дистрибутивных решеток непосредственно как сохраняющие диаметр ретракты гиперкубов. В более общем смысле, каждый медианный граф порождает тернарную операцию m, удовлетворяющую идемпотентности, коммутативности и дистрибутивности, но, возможно, без элементов тождества дистрибутивной решетки. Каждая тернарная операция на конечном множестве, удовлетворяющем этим трем свойствам (но не обязательно имеющем 0 и 1 элементов), порождает таким же образом медианный граф. ^[14]

Выпуклые множества и семейства Хелли

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

Выпуклые множества в медианном графе обладают свойством Хелли : если F — произвольное семейство попарно пересекающихся выпуклых множеств, то все множества в F имеют общее пересечение. ^[16] Ибо, если F имеет только три выпуклых множества S , T и U , причем a находится на пересечении пары S и T , b — на пересечении пары T и U , а c — на пересечении пары S и U , то каждый кратчайший путь от a до b должен лежать внутри T по выпуклости, и аналогично каждый кратчайший путь между двумя другими парами вершин должен лежать внутри двух других множеств; но m ( a , b , c ) принадлежит путям между всеми тремя парами вершин, поэтому он лежит внутри всех трех множеств и образует часть их общего пересечения. Если F содержит более трех выпуклых множеств, результат следует индукции по числу множеств, поскольку можно заменить произвольную пару множеств в F их пересечением, используя результат для троек множеств, чтобы показать, что замененное семейство по-прежнему попарно пересекается.

Особенно важным семейством выпуклых множеств в медианном графе, играющим роль, аналогичную роли полупространств в евклидовом пространстве, являются множества

W _uv = { w | d ( w , u ) < d ( w , v )}

определенное для каждого ребра uv графа. На словах W _uv состоит из вершин, которые ближе к u, чем к v , или, что эквивалентно, вершин w таких, что некоторый кратчайший путь от v до w проходит через u . Чтобы показать, что W _uv является выпуклым, пусть w ₁w ₂ ... w _k будет произвольным кратчайшим путем, который начинается и заканчивается внутри W _uv ; тогда w ₂ также должен лежать внутри W _uv , иначе можно было бы показать (рассмотрев возможные расстояния между вершинами), что две точки m ₁ = m ( u , w ₁ , w _k ) и m ₂ = m ( m ₁ , w ₂ ... w _k ) являются различными медианами u , w ₁ и w _k , что противоречит определению медианного графа, которое требует, чтобы медианы были уникальными. Таким образом, каждая последующая вершина на кратчайшем пути между двумя вершинами W _uv также лежит внутри W _uv , поэтому W _uv содержит все кратчайшие пути между своими узлами, что является одним из определений выпуклости.

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

2-выполнимость

Медианные графы тесно связаны с наборами решений задач 2-выполнимости , которые можно использовать как для характеристики этих графов, так и для их соотнесения с сохраняющими смежность картами гиперкубов. ^[17]

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

(x_{11}\lor x_{12})\land (x_{21}\lor x_{22})\land \cdots \land (x_{n1}\lor x_{n2})\land \cdots .

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

Наоборот, каждый медианный граф G может быть представлен таким образом как набор решений для экземпляра 2-выполнимости. Чтобы найти такое представление, создайте экземпляр 2-выполнимости, в котором каждая переменная описывает ориентацию одного из ребер в графе (назначение направления ребру, заставляющее граф стать направленным, а не ненаправленным), и каждое ограничение позволяет двум ребрам совместно использовать пару ориентаций только тогда, когда существует вершина v такая, что обе ориентации лежат вдоль кратчайших путей от других вершин к v . Каждая вершина v графа G соответствует решению для этого экземпляра 2-выполнимости, в котором все ребра направлены к v . Каждое решение для экземпляра должно исходить из некоторой вершины v таким образом, где v является общим пересечением множеств W _uw для ребер, направленных от w к u ; это общее пересечение существует из-за свойства Хелли множеств W _uw . Следовательно , решения этого примера 2-выполнимости соответствуют один к одному вершинам G.

Ретракты гиперкубов

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

Если G — медианный граф, а a , b и c — произвольные три вершины ретракции φ( G ), то φ( m ( a , b , c )) должна быть медианой a , b и c , и поэтому должна быть равна m ( a , b , c ). Следовательно, φ( G ) содержит медианы всех троек своих вершин и также должна быть медианным графом. Другими словами, семейство медианных графов замкнуто относительно операции ретракции. ^[19]

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

Наоборот, каждый медианный граф должен быть ретрактом гиперкуба. ^[20] Это можно увидеть из связи, описанной выше, между медианными графами и 2-выполнимостью: пусть G будет графом решений для экземпляра 2-выполнимости; без потери общности этот экземпляр можно сформулировать таким образом, что никакие две переменные не будут всегда равны или всегда не равны в каждом решении. Тогда пространство всех истинностных назначений переменным этого экземпляра образует гиперкуб. Для каждого предложения, образованного как дизъюнкция двух переменных или их дополнений, в экземпляре 2-выполнимости можно образовать ретракт гиперкуба, в котором истинностные назначения, нарушающие это предложение, отображаются в истинностные назначения, в которых обе переменные удовлетворяют предложению, не изменяя другие переменные в истинностном назначении. Состав ретракций, сформированных таким образом для каждого из предложений, дает ретракцию гиперкуба на пространство решений экземпляра и, следовательно, дает представление G как ретракции гиперкуба. В частности, медианные графы являются изометрическими подграфами гиперкубов и, следовательно, являются частичными кубами . Однако не все частичные кубы являются медианными графами; например, граф цикла с шестью вершинами является частичным кубом, но не является медианным графом.

Как описывают Имрих и Клавжар (2000), изометрическое вложение медианного графа в гиперкуб может быть построено за время O( m log n ), где n и m — количество вершин и ребер графа соответственно. ^[21]

Графы без треугольников и алгоритмы распознавания

Проблемы проверки того, является ли граф медианным графом, и того, является ли граф свободным от треугольников , были хорошо изучены, когда Имрих, Клавжар и Малдер (1999) заметили, что в некотором смысле они вычислительно эквивалентны. ^[22] Поэтому наиболее известное ограничение по времени для проверки того, является ли граф свободным от треугольников, O( m ^1.41 ), ^[23] применимо также к проверке того, является ли граф медианным графом, и любое улучшение алгоритмов проверки медианного графа также приведет к улучшению алгоритмов обнаружения треугольников в графах.

В одном направлении предположим, что в качестве входных данных задан граф G , и необходимо проверить, является ли G свободным от треугольников. Из G постройте новый граф H, имеющий в качестве вершин каждое множество из нуля, одной или двух смежных вершин G . Два таких множества смежны в H , когда они отличаются ровно на одну вершину. Эквивалентное описание H состоит в том, что он образован путем разбиения каждого ребра G на путь из двух ребер и добавления новой вершины, соединенной со всеми исходными вершинами G . Этот граф H по построению является частичным кубом, но он является медианным графом только тогда, когда G свободен от треугольников: если a , b , и c образуют треугольник в G , то { a , b }, { a , c } и { b , c } не имеют медианы в H , поскольку такая медиана должна была бы соответствовать множеству { a , b , c }, но множества из трех или более вершин G не образуют вершин в H . Следовательно, G не содержит треугольников тогда и только тогда, когда H является медианным графом. В случае, если G не содержит треугольников, H является его симплексным графом . Алгоритм для эффективной проверки того, является ли H медианным графом, может быть использован с помощью этой конструкции для проверки того, является ли G не содержащим треугольников. Это преобразование сохраняет вычислительную сложность задачи, поскольку размер H пропорционален размеру G.

Сокращение в другом направлении, от обнаружения треугольников до тестирования медианного графа, более сложное и зависит от предыдущего алгоритма распознавания медианного графа Хагауэра, Имриха и Клавжара (1999), который проверяет несколько необходимых условий для медианных графов за почти линейное время. Ключевой новый шаг включает использование поиска в ширину для разбиения вершин графа на уровни в соответствии с их расстояниями от некоторой произвольно выбранной корневой вершины, формирование графа из каждого уровня, в котором две вершины являются смежными, если они имеют общего соседа на предыдущем уровне, и поиск треугольников в этих графах. Медиана любого такого треугольника должна быть общим соседом трех вершин треугольника; если этот общий сосед не существует, граф не является медианным графом. Если все треугольники, найденные таким образом, имеют медианы, и предыдущий алгоритм обнаруживает, что граф удовлетворяет всем остальным условиям для того, чтобы быть медианным графом, то он действительно должен быть медианным графом. Этот алгоритм требует не только возможности проверить, существует ли треугольник, но и списка всех треугольников в графе уровня. В произвольных графах перечисление всех треугольников иногда требует Ω( m ^3/2 ) времени, поскольку некоторые графы имеют именно столько треугольников, однако Хагауэр и др. показывают, что количество треугольников, возникающих в графах уровня их сокращения, близко к линейному, что позволяет использовать метод быстрого умножения матриц Алона и др. для поиска треугольников.

Эволюционные деревья, графы Бунемана и системы разделения Хелли

Филогения — это вывод эволюционных деревьев из наблюдаемых характеристик видов ; такое дерево должно размещать виды в различных вершинах и может иметь дополнительные скрытые вершины , но скрытые вершины должны иметь три или более инцидентных ребер и также должны быть помечены характеристиками. Характеристика является бинарной , когда она имеет только два возможных значения, а набор видов и их характеристик демонстрирует идеальную филогению, когда существует эволюционное дерево, в котором вершины (виды и скрытые вершины), помеченные любым конкретным значением характеристики, образуют смежное поддерево. Если дерево с идеальной филогенией невозможно, часто желательно найти такое, которое демонстрирует максимальную экономность или, что эквивалентно, минимизирует количество раз, когда конечные точки ребра дерева имеют различные значения для одной из характеристик, суммированных по всем ребрам и всем характеристикам.

Бунеман (1971) описал метод вывода идеальных филогений для бинарных характеристик, когда они существуют. Его метод естественным образом обобщается на построение медианного графа для любого набора видов и бинарных характеристик, который был назван медианной сетью или графом Бунемана ^[24] и является типом филогенетической сети . Каждое максимально экономное эволюционное дерево встраивается в граф Бунемана в том смысле, что ребра дерева следуют путям в графе, а число изменений значений характеристик на ребре дерева совпадает с числом в соответствующем пути. Граф Бунемана будет деревом тогда и только тогда, когда существует идеальная филогения; это происходит, когда нет двух несовместимых характеристик, для которых наблюдаются все четыре комбинации значений характеристик.

Чтобы сформировать граф Бунемана для набора видов и характеристик, сначала исключите избыточные виды, которые неотличимы от некоторых других видов, и избыточные характеристики, которые всегда совпадают с некоторыми другими характеристиками. Затем сформируйте скрытую вершину для каждой комбинации значений характеристик таким образом, чтобы каждые два значения существовали в некоторых известных видах. В показанном примере есть маленькие коричневые бесхвостые мыши, маленькие серебристые бесхвостые мыши, маленькие коричневые хвостатые мыши, большие коричневые хвостатые мыши и большие серебристохвостые мыши; метод графа Бунемана сформирует скрытую вершину, соответствующую неизвестному виду маленьких серебристохвостых мышей, потому что каждая попарная комбинация (маленькие и серебристые, маленькие и хвостатые и серебристохвостые) наблюдается в некоторых других известных видах. Однако метод не выведет существование больших коричневых бесхвостых мышей, потому что нет мышей, которые имели бы как большие, так и бесхвостые признаки. После определения скрытых вершин сформируйте ребро между каждой парой видов или скрытыми вершинами, которые отличаются одной характеристикой.

Можно эквивалентно описать набор бинарных характеристик как систему разделения , семейство множеств, обладающее свойством, что дополнительный набор каждого множества в семействе также находится в семействе. Эта система разделения имеет набор для каждого значения характеристики, состоящий из видов, которые имеют это значение. Когда включены скрытые вершины, результирующая система разделения имеет свойство Хелли : каждое попарно пересекающееся подсемейство имеет общее пересечение. В некотором смысле медианные графы характеризуются как происходящие из систем разделения Хелли: пары ( W _uv , W _vu ), определенные для каждого ребра uv медианного графа, образуют систему разделения Хелли, поэтому, если применить конструкцию графа Бунемана к этой системе, скрытые вершины не понадобятся, и результат будет таким же, как у исходного графа. ^[25]

Бандельт и др. (1995) и Бандельт, Маколей и Ричардс (2000) описывают методы упрощенного ручного расчета графика Бунемана и используют эту конструкцию для визуализации генетических связей человека.

Дополнительные свойства

Декартово произведение графов образует медианный граф из двух меньших медианных графов.

Декартово произведение каждых двух медианных графов — это еще один медианный граф. Медианы в графе произведения могут быть вычислены путем независимого нахождения медиан в двух факторах, так же как медианы в решетчатых графах могут быть вычислены путем независимого нахождения медианы в каждом линейном измерении.
Windex графа измеряет количество предпросмотра, необходимого для оптимального решения задачи, в которой задана последовательность вершин графа s _i , и необходимо найти в качестве вывода другую последовательность вершин t _{i ,} минимизирующую сумму расстояний $d$ $($ $s$ $i$ $, t$ $i$ $)$ и $d$ $($ $t$ $i$ $- 1$ $,$ $t$ $i$ $)$ . Медианные графы — это именно те графы, которые имеют windex 2. В медианном графе оптимальным выбором является установка $t$ $i$ $=$ $m$ $($ $t$ $i$ $- 1$ $,$ $s$ $i$ $,$ $s$ $i$ $+ 1$ $)$ . ^[1]
Свойство иметь уникальную медиану также называется свойством уникальной точки Штейнера . ^[1] Оптимальное дерево Штейнера для трех вершин a , b и c в медианном графе может быть найдено как объединение трех кратчайших путей из a , b и c в m ( a , b , c ). Бандельт и Бартелеми (1984) изучают в более общем плане задачу нахождения вершины, минимизирующей сумму расстояний до каждой из заданного набора вершин, и показывают, что она имеет единственное решение для любого нечетного числа вершин в медианном графе. Они также показывают, что эта медиана набора S вершин в медианном графе удовлетворяет критерию Кондорсе для победителя выборов : по сравнению с любой другой вершиной она ближе к большинству вершин в S.
Как и в случае с частичными кубами в более общем смысле, каждый медианный граф с n вершинами имеет не более ( n /2) log2 $n$ _ребер . Однако число ребер не может быть слишком малым: Клавжар, Малдер и Шкрековски (1998) доказывают, что в каждом медианном графе выполняется неравенство $2n - m - k \leq 2$ , где m — число ребер, а k — размерность гиперкуба, ретрактом которого является граф. Это неравенство является равенством тогда и только тогда, когда медианный граф не содержит кубов. Это следствие другого тождества для медианных графов: эйлерова характеристика Σ (−1) ^{dim( Q )} всегда равна единице, где сумма берется по всем подграфам гиперкуба Q данного медианного графа. ^[26]
Единственными правильными медианными графами являются гиперкубы. ^[27]
Каждый медианный граф является модулярным графом . Модульные графы — это класс графов, в которых каждая тройка вершин имеет медиану, но медианы не обязаны быть уникальными. ^[28]

Примечания

^ abc Чанг, Грэм и Сакс (1987).
^ Бунеман (1971); Дресс и др. (1997); Дресс, Хубер и Молтон (1997).
^ Бандельт и Бартелеми (1984); Дэй и МакМоррис (2003).
^ Имрих и Клавжар (2000), Предложение 1.26, с. 24.
^ Это непосредственно следует из характеристики медианных графов как ретракций гиперкубов, описанной ниже.
^ Солтан, Замбицкий и Присэкару (1973); Чепой, Драган и Ваксес (2002); Чепой, Фанчуллини и Ваксес (2004).
^ Клавжар и Шкрековски (2000).
^ Бартелеми, Леклерк и Монжарде (1986), стр. 200.
^ Биркгофф и Кисс (1947) приписывают определение этой операции Биркгоффу, Г. (1940), Теория решеток , Американское математическое общество, стр. 74.
^ Кнут (2008), стр. 65 и упражнения 75 и 76 на стр. 89–90. Кнут утверждает, что простое доказательство того, что ассоциативность подразумевает дистрибутивность, остается неизвестным.
^ Эквивалентность между двумя выражениями в этом уравнении, одним в терминах операции медианы, а другим в терминах решеточных операций и неравенств, является теоремой 1 Биркгофа и Кисса (1947).
^ Биркгоф и Кисс (1947), Теорема 2.
↑ Биркгоф и Кисс (1947), стр. 751.
^ Аванн (1961).
^ Кнут (2008) называет такое множество идеалом , но выпуклое множество в графике дистрибутивной решетки — это не то же самое, что идеал решетки .
^ Имрих и Клавжар (2000), Теорема 2.40, с. 77.
^ Бандельт и Чепои (2008), Предложение 2.5, стр. 8; Чунг, Грэм и Сакс (1989); Федер (1995); Кнут (2008), Теорема S, стр. 72.
↑ Ад (1976).
^ Имрих и Клавжар (2000), Предложение 1.33, с. 27.
^ Бандельт (1984); Имрих и Клавжар (2000), теорема 2.39, стр.76; Кнут (2008), с. 74.
^ Техника, которая достигает кульминации в Лемме 7.10 на стр. 218 Имриха и Клавжара, состоит в применении алгоритма Чибы и Нишизеки (1985) для перечисления всех 4-циклов в графе G , формирования неориентированного графа, имеющего в качестве вершин ребра G и имеющего в качестве ребер противоположные стороны 4-цикла, и использования связных компонентов этого производного графа для формирования координат гиперкуба. Эквивалентный алгоритм — Кнут (2008), Алгоритм H, стр. 69.
^ Для предыдущих алгоритмов распознавания медианного графа см. Jha & Slutzki (1992), Imrich & Klavžar (1998) и Hagauer, Imrich & Klavžar (1999). Для алгоритмов обнаружения треугольников см. Itai & Rodeh (1978), Chiba & Nishizeki (1985) и Alon, Yuster & Zwick (1995).
^ Alon, Yuster & Zwick (1995), основанный на быстром умножении матриц . Здесь m — число ребер в графе, а большая нотация O скрывает большой постоянный множитель; лучшие практические алгоритмы для обнаружения треугольников требуют времени O( m ^3/2 ). Для распознавания медианного графа временная граница может быть выражена либо через m , либо через n (число вершин), как m = O( n log n ).
^ Mulder & Schrijver (1979) описали версию этого метода для систем характеристик, не требующих никаких скрытых вершин, а Barthélémy (1989) дает полную конструкцию. Название графа Бунемана дано в Dress et al. (1997) и Dress, Huber & Moulton (1997).
^ Малдер и Шрайвер (1979).
^ Шкрековски (2001).
^ Малдер (1980).
^ Модульные графы, Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.

Ссылки

Алон, Нога ; Юстер, Рафаэль; Цвик, Ури (1995), «Цветовое кодирование», Журнал ACM , 42 (4): 844–856, doi : 10.1145/210332.210337 , MR 1411787, S2CID 208936467.
Аванн, СП (1961), «Метрические тернарные дистрибутивные полурешетки», Труды Американского математического общества , 12 (3): 407–414, doi : 10.2307/2034206 , JSTOR 2034206, MR 0125807.
Бандельт, Ханс-Юрген (1984), «Ретракты гиперкубов», Журнал теории графов , 8 (4): 501–510, doi : 10.1002/jgt.3190080407, MR 0766499.
Бандельт, Ханс-Юрген; Бартелеми, Жан-Пьер (1984), «Медианы в медианных графах», Discrete Applied Mathematics , 8 (2): 131–142, doi :10.1016/0166-218X(84)90096-9, MR 0743019.
Бандельт, Ханс-Юрген; Чепои, Виктор (2008), «Метрическая теория графов и геометрия: обзор» (PDF) , Обзоры по дискретной и вычислительной геометрии , Contemporary Mathematics, т. 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 49–86, doi : 10.1090/conm/453/08795, ISBN 9780821842393, г-н 2405677.
Бандельт, Ханс-Юрген; Форстер, П.; Сайкс, Б. К.; Ричардс, Мартин Б. (1 октября 1995 г.), «Митохондриальные портреты человеческих популяций с использованием медианных сетей», Genetics , 141 (2): 743–753, doi :10.1093/genetics/141.2.743, PMC 1206770 , PMID 8647407.
Бандельт, Ханс-Юрген; Форстер, П.; Роль, Арне (1 января 1999 г.), «Сети с медианным соединением для вывода внутривидовых филогений», Молекулярная биология и эволюция , 16 (1): 37–48, doi : 10.1093/oxfordjournals.molbev.a026036 , PMID 10331250, архивировано из оригинала 27 декабря 2005 г..
Бандельт, Ханс-Юрген; Маколей, Винсент; Ричардс, Мартин Б. (2000), «Медианные сети: быстрое построение и жадная редукция, одна симуляция и два тематических исследования на основе человеческой мтДНК», Молекулярная филогенетика и эволюция , 16 (1): 8–28, CiteSeerX 10.1.1.128.3232 , doi :10.1006/mpev.2000.0792, PMID 10877936.
Бартелеми, Жан-Пьер (1989), «От гиперграфов копаэра к медианным графам со скрытыми вершинами», Дискретная математика , 76 (1): 9–28, doi : 10.1016/0012-365X(89)90283-5 , MR 1002234.
Бартелеми, Ж.-П.; Леклерк, Б.; Монжарде, Б. (1986), «Об использовании упорядоченных множеств в задачах сравнения и консенсуса классификаций», Журнал классификации , 3 (2): 187–224, doi :10.1007/BF01894188, S2CID 6092438.
Биркгоф, Гарретт ; Кисс, С.А. (1947), «Тернарная операция в дистрибутивных решетках», Бюллетень Американского математического общества , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR 0021540.
Бунеман, П. (1971), «Восстановление деревьев по мерам несходства», в Hodson, FR; Kendall, DG; Tautu, PT (ред.), Математика в археологических и исторических науках , Издательство Эдинбургского университета, стр. 387–395.
Chepoi, V.; Dragan, F.; Vaxès, Y. (2002), «Проблемы центра и диаметра в плоских четырех- и триангуляциях», Труды 13-го симпозиума ACM-SIAM по дискретным алгоритмам, Soda '02, стр. 346–355, ISBN 9780898715132.
Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004), «Проблема медианы в некоторых плоских триангуляциях и квадрангулях», Computational Geometry: Theory & Applications , 27 (3): 193–210, doi : 10.1016/j.comgeo.2003.11.002.
Чиба, Н.; Нишизеки, Т. (1985), «Алгоритмы древовидности и перечисления подграфов», SIAM Journal on Computing , 14 : 210–223, doi : 10.1137/0214017, MR 0774940.
Chung, FRK ; Graham, RL ; Saks, ME (1987), «Динамический поиск в графах», в Wilf, H. (ред.), Discrete Algorithms and Complexity (Киото, 1986) (PDF) , Perspectives in Computing, т. 15, Нью-Йорк: Academic Press, стр. 351–387, MR 0910939.
Чанг, ФРК ; Грэм, РЛ ; Сакс, МЭ (1989), «Динамическая задача размещения графов» (PDF) , Combinatorica , 9 (2): 111–132, doi :10.1007/BF02124674, S2CID 5419897.
Дей, Уильям Х. Э.; Макморрис, Ф. Р. (2003), Аксиоматическая теория консенсуса в групповом выборе и биоинформатике , Общество промышленной и прикладной математики, стр. 91–94, ISBN 978-0-89871-551-4.
Дресс, А.; Хенди, М.; Хубер, К.; Молтон, В. (1997), «О числе вершин и ребер графа Бунемана», Annals of Combinatorics , 1 (1): 329–337, doi :10.1007/BF02558484, MR 1630739, S2CID 120716928.
Дресс, А.; Хубер, К.; Молтон, В. (1997), «Некоторые вариации на тему Бунемана», Annals of Combinatorics , 1 (1): 339–352, doi :10.1007/BF02558485, MR 1630743, S2CID 122966547.
Даффус, Дуайт ; Ривал, Иван (1983), «Графы, ориентируемые как дистрибутивные решетки», Труды Американского математического общества , 88 (2): 197–200, doi : 10.2307/2044697 , JSTOR 2044697.
Федер, Т. (1995), Стабильные сети и графы произведений , Мемуары Американского математического общества, т. 555.
Хагауэр, Иоганн; Имрих, Вильфрид; Клавжар, Санди (1999), «Распознавание медианных графов за субквадратичное время», Теоретическая информатика , 215 (1–2): 123–136, doi :10.1016/S0304-3975(97)00136-9, MR 1678773.
Черт, Павол (1976), «Отказы от графиков», Colloquio Internazionale sulle Teorie Combinatorie (Рим, 1973), Tomo II , Atti dei Convegni Lincei, vol. 17, Рим: Аккад. Наз. Линчеи, стр. 263–268, MR 0543779..
Имрих, Вильфрид; Клавжар, Санди (1998), «Лемма о выпуклости и процедуры расширения для двудольных графов», Европейский журнал комбинаторики , 19 (6): 677–686, doi : 10.1006/eujc.1998.0229 , MR 1642702.
Имрих, Вильфрид; Клавжар, Санди (2000), Графы продуктов: структура и распознавание , Wiley, ISBN 978-0-471-37039-0, МР 0788124.
Имрих, Вильфрид; Клавжар, Сэнди; Малдер, Генри Мартин (1999), «Медианные графы и графы без треугольников», SIAM Journal on Discrete Mathematics , 12 (1): 111–118, CiteSeerX 10.1.1.28.5906 , doi :10.1137/S0895480197323494, MR 1666073.
Итай, А.; Родех, М. (1978), «Поиск минимальной схемы в графе», SIAM Journal on Computing , 7 (4): 413–423, doi :10.1137/0207033, MR 0508603.
Джа, Пранава К.; Слуцки, Джиора (1992), «Алгоритмы выпуклого расширения для распознавания и изометрического вложения медианных графов», Ars Combinatoria , 34 : 75–92, MR 1206551.
Клавжар, Сэнди; Малдер, Генри Мартин (1999), «Медианные графы: характеристики, теория расположения и связанные структуры», Журнал комбинаторной математики и комбинаторных вычислений , 30 : 103–127, MR 1705337.
Клавжар, Санди; Малдер, Генри Мартин; Шкрековски, Ристе (1998), «Формула типа Эйлера для медианных графов», Дискретная математика , 187 (1): 255–258, doi : 10.1016/S0012-365X(98)00019-3 , MR 1630736.
Клавжар, Санди; Шкрековски, Ристе (2000), «О медианных графах и медианных решетчатых графах», Дискретная математика , 219 (1–3): 287–293, CiteSeerX 10.1.1.704.7507 , doi : 10.1016/S0012-365X(00)00085-6 , MR 1761732.
Кнут, Дональд Э. (2008), «Медианные алгебры и медианные графы», Искусство программирования , т. IV, Выпуск 0: Введение в комбинаторные алгоритмы и булевы функции, Addison-Wesley, стр. 64–74, ISBN 978-0-321-53496-5.
Малдер, Генри Мартин (1980), " $n$ -кубы и медианные графы", Журнал теории графов , 4 (1): 107–110, doi :10.1002/jgt.3190040112, MR 0558458.
Малдер, Генри Мартин; Шрайвер, Александр (1979), «Медианные графы и гиперграфы Хелли», Дискретная математика , 25 (1): 41–50, doi : 10.1016/0012-365X(79)90151-1 , MR 0522746.
Небесский, Ладислав (1971), «Медианные графики», Commentationes Mathematicae Universitatis Carolinae , 12 : 317–325, MR 0286705.
Шкрековски, Ристе (2001), «Два отношения для медианных графов», Дискретная математика , 226 (1): 351–353, doi :10.1016/S0012-365X(00)00120-5, MR 1802603.
Солтан, П.; Замбицкий Д.; Присэкару, К. (1973), Экстремальные задачи на графах и алгоритмы их решения (на русском языке), Кишинев: Штиинца.

Внешние ссылки

Медианные графы, информационная система для включения классов графов.
Network, бесплатное программное обеспечение для филогенетической сети. Network генерирует эволюционные деревья и сети из генетических, лингвистических и других данных.
PhyloMurka — программное обеспечение с открытым исходным кодом для вычислений медианных сетей на основе биологических данных.