Википедия

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

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

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

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

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

Примеры править

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

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

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

 
Рамочный граф.

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

Симплекс-граф[en] κ(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. Смотрите разделы ниже.

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

 
Граф распределённой решётки, нарисованной в виде диаграммы Хассе.

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

В дистрибутивной решётке Биркхофа самодвойственная тернарная операция медианы[8]

m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c),

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

Дистрибутивный закон можно заменить ассоциативным:[9]

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

I(a,b) = {x | m(a, x, b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.[10]

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

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

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

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

Выпуклые множества в медианном графе имеют свойство Хэлли[en]: если F является произвольным семейством попарно пересекающихся выпуклых множеств, то все множества F имеют общую точку.[15] Так, пусть 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-выполнимости[en], которые можно использовать для описания этих графов и с помощью которых можно показать связь с отображением гиперкубов, сохраняющих смежность.[16]

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

 

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

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

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

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

Редукция графа G — это отображение графа G в один из его подграфов с сохранением смежности.[17] Точнее, это гомоморфизм φ из 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) содержит медианы всех троек вершин и должен быть медианным графом. Другими словами, семейство медианных графов замкнуто по отношению операции редукции.[18]

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

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

Имрих и Клавжар (Imrich, Klavžar 1998) пишут, что изометричное вложение медианного графа в гиперкуб можно построить за время O(m log n), где n и m — число вершин и рёбер графа.[20]

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

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

Задачи проверки, является ли граф медианным, и содержит ли граф треугольники, обе хорошо изучены, и как отмечают Имрих, Клавжар и Мулдер (Imrich, Klavžar, Mulder 1999), в некотором смысле они вычислительно эквивалентны.[21] Таким образом, лучшее известное время для проверки, есть ли в графе треугольники, равное O(m1.41),[22] можно использовать как оценку времени проверки, является ли граф медианным, и любое продвижение в задаче распознавания медианных графов приведёт к продвижению в алгоритмах определения треугольников в графах.

Для доказательства эквивалентности в одном направлении, предположим, что задан граф 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 является его симплекс-графом[en]. Алгоритм эффективной проверки, является ли H медианным графом, по этому построению может быть использован для проверки отсутствия треугольников в графе G. Такое преобразование сохраняет вычислительную сложность задачи, поскольку размер H пропорционален размеру G.

Сведение в другом направлении, от поиска треугольников к проверке, является ли граф медианным, более сложно и зависит от описанного алгоритма распознавания медианного графа (Hagauer, Imrich, Klavžar 1999), который проверяет некоторые необходимые условия медианного графа в почти линейное время. Новый ключевой шаг использует поиск в ширину для разложения графа на уровни согласно их расстоянию от произвольно выбранного корня, образуя тем самым граф, в котором две вершины смежны, если у них есть общий сосед на предыдущем уровне, и поиск треугольников происходит в этих графах. Медиана любого такого треугольника должна быть общим соседом трёх вершин треугольника. Если такой сосед не существует, граф не является медианным. Если все треугольники найдены и у всех них есть медианы, а также предыдущий алгоритм определяет, что граф удовлетворяет остальным условиям медианных графов, то он должен быть медианным. Заметим, что этот алгоритм требует не только проверки отсутствия треугольников, но и перечисление треугольников в графе уровней. В произвольном графе перечисление треугольников требует иногда время Ω(m3/2), поскольку некоторые графы имеют столько треугольников. Однако Хагауэр (Hagauer и др.) показал, что число треугольников, возникающих в уровневых графах, почти линейно, что позволило Алону (Alon и др.) использовать технику быстрого умножения матриц для поиска треугольников.

Деревья эволюции, графы Бунемана и системы разбиения Хэлли править

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

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

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

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

Можно эквивалентным образом описать набор бинарных характеристик как систему разбиений, семейств множеств[en]* со свойством, что дополнение любого множества в семействе принадлежит семейству. Эта система разбиений представляет множество для каждого значения характеристик, состоящее из видов, которые имеют это значение. Если включить скрытые вершины, результирующая система разбиений имеет свойство Хэлли[en] — любые попарные пересечения подсемейств не пусты. В некотором смысле медианные графы можно представить как производные от систем разбиений Хэлли — пары (Wuv, Wvu), определённые для каждого ребра uv медианного графа, образуют систему разбиений Хэлли, так, что в случае применения построения графа Бунемана к этой системе скрытые вершины не понадобятся, и результатом будет исходный граф.[24]

В статьях Bandelt, Forster, Sykes, Richards, 1995 и Bandelt, Macaulay, Richards, 2000 описывается техника упрощения ручного вычисления графов Бунемана и показано использование этой конструкции для визуального представления генетических связей людей.

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

 
Прямое произведение графов образует медианный граф из двух меньших медианных графов.
  • Прямое произведение любых двух медианных графов является тоже медианным графом. Медианы в результирующем графе можно найти путём независимого поиска медиан обоих сомножителей, точно так же, как медианы графов решёток можно найти путём независимого поиска медиан по всем линейным измерениям.
  • виндекс графа измеряет число поисков вперёд[en], необходимых для оптимального решения задачи, в которой задана последовательность вершин графа si и следует найти другую последовательность вершин ti, минимизирующую сумму расстояний d(si,ti) и d(ti − 1,ti). Медианные графы — это в точности те графы, для которых windex равен 2. В медианном графе, оптимальный выбор — это множество ti = m(ti − 1,si,si + 1).[1]
  • Свойство иметь единственную медиану называется также свойство единственности точек Штайнера.[1] Оптимальное дерево Штайнера для трёх вершин a, b и c в медианном графе можно найти как объединение трёх кратчайших путей, из a, b и c в m(a,b,c). Бандельт и Бартелеми (Bandelt, Barthélémy 1984) изучали задачу нахождения вершины, минимизирующей сумму расстояний[en] до каждой вершины заданного множества, и показали, что она имеет единственное решение для любого нечётного числа вершин медианного графа. Они также показали, что эта медиана вершин множества S медианного графа удовлетворяет критерию Кондорсе[en] победителя выборов: по сравнению с другими вершинами он ближе всех к большинству вершин S.
  • Как и в случае частичных кубов, любой медианный граф с n вершинами имеет максимум (n/2) log2 n рёбер. Однако число рёбер не может быть слишком маленьким: Клавжар, Мулдер и Шкрековски (Klavžar, Mulder, Škrekovski 1998) доказали, что в любом медианном графе выполняется неравенство 2n − m − k ≤ 2, где m — число рёбер и k — размерность гиперкуба, из которого граф получен. Это неравенство превращается в равенство тогда и только тогда, когда медианный граф не содержит кубов. Всё это следствия другого равенства для медианных графов: эйлерова характеристика Σ (-1)dim(Q) всегда равна единице, где сумма берётся по всем гиперкубам подграфов Q данного медианного графа.[25]

Примечания править

  1. ↑ 1 2 3 Chung, Graham, Saks, 1987.
  2. ↑ Buneman, 1971, Dress, Hendy, Huber, Moulton, 1997, Dress, Huber, Moulton, 1997.
  3. ↑ Bandelt, Barthélémy, 1984, Day, McMorris, 2003.
  4. ↑ Imrich, Klavžar, 2000, Утверждение 1.26, стр. 24.
  5. ↑ Это следует немедленно из свойства медианных графов как редукции гиперкуба, как описано ниже.
  6. ↑ А. В. Карзанов. Расширения конечных метрик и задача о размещении оборудования // Труды ИСА РАН. — 2007. — Т. 29. — С. 225—244.
  7. ↑ Soltan, Zambitskii, Prisˇacaru, 1973, Chepoi, Dragan, Vaxès, 2002, Chepoi, Fanciullini, Vaxès, 2004.
  8. ↑ Birkhoff, Kiss, 1947 приписывают определение этой операции статье G. Birkhoff. Lattice Theory. — American Mathematical Society, 1940. — С. 74..
  9. ↑ Knuth, 2008, стр. 65, и упражнения 75, 76 на страницах 89—90. Кнут утверждает, что неизвестно простого доказательства, что из ассоциативности следует дистрибутивность.
  10. ↑ Эквивалентность двух выражений в этом равенстве, одного в терминах операции медианы и другого в терминах операций решётки и неравенств, — это теорема 1 в работе Биркгофа и Кисса (Birkhoff, Kiss 1947).
  11. ↑ Birkhoff, Kiss, 1947, Теорема 2.
  12. ↑ Birkhoff, Kiss, 1947, стр. 751.
  13. ↑ Avann, 1961.
  14. ↑ Knuth, 2008 называет такое множество идеальным, но выпуклое множество в графе распределённой решётки — это не то же самое, что идеал решётки[en].
  15. ↑ Imrich, Klavžar, 2000, теорема 2.40, стр. 77.
  16. ↑ Bandelt, Chepoi, 2008, утверждение 2.5, стр.8; Chung, Graham, Saks, 1989; Feder, 1995; Knuth, 2008, теорема S, стр. 72.
  17. ↑ Hell, 1976.
  18. ↑ Imrich, Klavžar, 2000, утверждение 1.33, стр. 27.
  19. ↑ Bandelt, 1984; Imrich, Klavžar, 2000, Теорема 2.39, стр.76; Knuth, 2008, стр. 74.
  20. ↑ Техника, которая достигает апогея в лемме 7.10 на стр. 218 статьи, состоит в использовании алгоритма Чиба и Нишизеки (Chiba, Nishizeki 1985) для получения списка всех циклов длины 4 графа G, и с помощью которой создаётся граф, имеющий в качестве вершин рёбра графа G и в качестве рёбер его противоположные стороны цикла из 4 рёбер. Связные компоненты этих графов используются для образования координат гиперкуба. Эквивалентным алгоритмом является алгоритм Кнута (Knuth 2008), Алгоритм H, стр. 69.
  21. ↑ Об алгоритме распознавания медианных графов см. Jha, Slutzki, 1992, Imrich, Klavžar, 1998 и Hagauer, Imrich, Klavžar, 1999. Для алгоритма распознавания графов без треугольников см. Itai, Rodeh, 1978, Chiba, Nishizeki, 1985 и Alon, Yuster, Zwick, 1995.
  22. ↑ Alon, Yuster, Zwick, 1995. Алгоритм базируется на быстром перемножении матриц. Здесь m — число рёбер графа, а «O» большое скрывает большой постоянный множитель. Лучший практический алгоритм распознавания треугольников требует время O(m3/2). Для распознавания медианного графа ограничение времени можно выразить либо в терминах m или n (число вершин), как, например, m = O(n log n).
  23. ↑ Mulder, Schrijver, 1979 описали версию этого метода для систем характеристик, не требующих скрытых вершин, а Barthélémy, 1989 дал полную версию. Имя графам Бунемана дано в статьях Dress, Hendy, Huber, Moulton, 1997 и Dress, Huber, Moulton, 1997.
  24. ↑ Mulder, Schrijver, 1979.
  25. ↑ Škrekovski, 2001.
  26. ↑ Mulder, 1980.

Литература править

  • Noga Alon, Yuster Raphael, Zwick Uri. Color-coding // Journal of the Association for Computing Machinery. — 1995. — Т. 42, вып. 4. — С. 844–856. — doi:10.1145/210332.210337.
  • Avann. Metric ternary distributive semi-lattices // Proceedings of the American Mathematical Society. — American Mathematical Society, 1961. — Т. 12, вып. 3. — С. 407–414. — doi:10.2307/2034206. — JSTOR 2034206.
  • Bandelt. Retracts of hypercubes // Journal of Graph Theory. — 1984. — Т. 8, вып. 4. — С. 501–510. — doi:10.1002/jgt.3190080407.
  • Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre. Medians in median graphs // Discrete Applied Mathematics. — 1984. — Т. 8, вып. 2. — С. 131–142. — doi:10.1016/0166-218X(84)90096-9.
  • Bandelt, Hans-Jürgen; Chepoi, Victor. Metric graph theory and geometry: a survey // Contemporary Mathematics. — 2008. Архивировано 25 ноября 2006 года., to appear.
  • Hans-Jürgen Bandelt, P. Forster, B. C. Sykes, Martin B. Richards. Mitochondrial portraits of human populations using median networks // Genetics. — Т. 141, вып. 2. — С. 743–753. — PMID 8647407. — PMC 1206770.
  • Hans-Jürgen Bandelt, P. Forster, Arne Rohl. Median-joining networks for inferring intraspecific phylogenies // Molecular Biology and Evolution. — Т. 16, вып. 1. — С. 37–48. — PMID 10331250.
  • Hans-Jürgen Bandelt, Vincent Macaulay, Martin B. Richards. Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA // Molecular Phylogenetics and Evolution. — 2000. — Т. 16, вып. 1. — С. 8–28. — doi:10.1006/mpev.2000.0792. — PMID 10877936.
  • Jean-Pierre Barthélémy. From copair hypergraphs to median graphs with latent vertices // Discrete Mathematics. — 1989. — Т. 76, вып. 1. — С. 9–28. — doi:10.1016/0012-365X(89)90283-5.
  • Garrett Birkhoff , S. A. Kiss. A ternary operation in distributive lattices // Bulletin of the American Mathematical Society. — 1947. — Т. 53, вып. 1. — С. 749–752. — doi:10.1090/S0002-9904-1947-08864-9.
  • P. Buneman. Mathematics in the Archaeological and Historical Sciences / F. R. Hodson, D. G. Kendall, P. T. Tautu. — Edinburgh University Press, 1971. — С. 387–395.
  • V. Chepoi, F. Dragan, Y. Vaxès. Proc. 13th ACM-SIAM Symposium on Discrete Algorithms. — 2002. — С. 346–355.
  • V. Chepoi, C. Fanciullini, Y. Vaxès. Median problem in some plane triangulations and quadrangulations // Computational Geometry: Theory & Applications. — 2004. — Т. 27. — С. 193–210.
  • N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms // SIAM Journal on Computing. — 1985. — Т. 14. — С. 210–223. — doi:10.1137/0214017.
  • F. R. K. Chung, R. L. Graham, M. E. Saks. Discrete Algorithms and Complexity (Kyoto, 1986) / Herbert Wilf. — New York: Academic Press, 1987. — Т. 15. — С. 351–387. — (Perspectives in Computing).
  • F. R. K. Chung, R. L. Graham, M. E. Saks. A dynamic location problem for graphs // Combinatorica. — 1989. — Т. 9, вып. 2. — С. 111–132. — doi:10.1007/BF02124674.
  • William H. E. Day, F. R. McMorris. Axiomatic Concensus[sic] Theory in Group Choice and Bioinformatics. — Society for Industrial and Applied Mathematics, 2003. — С. 91–94. — ISBN 0-89871-551-2.
  • A. Dress, M. Hendy, K. Huber, V. Moulton. On the number of vertices and edges of the Buneman graph // Annals of Combinatorics. — 1997. — Т. 1, вып. 1. — С. 329–337. — doi:10.1007/BF02558484.
  • A. Dress, K. Huber, V. Moulton. Some variations on a theme by Buneman // Annals of Combinatorics. — 1997. — Т. 1, вып. 1. — С. 339–352. — doi:10.1007/BF02558485.
  • Dwight Duffus, Ivan Rival. Graphs orientable as distributive lattices // Proceedings of the American Mathematical Society. — American Mathematical Society, 1983. — Т. 88, вып. 2. — С. 197–200. — doi:10.2307/2044697. — JSTOR 2044697.
  • T. Feder. Stable Networks and Product Graphs. — 1995. — Т. 555.
  • Johann Hagauer, Wilfried Imrich, Sandi Klavžar. Recognizing median graphs in subquadratic time // Theoretical Computer Science. — 1999. — Т. 215, вып. 1–2. — С. 123–136. — doi:10.1016/S0304-3975(97)00136-9.
  • Pavol Hell. Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II. — Rome: Accad. Naz. Lincei, 1976. — Т. 17. — С. 263–268.
  • Wilfried Imrich, Sandi Klavžar. A convexity lemma and expansion procedures for bipartite graphs // European Journal of Combinatorics. — 1998. — Т. 19, вып. 6. — С. 677–686. — doi:10.1006/eujc.1998.0229.
  • Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
  • Wilfried Imrich, Sandi Klavžar, Henry Martyn Mulder. Median graphs and triangle-free graphs // SIAM Journal on Discrete Mathematics. — 1999. — Т. 12, вып. 1. — С. 111–118. — doi:10.1137/S0895480197323494.
  • A. Itai, M. Rodeh. Finding a minimum circuit in a graph // SIAM Journal on Computing. — 1978. — Т. 7, вып. 4. — С. 413–423. — doi:10.1137/0207033.
  • Pranava K. Jha, Giora Slutzki. Convex-expansion algorithms for recognizing and isometric embedding of median graphs // Ars Combinatorica. — 1992. — Т. 34. — С. 75–92.
  • Sandi Klavžar, Henry Martyn Mulder. Median graphs: characterizations, location theory and related structures // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1999. — Т. 30. — С. 103–127.
  • Sandi Klavžar, Henry Martyn Mulder, Riste Škrekovski. An Euler-type formula for median graphs // Discrete Mathematics. — 1998. — Т. 187, вып. 1. — С. 255–258. — doi:10.1016/S0012-365X(98)00019-3.
  • Donald E. Knuth. The Art of Computer Programming. — Addison-Wesley, 2008. — Т. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. — С. 64–74. — ISBN 978-0-321-53496-5.
  • Дональд Э. Кнут. Искусство программирования. — Москва, Санкт-Петербург, Киев: ООО "И. Д. Вильяме", 2013. — Т. 4A, Комбинаторные алгоритмы. Часть 1. — С. 90 – 101. — ISBN 978-5-8459-1744-7 (рус).
  • Henry Martyn Mulder. n-cubes and median graphs // Journal of Graph Theory. — 1980. — Т. 4, вып. 1. — С. 107–110. — doi:10.1002/jgt.3190040112.
  • Henry Martyn Mulder, Alexander Schrijver. Median graphs and Helly hypergraphs // Discrete Mathematics. — 1979. — Т. 25, вып. 1. — С. 41–50. — doi:10.1016/0012-365X(79)90151-1.
  • Ladislav Nebesk'y. Median graphs // Commentationes Mathematicae Universitatis Carolinae. — 1971. — Т. 12. — С. 317–325.
  • Riste Škrekovski. Two relations for median graphs // Discrete Mathematics. — 2001. — Т. 226, вып. 1. — С. 351–353. — doi:10.1016/S0012-365X(00)00120-5.
  • Солтан П.С., Замбицкий Д.К., Присакару К.Ф. Экстремальные задачи на графах и алгоритмы их решения. — Кишинёв: Штиинца, 1973.

Ссылки править

  • Median graphs, Information System for Graph Class Inclusions.
  • Network, Free Phylogenetic Network Software. Network generates evolutionary trees and networks from genetic, linguistic, and other data.
  • PhyloMurka, open-source software for median network computations from biological data.
Источник — https://ru.wikipedia.org/w/index.php?title=Медианный_граф&oldid=129000485