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

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

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

Определение

Как определяют, например, Голдберг и Карзанов, кососимметрический граф $G$ — это ориентированный граф вместе с функцией $\sigma$, отображающей вершины графа $G$ в другие его вершины и удовлетворяющей свойствам:

1. Для любой вершины $v,\sigma (v)\neq v$,
2. Для любой вершины $v,\sigma (\sigma (v))=v$,
3. Для любой дуги $(u,v),(\sigma (v),\sigma (u))$ также должна быть дугой.

Можно использовать третье свойство для расширения $\sigma$ до функции обращения ориентации дуг графа $G$.

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

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

Примеры

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

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

Полярные графы и путевые стрелки, графы двойного накрытия и двунаправленные графы

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

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

О соответствии между двунаправленными графами и кососимметрическими графами см. статьи Заславского или Бабенко.

Чтобы образовать граф двойного накрытия (то есть соответствующий кососимметрический граф) из полярного графа $G$, создадим из каждой вершины $v$ графа $G$ две вершины, $v_{0}$ и $v_{1}$, и пусть $\sigma (v_{i})=v_{1-i}$. Для каждого ребра $e=(u,v)$ графа $G$ создадим два ориентированных ребра в накрывающем графе, одна из $u$ в $v$ и одна из $v$ в $u$. Если $e$ находится в первом подмножестве рёбер в $v$, эти две дуги идут из $u_{0}$ в $v_{0}$ и из $v_{1}$ в $u_{1}$, если же $e$ принадлежит другому подмножеству, дуги будут из $u_{0}$ в $v_{1}$ и из $v_{0}$ в $u_{1}$. Обратно, если дан кососимметрический граф $G$, можно образовать полярный граф, который имеет одну вершину для любой соответствующей пары вершин графа $G$ и одно неориентированное ребро для каждой соответствующей пары рёбер в $G$. Неориентированные рёбра в каждой вершине полярного графа можно разбить на два подмножества согласно тому, из какой вершины исходного графа дуга выходит и в какую входит.

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

Паросочетания

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

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

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

Теория игры «Жизнь»

Кук показал, что конфигурация в игре «Жизнь» может быть разбита на две меньшие конфигурации тогда и только тогда, когда граф ассоциированного графа путевых стрелок содержит регулярный цикл. Для графов путевых стрелок, содержащих не более трёх рёбер на одну вершину, это можно проверить за полиномиальное время путём удаления один за одним мостов (рёбер, удаление которых делает граф несвязным) и вершин, в которых все рёбра принадлежат одной части разбиения, пока есть возможность осуществлять такие упрощения. Если в результате получается пустой граф, регулярного цикла в графе нет. В противном случае регулярный цикл можно найти в любом компоненте, не содержащем мостов. Поиск мостов в этом алгоритме можно осуществить эффективно с помощью динамического алгоритма Сорупа. Аналогичную технику удаления мостов в контексте паросочетаний рассматривали до этого Габов, Каплан и Тарьян.

Выполнимость

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

Задача 2-выполнимости, то есть выражение в конъюнктивной нормальной форме с двумя переменными или их отрицанием может быть преобразовано в граф вывода путём замены каждого выражения $u\lor v$ двумя импликациями $(\lnot u)\Rightarrow v$ и $(\lnot v)\Rightarrow u$. В этом графе каждая вершина олицетворяет переменную или её отрицание и каждое ориентированное ребро — импликацию. Граф по построению кососимметричен с функцией $\sigma$, которая отображает каждую переменную в её отрицание. Как показали Асвалл, Пласс и Тарьян, нахождение выполняющего набора значений для экземпляра задачи 2-выполнимости эквивалентно разбиению этого графа вывода на два подмножества вершин, $S$ и $\sigma (S)$, так что никакая дуга не начинается в $S$ и кончается в $\sigma (S)$. Если такое разбиение существует, выполняющий набор значений может быть получен путём назначения значения «Истина» каждой переменной из $S$ и значения «Ложь» каждой переменной из $\sigma (S)$. Это можно сделать тогда и только тогда, когда никакая компонента сильной связности графа не содержит одновременно вершину $v$ и её дополняющую вершину $\sigma (v)$. Если две вершины принадлежат одной и той же компоненте сильной связности, соответствующие переменные или их отрицания необходимым образом равны друг другу в любом выполняющем наборе значений экземпляра задачи 2-выполнимости. Полное время проверки сильной связности и нахождения разбиения графа вывода линейно от размера данного 2-CNF выражения.

Распознавание

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

Литература

• Bengt Aspvall, Michael F. Plass, Robert E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas // Information Processing Letters. — 1979. — Т. 8, вып. 3. — С. 121–123. — doi:10.1016/0020-0190(79)90002-4.
• Maxim A. Babenko. Acyclic bidirected and skew-symmetric graphs: algorithms and structure // Computer Science – Theory and Applications. — Springer-Verlag, 2006. — Т. 3967. — С. 23–34. — (Lecture Notes in Computer Science). — ISBN 978-3-540-34166-6. — doi:10.1007/11753728_6.
• Norman L. Biggs. Algebraic Graph Theory. — London: Cambridge University Press, 1974.
• Matthew Cook. Still life theory // New Constructions in Cellular Automata. — Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, 2003. — С. 93–118..
• Jack Edmonds, Ellis L. Johnson. Matching: a well-solved class of linear programs // Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, June 1969. — Gordon and Breach, 1970. Перепечатано в «Combinatorial Optimization — Eureka, You Shrink!», Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27-30, doi:10.1007/3-540-36478-1_3.
• Harold N. Gabow, Haim Kaplan, Robert E. Tarjan. Unique maximum matching algorithms // Proc. 31st ACM Symp. Theory of Computing (STOC). — 1999. — С. 70–78. — ISBN 1-58113-067-8. — doi:10.1145/301250.301273.
• Andrew V. Goldberg, Alexander V. Karzanov. Path problems in skew-symmetric graphs // Combinatorica. — 1996. — Т. 16, вып. 3. — С. 353–382. — doi:10.1007/BF01261321.
• Andrew V. Goldberg, Alexander V. Karzanov. Maximum skew-symmetric flows and matchings // Mathematical programming. — 2004. — Т. 100, вып. 3. — С. 537–568. — doi:10.1007/s10107-004-0505-z. — arXiv:math/0304290.
• Peter Hui, Marcus Schaefer, Daniel Štefankovič. Train tracks and confluent drawings // Proc. 12th Int. Symp. Graph Drawing. — Springer-Verlag, 2004. — Т. 3383. — С. 318–328. — (Lecture Notes in Computer Science).
• François Lalonde. Le problème d’étoiles pour graphes est NP-complet // Discrete Mathematics. — 1981. — Т. 33, вып. 3. — С. 271–280. — doi:10.1016/0012-365X(81)90271-5.
• Mikkel Thorup. Near-optimal fully-dynamic [sic] graph connectivity // Proc. 32nd ACM Symposium on Theory of Computing. — 2000. — С. 343–350. — ISBN 1-58113-184-4. — doi:10.1145/335305.335345.
• Tutte W. T. Antisymmetrical digraphs // Canadian Journal of Mathematics. — 1967. — Т. 19. — С. 1101–1117. — doi:10.4153/CJM-1967-101-8.
• Thomas Zaslavsky. Signed graphs // Discrete Applied Mathematics. — 1982. — Т. 4. — С. 47–74. — doi:10.1016/0166-218X(82)90033-6.
• Thomas Zaslavsky. Orientation of signed graphs // European Journal of Combinatorics. — 1991. — Т. 12. — С. 361–375. — doi:10.1016/s0195-6698(13)80118-7.
• Bohdan Zelinka. Polar graphs and railway traffic // Aplikace Matematiky. — 1974. — Т. 19. — С. 169–176.
• Bohdan Zelinka. Isomorphisms of polar and polarized graphs // Czechoslovak Mathematical Journal. — 1976a. — Т. 26. — С. 339–351.
• Bohdan Zelinka. Analoga of Menger's theorem for polar and polarized graphs // Czechoslovak Mathematical Journal. — 1976b. — Т. 26. — С. 352–360.