Кососимметричный граф

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

Кососимметрические графики впервые были введены под названием антисимметричных орграфов от Татты (1967) , затем в качестве двойных облицовочных графиков полярных графов Zelinka (1976b) , а еще позднее в качестве двойных облицовочных графов двунаправленных графов Заславского (1991) . Они возникают при моделировании поиска чередующихся путей и чередующихся циклов в алгоритмах поиска соответствий в графах, при проверке того, можно ли разбить натюрморт в «Игре жизни» Конвея на более простые компоненты, в рисовании графа и в графах импликации, используемых для эффективно решить 2-выполнимость проблема.

Определение [ править ]

Как определено, например, Голдбергом и Карзановым (1996) , кососимметричный граф G - это ориентированный граф вместе с функцией σ, отображающей вершины графа G в другие вершины графа G , удовлетворяющий следующим свойствам:

1. Для каждой вершины v σ ( v ) ≠ v ,
2. Для каждой вершины v σ (σ ( v )) = v ,
3. Для каждого ребра ( u , v ) (σ ( v ), σ ( u )) также должно быть ребром.

Можно использовать третье свойство расширить σ к функции ориентации реверсирования по краям G .

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

Путь или цикл в кососимметричном графе называется регулярным, если для каждой вершины v пути или цикла соответствующая вершина σ ( v ) не является частью пути или цикла.

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

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

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

Полярные / переключательные графики, графики двойного покрытия и двунаправленные графики [ править ]

Кососимметрический граф может быть эквивалентно определен как двойное накрытием графика полярного графа (введенного Zelinka (1974) , Zelinka (1976) , называемый переключателем графом с помощью Кука (2003) ), которая представляет собой неориентированный граф , в котором ребра, инцидентные каждой вершине, разбиваются на два подмножества. Каждая вершина полярного графа соответствует двум вершинам кососимметричного графа, а каждое ребро полярного графа соответствует двум ребрам кососимметричного графа. Эта эквивалентность используется Голдбергом и Карзановым (1996).Ошибка harvtxt: нет цели: CITEREFZelinka1976 ( справка )моделировать задачи согласования в терминах кососимметричных графов; в этом приложении два подмножества ребер в каждой вершине - это несовпадающие ребра и совпадающие ребра. Зелинка (вслед за Ф. Зитеком) и Кук визуализируют вершины полярного графа как точки, где сходятся несколько путей железнодорожного пути : если поезд входит в стрелку через путь, идущий с одного направления, он должен выйти через путь. в другом направлении. Проблема поиска несамопересекающихся гладких кривых между заданными точками на железнодорожном пути возникает при проверке правильности определенных видов графических рисунков ( Hui, Schaefer & Štefankovič 2004 ) и их можно смоделировать как поиск правильного пути в кососимметричный граф.

Тесно связанное с понятием является двунаправленными графами из Edmonds & Johnson (1970) ( «поляризованный график» в терминологии Zelinka (1974) , Zelinka (1976) ), график , в котором каждый из двух концов каждого ребра может быть либо голова или хвост, независимо от другого конца. Двунаправленный граф можно интерпретировать как полярный граф, позволяя определять разделение ребер в каждой вершине разделением конечных точек в этой вершине на головы и хвосты; однако, если поменять местами орел и решку в одной вершине («переключение» вершины, по терминологии Заславского (1991) ), получается другой двунаправленный граф, но тот же полярный граф. Ошибка harvtxt: нет цели: CITEREFZelinka1976 ( справка )

О соответствии между двунаправленными графами и кососимметричными графами (т. Е. Их графами с двойным накрытием) см. Заславский (1991) , раздел 5, или Бабенко (2006) .

Для того, чтобы сформировать двойное покрытие граф (т.е., соответствующая кососимметрична граф) от полярного графа G , создать для каждой вершины V из G две вершины v ₀ и V ₁ , и пусть σ ( v _я ) =  v _{1 -  я} . Для каждого ребра e  = ( u , v ) графа G создайте два направленных ребра в графе покрытия, одно ориентировано от u к v, а другое - от v к u . Если e находится в первом подмножестве ребер вv эти два ребра идут из u ₀ в v ₀ и из v ₁ в u ₁ , в то время как, если e находится во втором подмножестве, ребра идут из u ₀ в v ₁ и из v ₀ в u ₁ . В другом направлении, учитывая кососимметричный граф G , можно сформировать полярный граф, который имеет одну вершину для каждой соответствующей пары вершин в G и одно неориентированное ребро для каждой соответствующей пары ребер в G. Ненаправленные ребра в каждой вершине полярного графа можно разделить на два подмножества, в зависимости от того, из какой вершины полярного графа они выходят и входят.

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

Соответствие [ править ]

При построении сопоставлений в неориентированных графах важно найти чередующиеся пути , пути вершин, которые начинаются и заканчиваются в несовпадающих вершинах, в которых ребра в нечетных положениях пути не являются частью данного частичного сопоставления и в которых ребра в даже позиции в пути являются частью соответствия. Удалив совпадающие края такого пути из сопоставления и добавив несовпадающие кромки, можно увеличить размер сопоставления. Точно так же циклы, которые чередуются между согласованными и несогласованными ребрами, важны в задачах взвешенного согласования. В партии Гольдберга и Карзанова (1996)Как было показано, чередующийся путь или цикл в неориентированном графе можно смоделировать как регулярный путь или цикл в кососимметричном ориентированном графе. Чтобы создать кососимметричный граф из неориентированного графа G с заданным соответствием M , рассматривайте G как переключающий граф, в котором ребра в каждой вершине разделены на совпадающие и несовпадающие ребра; чередующийся путь в G является регулярным путем в этом графе переключений, а чередующийся цикл в G является регулярным циклом в графе переключений.

Голдберг и Карзанов (1996) обобщили алгоритмы чередующихся путей, чтобы показать, что существование регулярного пути между любыми двумя вершинами кососимметричного графа можно проверить за линейное время. Учитывая дополнительно неотрицательную функцию длины на ребрах графа, которая присваивает одинаковую длину любому ребру e и σ ( e ), кратчайший регулярный путь, соединяющий данную пару узлов в кососимметричном графе с m ребрами и n вершин можно проверить за время O ( m  log  n ). Если функция длины может иметь отрицательную длину, существование отрицательного регулярного цикла может быть проверено за полиномиальное время.

Наряду с проблемами пути, возникающими при согласовании, также изучались кососимметричные обобщения теоремы о максимальном потоке и минимальном разрезе ( Goldberg & Karzanov 2004 ; Tutte 1967 ).

Теория натюрморта [ править ]

Кук (2003) показывает, что образец натюрморта в «Игре жизни» Конвея может быть разделен на два меньших натюрморта тогда и только тогда, когда связанный граф переключателей содержит регулярный цикл. Как он показывает, для графов переключателей с не более чем тремя ребрами на вершину это можно проверить за полиномиальное время, многократно удаляя мосты (ребра, удаление которых разъединяет граф) и вершины, в которых все ребра принадлежат одному разделу, пока не перестанет такие упрощения могут быть выполнены. Если результат - пустой график, нет регулярного цикла; в противном случае в любом остающемся безмостовом компоненте может быть найден регулярный цикл. Повторный поиск мостов в этом алгоритме может быть эффективно выполнен с использованием алгоритма динамического графа Thorup (2000) .

Подобные методы удаления мостовидного протеза в контексте сопоставления ранее рассматривались Gabow, Kaplan & Tarjan (1999) .

Выполнимость [ править ]

Экземпляр проблемы 2-выполнимости , то есть логическое выражение в конъюнктивной нормальной форме с двумя переменными или отрицаниями переменных на каждое предложение, может быть преобразован в граф импликации путем замены каждого предложения двумя импликациями и . Этот граф имеет вершину для каждой переменной или отрицательной переменной и направленное ребро для каждой импликации; по построению она кососимметрична, с соответствием σ, которое отображает каждую переменную в ее отрицание. Как показали Aspvall, Plass & Tarjan (1979) , удовлетворительное присвоение экземпляру 2-выполнимости эквивалентно разбиению этого графа импликации на два подмножества вершин, S и σ ( S${\displaystyle \scriptstyle u\lor v}$${\displaystyle \scriptstyle (\lnot u)\Rightarrow v}$${\displaystyle \scriptstyle (\lnot v)\Rightarrow u}$) такой, что никакое ребро не начинается в S и не заканчивается в σ ( S ). Если такое разделение существует, удовлетворительное присвоение может быть сформировано путем присвоения истинного значения каждой переменной в S и ложного значения каждой переменной в σ ( S ). Это можно сделать тогда и только тогда, когда никакая сильно связная компонента графа не содержит одновременно некоторую вершину v и ее дополнительную вершину σ ( v). Если две вершины принадлежат одному и тому же компоненту сильной связности, соответствующие переменные или инвертируемые переменные ограничиваются равными друг другу в любом удовлетворяющем назначении экземпляра 2-выполнимости. Общее время для проверки сильной связности и нахождения раздела графа импликации линейно зависит от размера данного выражения 2-CNF.

Признание [ править ]

Это NP-полной , чтобы определить , является ли кососимметрична данный ориентированный граф, по результату Lalonde (1981) , что это NP-полной , чтобы найти цвет реверсирования инволюцию в двудольный граф . Такая инволюция существует тогда и только тогда, когда ориентированный граф, задаваемый ориентацией каждого ребра из одного цветового класса в другой, является кососимметричным, поэтому проверка кососимметрии этого ориентированного графа является сложной задачей. Эта сложность не влияет на алгоритмы поиска путей для кососимметричных графов, потому что эти алгоритмы предполагают, что кососимметричная структура задается как часть входных данных для алгоритма, а не требует, чтобы она выводилась из одного только графа.

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

• Аспвалл, Бенгт; Plass, Майкл Ф .; Тарьян, Роберт Э. (1979), «Алгоритм линейного времени для проверки истинности определенных количественных булевых формул», Письма об обработке информации , 8 (3): 121–123, DOI : 10.1016 / 0020-0190 (79) 90002 -4.
• Бабенко, Максим А. (2006), «Ациклические двунаправленные и кососимметричные графы: алгоритмы и структура», Компьютерные науки - теория и приложения , Lecture Notes in Computer Science, 3967 , Springer-Verlag, стр. 23–34, arXiv : математика / 0607547 , DOI : 10.1007 / 11753728_6 , ISBN 978-3-540-34166-6.
• Биггс, Норман (1974), алгебраическая теория графов , Лондон: издательство Кембриджского университета.
• Кук, Мэтью (2003), «Теория натюрморта», Новые конструкции в клеточных автоматах , Исследования Института Санта-Фе в области наук о сложности, Oxford University Press, стр. 93–118.
• Эдмондс, Джек ; Джонсон, Эллис Л. (1970), «Соответствие: хорошо решенный класс линейных программ», Комбинаторные структуры и их приложения: Труды симпозиума в Калгари, июнь 1969 г. , Нью-Йорк: Гордон и Брич. Перепечатано в книге «Комбинаторная оптимизация» - «Эврика, сжимайся!» , Springer-Verlag, Lecture Notes в области компьютерных наук 2570, 2003, стр 27-30. Дои : 10.1007 / 3-540-36478-1_3 .
• Габоу, Гарольд Н .; Каплан, Хаим; Tarjan, Роберт Э. (1999), "Уникальные алгоритмы максимального соответствия", Proc. 31-й ACM Symp. Теория вычислений (STOC) ., Стр 70-78, DOI : 10,1145 / 301250,301273 , ISBN 1-58113-067-8.
• Гольдберг, Эндрю В .; Карзанов, Александр В. (1996), "Проблемы пути в кососимметричных графах", Combinatorica , 16 (3): 353–382, doi : 10.1007 / BF01261321.
• Гольдберг, Эндрю В .; Карзанов, Александр В. (2004), «Максимальные кососимметричные потоки и согласования», Математическое программирование , 100 (3): 537–568, arXiv : math / 0304290 , doi : 10.1007 / s10107-004-0505-z.
• Хуэй, Питер; Шефер, Маркус; Штефанкович, Даниэль (2004), «Железнодорожные пути и сходящиеся рисунки», Proc. 12-е межд. Symp. Graph Drawing , Lecture Notes in Computer Science, 3383 , Springer-Verlag, стр. 318–328..
• Лалонда Франсуа (1981), "Le problème d'étoiles налить EST NP в виде графиков-Complet", дискретной математики , 33 (3): 271-280, DOI : 10.1016 / 0012-365X (81) 90271-5 , MR  0602044.
• Thorup, Mikkel (2000), "Почти оптимальная полностью динамическая связность графа", Proc. Тридцать второй ACM симпозиум по теории вычислений ., Стр 343-350, DOI : 10,1145 / 335305,335345 , ISBN 1-58113-184-4.
• Tutte, WT (1967), "антисимметричен орграфы", Canadian Journal математики , 19 : 1101-1117, DOI : 10,4153 / CJM-1967-101-8.
• Заславский, Томас (1982), "Подписанные графики", дискретная Прикладная математика , 4 : 47-74, DOI : 10.1016 / 0166-218X (82) 90033-6 , ЛВП : 10338.dmlcz / 127957.
• Заславский, Томас (1991), "Ориентирование подписанных графов", Европейский журнал комбинаторика , 12 (4): 361-375, DOI : 10.1016 / s0195-6698 (13) 80118-7.
• Зелинка, Богдан (1974), «Полярные графы и железнодорожное движение», Aplikace Matematiky , 19 : 169–176..
• Зелинка, Богдан (1976a), "Изоморфизмы полярных и поляризованных графов", Чехословацкий математический журнал , 26 : 339–351.
• Зелинка, Богдан (1976b), "Аналог теоремы Менгера для полярных и поляризованных графов", Чехословацкий математический журнал , 26 : 352–360.