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

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, t ≥ 2		кососимметричный
↓
(если подключен) вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	(если двусторонний) бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный

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

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

Определение

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

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

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

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

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

Примеры

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

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

переключательные графики, графы с двойным покрытием и

Кососимметричный граф можно эквивалентно определить как граф двойного покрытия полярного графа или графа переключателей . который представляет собой неориентированный граф, в котором ребра, инцидентные каждой вершине, разделены на два подмножества. Каждая вершина полярного графа соответствует двум вершинам кососимметричного графа, а каждое ребро полярного графа соответствует двум ребрам кососимметричного графа. Эту эквивалентность использовали Голдберг и Карзанов (1996) для моделирования проблем сопоставления в терминах кососимметричных графов; в этом приложении два подмножества ребер в каждой вершине — это несовпадающие ребра и совпадающие ребра. Зелинка (вслед за Ф. Зитеком) и Кук визуализируют вершины полярного графа как точки, где несколько путей железнодорожного пути сходятся : если поезд въезжает на стрелку через путь, который входит в одном направлении, он должен выйти через путь в другом направлении. Проблема поиска несамопересекающихся гладких кривых между заданными точками на железнодорожном пути возникает при проверке достоверности определенных видов графических изображений . и может быть смоделирован как поиск регулярного пути в кососимметричном графе.

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

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

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

Соответствие

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

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

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

Теория натюрморта

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

Подобные методы удаления мостов в контексте сопоставления ранее рассматривались Габоу, Капланом и Тарджаном (1999) .

Удовлетворенность

Граф импликации . Его косую симметрию можно реализовать, повернув граф на угол 180 градусов и поменяв местами все ребра.

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

Признание

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

Ссылки

• Аспвалль, Бенгт; Пласс, Майкл Ф.; Тарьян, Роберт Э. (1979), «Алгоритм линейного времени для проверки истинности некоторых количественных логических формул», Information Processing Letters , 8 (3): 121–123, doi : 10.1016/0020-0190(79)90002 -4 .
• Бабенко, Максим А. (2006), «Ациклические двунаправленные и кососимметричные графы: алгоритмы и структура», Информатика – теория и приложения , Конспект лекций по информатике, том. 3967, Springer-Verlag, стр. 23–34, arXiv : math/0607547 , doi : 10.1007/11753728_6 , ISBN  978-3-540-34166-6 .
• Биггс, Норман (1974), Алгебраическая теория графов , Лондон: Издательство Кембриджского университета .
• Кук, Мэтью (2003), «Теория натюрморта», Новые конструкции в клеточных автоматах , Исследования Института Санта-Фе в области наук о сложности, Oxford University Press, стр. 93–118 .
• Эдмондс, Джек ; Джонсон, Эллис Л. (1970), «Сопоставление: хорошо решаемый класс линейных программ», Комбинаторные структуры и их приложения: материалы симпозиума в Калгари, июнь 1969 г. , Нью-Йорк: Гордон и Брич . Перепечатано в журнале «Комбинаторная оптимизация» — Эврика, ты уменьшаешься! , Springer-Verlag, Конспекты лекций по информатике 2570, 2003, стр. 27–30, дои : 10.1007/3-540-36478-1_3 .
• Габоу, Гарольд Н .; Каплан, Хаим; Тарьян, Роберт Э. (1999), «Уникальные алгоритмы максимального соответствия», Proc. 31-й симпозиум ACM. Теория вычислений (STOC) , стр. 70–78, номер документа : 10.1145/301250.301273 , ISBN.  1-58113-067-8 .
• Гольдберг, Эндрю В .; Карзанов, Александр В. (1996), «Задачи о путях в кососимметричных графах», Combinatorica , 16 (3): 353–382, doi : 10.1007/BF01261321 .
• Гольдберг, Эндрю В .; Карзанов, Александр В. (2004), «Максимальные кососимметричные потоки и паросочетания», Mathematical Programming , 100 (3): 537–568, arXiv : math/0304290 , doi : 10.1007/s10107-004-0505-z .
• Хуэй, Питер; Шефер, Маркус; Штефанкович, Даниэль (2004), «Железнодорожные пути и сливающиеся рисунки», Proc. 12-й Международный. Симп. Рисование графиков , Конспекты лекций по информатике, вып. 3383, Springer-Verlag, стр. 318–328 .
• Лалонд, Франсуа (1981), «Звездная задача для графов NP-полна», Discrete Mathematics , 33 (3): 271–280, doi : 10.1016/0012-365X(81)90271-5 , MR   0602044 .
• Торуп, Миккель (2000), «Почти оптимальная полностью динамическая связность графов», Proc. 32-й симпозиум ACM по теории вычислений , стр. 343–350, doi : 10.1145/335305.335345 , ISBN  1-58113-184-4 .
• Тутте, WT (1967), «Антисимметричные орграфы», Canadian Journal of Mathematics , 19 : 1101–1117, doi : 10.4153/CJM-1967-101-8 .
• Заславский, Томас (1982), «Знаковые графики», Дискретная прикладная математика , 4 : 47–74, doi : 10.1016/0166-218X(82)90033-6 , hdl : 10338.dmlcz/127957 .
• Заславский, Томас (1991), «Ориентация знаковых графов», Европейский журнал комбинаторики , 12 (4): 361–375, doi : 10.1016/s0195-6698(13)80118-7 .
• Зелинка, Богдан (1974), «Полярные графики и железнодорожное движение», Прикладная математика , 19 : 169–176 .
• Зелинка, Богдан (1976a), «Изоморфизмы полярных и поляризованных графов», Чехословацкий математический журнал , 26 (3): 339–351, doi : 10.21136/CMJ.1976.101409 .
• Зелинка, Богдан (1976b), «Аналог теоремы Менгера для полярных и поляризованных графов», Чехословацкий математический журнал , 26 (3): 352–360, doi : 10.21136/CMJ.1976.101410 .