Войти
Медиана трех вершин в медианном графе В теории графов, разделе математики, медианный граф - это неориентированный граф, в котором каждые три вершины a, b и c имеют уникальную медиану: вершину m ( a, b, c), которая принадлежит кратчайшим путям между каждой парой. из a, b и c.
Концепция медианных графов уже давно изучается, например, Биркгофом и Киссом (1947) или (более подробно) Аваном (1961), но первая статья, назвавшая их «медианными графами», по-видимому, принадлежит Небески (1971). Как пишут Чанг, Грэм и Сакс, «медианные графы возникают естественным образом при изучении упорядоченных множеств и дискретных распределительных решеток, и по ним имеется обширная литература». В филогенетике граф Бунемана, представляющий все эволюционные деревья максимальной экономии, является медианным графом. Медианные графы также возникают в теории социального выбора : если набор альтернатив имеет структуру медианного графа, можно однозначно вывести предпочтение большинства среди них.
Дополнительные обзоры медианных графиков даны Klavžar amp; Mulder (1999), Bandelt amp; Chepoi (2008) и Knuth (2008).
Медиана трех вершин в дереве, показывающая поддерево, образованное объединением кратчайших путей между вершинами. Каждое дерево - это медианный граф. Чтобы убедиться в этом, заметьте, что в дереве объединение трех кратчайших путей между парами трех вершин a, b и c является либо путем, либо поддеревом, образованным тремя путями, встречающимися в одном центральном узле со степенью три. Если объединение трех путей само по себе является путем, медиана m ( a, b, c) равна одной из a, b или c, в зависимости от того, какая из этих трех вершин находится между двумя другими на пути. Если поддерево, образованное объединением трех путей, не является путем, медиана трех вершин является центральным узлом третьей степени поддерева.
Дополнительные примеры медианных графов представлены сеточными графами. В сеточном графике координаты медианы m ( a, b, c) могут быть найдены как медиана координат a, b и c. Наоборот, оказывается, что в каждом медианном графе можно пометить вершины точками в целочисленной решетке таким образом, чтобы медианы могли быть вычислены таким образом покоординатно.
Рамочный граф. Квадратные графы, плоские графы, в которых все внутренние грани являются четырехугольниками, а все внутренние вершины имеют четыре или более инцидентных ребра, являются еще одним подклассом медианных графов. Полимин является частным случаем рамочного графа и, следовательно, также образует средний график.
Симплекс график κ ( G) произвольного неориентированного графа G имеет вершину для каждого клика (полный подграф) из G ; две вершины х ( G) связаны ребром, если соответствующие клики отличаются одной вершиной из G. Симплексный граф всегда является медианным графом, в котором медиана данной тройки клик может быть сформирована с использованием правила большинства, чтобы определить, какие вершины клик нужно включить.
Нет цикла график длины, кроме четырех может быть средний график. Каждый такой цикл имеет три вершины a, b и c, так что три кратчайших пути охватывают весь цикл без общего пересечения. Для такой тройки вершин не может быть медианы.
В произвольном графе для каждых двух вершин a и b минимальное количество ребер между ними называется их расстоянием и обозначается d ( x, y). Интервал вершин, которые лежат на кратчайших между и б определяется как
Медианный граф определяется тем свойством, что для каждых трех вершин a, b и c эти интервалы пересекаются в одной точке:
Эквивалентно, для каждых трех вершин a, b и c можно найти вершину m ( a, b, c) такую, что невзвешенные расстояния в графе удовлетворяют равенствам
и m ( a, b, c) - единственная вершина, для которой это верно.
Также возможно определить медианные графы как наборы решений задач 2-выполнимости, как ретракты гиперкубов, как графы конечных медианных алгебр, как графы Бунемана расщепленных систем Хелли и как графы Windex 2; см. разделы ниже.
График дистрибутивной решетки, изображенный в виде диаграммы Хассе. В теории решетки граф конечной решетки имеет вершину для каждого элемента решетки и ребро для каждой пары элементов в отношении покрытия решетки. Решетки обычно представляются визуально с помощью диаграмм Хассе, которые представляют собой рисунки графов решеток. Эти графы, особенно в случае дистрибутивных решеток, оказываются тесно связанными с медианными графами.
В распределительной решетке самодуальная тернарная медианная операция Биркгофа
удовлетворяет определенным ключевым аксиомам, которые он разделяет с обычной медианой чисел в диапазоне от 0 до 1 и с медианными алгебрами в целом:
Распределительный закон может быть заменен ассоциативным законом:
Операция median также может использоваться для определения понятия интервалов для распределительных решеток:
Граф конечной дистрибутивной решетки имеет ребро между вершинами 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). Следовательно, граф произвольной конечной дистрибутивной решетки является медианным графом. И наоборот, если медианный граф G содержит две вершины 0 и 1, такие, что каждая другая вершина лежит на кратчайшем пути между ними (эквивалентно, m (0, a, 1) = a для всех a), то мы можем определить дистрибутивный решетка, в которой a ∧ b = m ( a, 0, b) и a ∨ b = m ( a, 1, b), а G будет графиком этой решетки.
Даффус и Риваль (1983) характеризуют графы дистрибутивных решеток как ретракты гиперкубов, сохраняющие диаметр. В более общем смысле, каждый медианный граф порождает тернарную операцию m, удовлетворяющую идемпотентности, коммутативности и дистрибутивности, но, возможно, без элементов идентичности дистрибутивной решетки. Каждая тернарная операция на конечном множестве, удовлетворяющем этим трем свойствам (но не обязательно имеющим элементы 0 и 1), аналогичным образом порождает медианный граф.
В средней графе, набор S вершин называется выпуклой, если для любых двух вершин и б, принадлежащих к S, весь интервал I (, б) представляет собой подмножество S. Эквивалентно, учитывая два определения интервалов выше, S является выпуклым, если она содержит все кратчайший путь между двумя из его вершин, или если она содержит медиану каждый набор из трех точек, по меньшей мере, две из которых взято из S. Заметим, что пересечение каждой пары выпуклых множеств само выпукло.
Выпуклые множества в медианном графе обладают свойством Хелли : если F - произвольное семейство попарно пересекающихся выпуклых множеств, то все множества в F имеют общее пересечение. В самом деле, если F имеет только три выпуклых множества S, T и U в нем, с a в пересечении пары S и T, b в пересечении пары T и U и c в пересечении пары S и U, то каждый кратчайший путь от a до b должен лежать внутри T в силу выпуклости, и аналогично каждый кратчайший путь между двумя другими парами вершин должен лежать внутри двух других множеств; но m ( a, b, c) принадлежит путям между всеми тремя парами вершин, поэтому он лежит внутри всех трех наборов и является частью их общего пересечения. Если F имеет более трех выпуклых множеств в нем, результат следует индукцией по количеству множеств, так как можно заменить произвольную пару множеств в F их пересечением, используя результат для троек множеств, чтобы показать, что замененное семейство все еще попарно пересекается.
Особенно важным семейством выпуклых множеств в медианном графе, играющим роль, аналогичную роли полупространств в евклидовом пространстве, являются множества
для каждого ребра uv графа. Другими словами, W uv состоит из вершин, более близких к u, чем к v, или, что то же самое, из вершин w таких, что кратчайший путь от v к w проходит через u. Чтобы показать, что W uv выпукло, пусть w 1 w 2... w k - произвольный кратчайший путь, который начинается и заканчивается в W uv ; тогда w 2 также должен лежать внутри W uv, иначе две точки m 1 = m ( u, w 1, w k) и m 2 = m ( m 1, w 2... w k) могут быть показаны (с помощью учитывая возможные расстояния между вершинами) как различные медианы u, w 1 и w k, что противоречит определению медианного графа, которое требует, чтобы медианы были уникальными. Таким образом, каждая последующая вершина на кратчайшем пути между двумя вершинами W uv также лежит внутри W uv, поэтому W uv содержит все кратчайшие пути между его узлами, одно из определений выпуклости.
Свойство Хелли для множеств W uv играет ключевую роль в описании медианных графов как решения примеров 2-выполнимости, описанных ниже.
Медианные графы имеют тесную связь с наборами решений задач 2-выполнимости, которые можно использовать как для характеристики этих графов, так и для связи их с сохраняющими смежность отображениями гиперкубов.
Экземпляр 2-выполнимости состоит из набора логических переменных и набора предложений, ограничений на определенные пары переменных, требующих, чтобы эти две переменные избегали определенных комбинаций значений. Обычно такие проблемы выражаются в соединительной нормальной форме, в которой каждое предложение выражается как дизъюнкция, а весь набор ограничений выражается как соединение предложений, например
Решением такого случая является присвоение значений истинности переменным, удовлетворяющим всем условиям, или, что то же самое, которое заставляет выражение конъюнктивной нормальной формы для этого экземпляра становиться истинным, когда в него подставляются значения переменных. Семейство всех решений имеет естественную структуру как медианную алгебру, где медиана трех решений формируется путем выбора каждого значения истинности в качестве функции большинства значений в трех решениях; несложно проверить, что это медианное решение не может нарушать ни одно из положений. Таким образом, эти решения образуют медианный граф, в котором сосед каждого решения формируется путем отрицания набора переменных, которые все ограничены, чтобы быть равными или неравными друг другу.
И наоборот, каждый медианный граф G может быть представлен таким образом как решение, установленное для экземпляра 2-выполнимости. Чтобы найти такое представление, создайте экземпляр 2-выполнимости, в котором каждая переменная описывает ориентацию одного из ребер в графе (назначение направления ребру, заставляющее граф стать направленным, а не ненаправленным), и каждое ограничение позволяет два ребра разделяют пару ориентаций только тогда, когда существует вершина v такая, что обе ориентации лежат на кратчайших путях от других вершин к v. Каждая вершина v из G соответствует решению этой 2-выполнимости Например, в которой все ребра направлены против. Таким образом, каждое решение экземпляра должно исходить из некоторой вершины v, где v - общее пересечение множеств W uw для ребер, направленных от w к u ; это общее пересечение существует благодаря свойству Хелли множеств W uw. Таким образом, решение этой 2-выполнимость инстанция соответствует один к одному с вершинами G.
Ретракция куба на шестивершинный подграф. Втягивания графы G является смежностью отображения, сохраняющей от G к одному из его подграфов. Точнее, это гомоморфизм графов φ из 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) содержит медианы всех троек своих вершин и также должен быть медианным графом. Другими словами, семейство медианных графов замыкается при операции ретракции.
Гиперкуба графа, в котором вершины соответствуют всем возможным к -разрядных битвекторов и в котором две вершины смежны, когда соответствующие битвекторов отличаются только одним битом, является частным случаем K сетки графа n - мерного и, следовательно, средний график. Медиана трех битовых векторов a, b и c может быть вычислена путем вычисления в каждой битовой позиции функции большинства битов a, b и c. Поскольку медианные графы закрываются при ретракции и включают гиперкубы, каждый ретракт гиперкуба является медианным графом.
И наоборот, каждый медианный граф должен быть ретрактом гиперкуба. Это можно увидеть из описанной выше связи между медианными графами и 2-выполнимостью: пусть G будет графом решений для случая 2-выполнимости; без потери общности этот пример можно сформулировать таким образом, что никакие две переменные не всегда равны или всегда неравны в каждом решении. Тогда пространство всех присвоений истинности переменным этого экземпляра образует гиперкуб. Для каждого предложения, сформированного как дизъюнкция двух переменных или их дополнений, в экземпляре 2-выполнимости можно сформировать ретракцию гиперкуба, в котором назначения истинности, нарушающие это предложение, отображаются в назначения истинности, в которых обе переменные удовлетворяют условию, без изменения других переменных в присвоении истинности. Композиция ретрактов, сформированных таким образом для каждого из предложений, дает ретракцию гиперкуба в пространство решений экземпляра и, следовательно, дает представление G как ретракт гиперкуба. В частности, медианные графы являются изометрическими подграфами гиперкубов и, следовательно, являются частичными кубами. Однако не все частичные кубы являются медианными графами; например, циклический граф с шестью вершинами - это частичный куб, но не медианный граф.
Как описывают Имрих и Клавжар (2000), изометрическое вложение медианного графа в гиперкуб может быть построено за время O ( m log n), где n и m - количество вершин и ребер графа соответственно.
Преобразование графа без треугольников в медианный граф. Проблемы проверки того, является ли граф медианным графом и является ли граф свободным от треугольников, были хорошо изучены, когда Имрих, Клавжар и Малдер (1999) заметили, что в некотором смысле они эквивалентны в вычислительном отношении. Следовательно, наиболее известная временная граница для проверки того, является ли граф свободным от треугольников, O ( m 1,41), также применима к проверке того, является ли граф медианным графом, и любое улучшение алгоритмов тестирования медианного графа также приведет к улучшению. в алгоритмах обнаружения треугольников в графах.
В одном направлении, предположим, что на входе дан граф G, и он должен проверить, не содержит ли G треугольников. Из G, построить новый граф H, имеющий в качестве вершин каждый набор ноль, один или два смежных вершин G. Два таких множества смежны в H, если они отличаются ровно на одну вершину. Эквивалентное описание Н является то, что она образована путем разделения каждого ребро G в пути двух краев, и добавлении новой вершины, соединенную со всеми оригинальными вершинами G. Этот граф H по построению является частичным кубом, но он является медианным графом только тогда, когда G не содержит треугольников: если a, b и c образуют треугольник в G, то { a, b }, { a, c }, и { Ь, с } не имеет медианы в H, для таких медианных бы, чтобы соответствовать множеству {, Ь, гр }, но наборы трех или более вершин G не образуют вершины в H. Следовательно, G не имеет треугольников тогда и только тогда, когда H - медианный граф. В случае, когда G не содержит треугольников, H - его симплексный граф. Алгоритм для эффективной проверки того, является ли H медианным графом, может с помощью этой конструкции также использоваться для проверки, является ли G свободным от треугольников. Это преобразование сохраняет вычислительную сложность задачи, для размера H пропорциональна, что из G.
Снижение в другом направлении, от обнаружения треугольников до тестирования медианного графа, является более сложным и зависит от предыдущего алгоритма распознавания медианного графа Хагауэра, Имриха и Клавжара (1999), который проверяет несколько необходимых условий для медианных графов за почти линейное время.. Ключевой новый шаг включает использование поиска в ширину для разделения вершин графа на уровни в соответствии с их расстояниями от произвольно выбранной корневой вершины, формирование графа из каждого уровня, в котором две вершины являются смежными, если они имеют общего соседа на предыдущем уровне., и поиск треугольников на этих графиках. Медиана любого такого треугольника должна быть общим соседом трех вершин треугольника; если этот общий сосед не существует, граф не является медианным графом. Если все треугольники, найденные таким образом, имеют медианы, и предыдущий алгоритм обнаруживает, что граф удовлетворяет всем остальным условиям для того, чтобы быть медианным графом, то это действительно должен быть медианный граф. Для этого алгоритма требуется не только возможность проверить, существует ли треугольник, но и список всех треугольников в графе уровней. В произвольных графах перечисление всех треугольников иногда требует времени Ω ( m 3/2), поскольку некоторые графы имеют такое количество треугольников, однако Hagauer et al. показывают, что количество треугольников, возникающих на графиках уровней их уменьшения, почти линейно, что позволяет Alon et al. метод быстрого матричного умножения для поиска используемых треугольников.
График Бунемана для пяти типов мышей. Филогения - это вывод эволюционных деревьев из наблюдаемых характеристик видов ; такое дерево должно размещать виды в различных вершинах и может иметь дополнительные скрытые вершины, но скрытые вершины должны иметь три или более инцидентных ребра и также должны быть помечены характеристиками. Характеристика является бинарной, если она имеет только два возможных значения, а набор видов и их характеристик демонстрирует идеальную филогению, когда существует эволюционное дерево, в котором вершины (виды и скрытые вершины), помеченные каким-либо конкретным значением характеристики, образуют смежное поддерево. Если невозможно построить дерево с совершенной филогенией, часто желательно найти такое дерево, которое демонстрирует максимальную экономию или, что эквивалентно, минимизирует количество раз, когда конечные точки ребра дерева имеют разные значения для одной из характеристик, суммированных по всем ребрам и всем. характеристики.
Бунеман (1971) описал метод определения идеальной филогении бинарных характеристик, если они существуют. Его метод естественным образом обобщается на построение медианного графа для любого набора видов и бинарных характеристик, который был назван медианной сетью или графом Бунемана и представляет собой тип филогенетической сети. Каждое эволюционное дерево максимальной экономичности встраивается в граф Бунемана в том смысле, что ребра дерева следуют по путям в графе, а количество изменений характеристических значений на краю дерева совпадает с числом в соответствующем пути. Граф Бунемана будет деревом тогда и только тогда, когда существует совершенная филогения; это происходит, когда нет двух несовместимых характеристик, для которых соблюдаются все четыре комбинации значений характеристик.
Чтобы сформировать граф Бунемана для набора видов и характеристик, сначала удалите повторяющиеся виды, которые неотличимы от некоторых других видов, и повторяющиеся характеристики, которые всегда совпадают с некоторыми другими характеристиками. Затем сформируйте скрытую вершину для каждой комбинации значений характеристик так, чтобы каждые два значения существовали в некоторых известных видах. В показанном примере есть маленькие коричневые бесхвостые мыши, маленькие серебристые бесхвостые мыши, маленькие коричневохвостые мыши, большие коричневохвостые мыши и большие серебристохвостые мыши; метод графа Бунемана формирует скрытую вершину, соответствующую неизвестному виду маленьких серебристо-хвостатых мышей, потому что каждая парная комбинация (маленькая и серебристая, маленькая и хвостатая, серебристая и хвостатая) наблюдается у некоторых других известных видов. Однако этот метод не позволяет сделать вывод о существовании больших коричневых бесхвостых мышей, поскольку не известно ни одной мыши, обладающей одновременно большими и бесхвостыми признаками. Как только скрытые вершины определены, сформируйте ребро между каждой парой видов или скрытых вершин, которые отличаются одной характеристикой.
Можно эквивалентно описать набор двоичных характеристик как систему разделения, семейство наборов, обладающих тем свойством, что дополнительный набор каждого набора в семействе также входит в семейство. В этой сплит-системе есть набор для каждого значения характеристики, состоящий из видов, которые имеют это значение. Когда скрытые вершины включены, результирующая система разделения обладает свойством Helly : каждое попарно пересекающееся подсемейство имеет общее пересечение. В некотором смысле медианные графы характеризуются как происходящие из систем расщепления Хелли: пары ( W uv, W vu), определенные для каждого ребра uv медианного графа, образуют расщепленную систему Хелли, поэтому, если применить конструкцию графа Бунемана к этой системе, то потребуются скрытые вершины, и результат будет таким же, как и у исходного графа.
Bandelt et al. (1995) и Bandelt, Macaulay amp; Richards (2000) описывают методы упрощенного ручного вычисления графа Бунемана и используют эту конструкцию для визуализации генетических взаимоотношений человека.
Декартово произведение графов образует средний граф из двух меньших срединных графиков. 
