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

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

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

Определение

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

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

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

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

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

Примеры

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

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

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

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

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

Чтобы образовать граф двойного накрытия (то есть соответствующий кососимметрический граф) из полярного графа $G$ , создадим из каждой вершины $v$ графа $G$ две вершины, $v_{0}$ и $v_{1}$ , и пусть $σ (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$ . Неориентированные рёбра в каждой вершине полярного графа можно разбить на два подмножества согласно тому, из какой вершины исходного графа дуга выходит и в какую входит.

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

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

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

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

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

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

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Статья
Шаблон:Книга
Шаблон:Книга
Шаблон:Книга.
Шаблон:Книга Перепечатано в «Combinatorial Optimization — Eureka, You Shrink!», Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, pp. 27-30, Шаблон:Doi.
Шаблон:Книга
Шаблон:Статья
Шаблон:Статья
Шаблон:Книга
Шаблон:Статья
Шаблон:Книга
Шаблон:Статья
Шаблон:Статья
Шаблон:Статья
Шаблон:Статья
Шаблон:Статья
Шаблон:Статья

Шаблон:Rq

↑ Граф путевых стрелок происходит от представления графа как аналога железнодорожных путей с местами соединений отдельных веток как переключающих стрелок.

[1] Граф путевых стрелок происходит от представления графа как аналога железнодорожных путей с местами соединений отдельных веток как переключающих стрелок.

[1]