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

Медиана трех вершин в медианном графе

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

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

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

Примеры

Медиана трех вершин в дереве, показывающая поддерево, образованное объединением кратчайших путей между вершинами.

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

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

А квадратный граф.

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

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

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

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

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

я(а,б) = {v | d(а,б) = г (а, в) + d (v, b)}.

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

Для всех а, б, и c, |я(а,б) ∩ я(а,c) ∩ я(б,c)| = 1.

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

• d(а,б) = d(а,м(а,б,c)) + d(м(а,б,c),б)
• d(а,c) = d(а,м(а,б,c)) + d(м(а,б,c),c)
• d(б,c) = d(б,м(а,б,c)) + d(м(а,б,c),c)

и м(а,б,c) - единственная вершина, для которой это верно.

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

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

График дистрибутивной решетки, изображенный в виде Диаграмма Хассе.

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

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

м(а,б,c) = (а ∧ б) ∨ (а ∧ c) ∨ (б ∧ c) = (а ∨ б) ∧ (а ∨ c) ∧ (б ∨ c),

удовлетворяет некоторым ключевым аксиомам, которые разделяет с обычными медиана чисел в диапазоне от 0 до 1 и с медианные алгебры в более общем смысле:

• Идемпотентность: м (а, а, б) = а для всех а и б.
• Коммутативность: м(а,б,c) = м (а, в, б) = м (б, а, в) = м (б, в, а) = м (в, а, б) = м (в, б, а) для всех а, б, и c.
• Распределительность: м (а, м (б, в, г), д) = м (м (а, б, д), в, м (а, г, д)) для всех а, б, c, d, и е.
• Элементы идентичности: м(0,а,1) = а для всех а.

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

• Ассоциативность: м(Икс,ш,м(у,ш,z)) = м(м(Икс,ш,у),ш,z)

Операция median также может использоваться для определения понятия интервалов для распределительных решеток:

я(а,б) = {Икс | м (а, х, б) = Икс} = {Икс | а ∧ б ≤ Икс ≤ а ∨ б}.^[11]

Граф конечной дистрибутивной решетки имеет ребро между вершинами а и б всякий раз, когда я(а,б) = {а,б}. Для каждых двух вершин а и б этого графика интервал я(а,б), определенная в терминах теории решеток выше, состоит из вершин на кратчайших путях из а к б, и, таким образом, совпадает с теоретико-графовыми интервалами, определенными ранее. На каждые три элемента решетки а, б, и c, м(а,б,c) - единственное пересечение трех интервалов я(а,б), я(а,c), и я(б,c).^[12] Следовательно, граф произвольной конечной дистрибутивной решетки является медианным графом. И наоборот, если медианный граф г содержит две вершины 0 и 1 такие, что каждая другая вершина лежит на кратчайшем пути между ними (эквивалентно, м(0,а,1) = а для всех а), то мы можем определить дистрибутивную решетку, в которой а ∧ б = м(а,0,б) и а ∨ б = м(а,1,б), и г будет графиком этой решетки.^[13]

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

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

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

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

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

W_УФ = {ш | d(ш,ты) < d(ш,v)}

определяется для каждого края УФ графа. Прописью, W_УФ состоит из вершин ближе к ты чем v, или, что то же самое, вершины ш такой, что кратчайший путь из v к ш проходит через ты. Чтобы показать это W_УФ выпукло, пусть ш₁ш₂...ш_k произвольный кратчайший путь, который начинается и заканчивается в W_УФ; тогда ш₂ также должен находиться внутри W_УФ, иначе две точки м₁ = м(ты,ш₁,ш_k) и м₂ = м(м₁,ш₂...ш_k) можно было бы показать (рассматривая возможные расстояния между вершинами) как различные медианы ты, ш₁, и ш_k, что противоречит определению медианного графа, которое требует, чтобы медианы были уникальными. Таким образом, каждая последующая вершина на кратчайшем пути между двумя вершинами W_УФ также находится внутри W_УФ, так W_УФ содержит все кратчайшие пути между его узлами, одно из определений выпуклости.

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

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

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

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

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

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

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

Втягивания гиперкубов

Ретракция куба на шестивершинный подграф.

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

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

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

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

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

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

Преобразование графа без треугольников в медианный граф.

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

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

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

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

График Бунемана для пяти типов мышей.

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

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

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

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

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

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

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

• В Декартово произведение из каждых двух медианных графов есть еще один медианный граф. Медианы в графе продукта могут быть вычислены путем независимого нахождения медиан в двух факторах, так же как медианы в графах сетки могут быть вычислены путем независимого нахождения медианы в каждом линейном измерении.
• В Windex графика измеряет количество смотреть вперед необходимо для оптимального решения задачи, в которой задана последовательность вершин графа s_я, и должен найти в качестве вывода другую последовательность вершин т_я минимизация суммы расстояний d(s_я, т_я) и d(т_я − 1, т_я). Медианные графы - это именно те графы, которые имеют Windex 2. В медианном графе оптимальный выбор - установить т_я = м(т_я − 1, s_я, s_я + 1).^[1]
• Свойство наличия уникальной медианы также называют уникальное свойство точки Штайнера.^[1] Оптимальный Дерево Штейнера для трех вершин а, б, и c в медианном графе может быть найден как объединение трех кратчайших путей из а, б, и c к м(а,б,c). Бандельт и Бартелеми (1984) изучить в более общем плане проблему поиска вершины минимизация суммы расстояний для каждой из заданного набора вершин и покажите, что у него есть уникальное решение для любого нечетного числа вершин в медианном графе. Они также показывают, что эта медиана набора S вершин в медианном графе удовлетворяет Критерий Кондорсе для победителя выборы: по сравнению с любой другой вершиной, она ближе к большинству вершин в S.
• Как и в случае с частичными кубами в более общем смысле, каждый медианный граф с п вершин не более (п/ 2) журнал₂ п края. Однако количество ребер не может быть слишком маленьким: Клавжар, Малдер и Шкрековски (1998) докажите, что в каждом медианном графе выполняется неравенство 2п − м − k ≤ 2 держит, где м количество ребер и k - размерность гиперкуба, ретрактом которого является граф. Это неравенство является равенством тогда и только тогда, когда медианный граф не содержит кубов. Это следствие другого тождества медианных графов: Эйлерова характеристика Σ (-1)^{тусклый (Q)} всегда равен единице, где сумма берется по всем подграфам гиперкуба Q данного медианного графа.^[26]
• Единственный регулярный Медианные графы - это гиперкубы.^[27]
• Каждый медианный граф представляет собой модульный граф. Модульные графы - это класс графов, в которых каждая тройка вершин имеет медиану, но не обязательно, чтобы медианы были уникальными.^[28]

Примечания

использованная литература

внешняя ссылка

• Медианные графики, Информационная система для включений классов графов.
• Сеть, Бесплатное программное обеспечение для филогенетических сетей. Сеть генерирует эволюционные деревья и сети на основе генетических, лингвистических и других данных.
• Филомурка, программное обеспечение с открытым исходным кодом для вычисления медианных сетей на основе биологических данных.