В теории графов , разделе математики, кососимметричный граф — это ориентированный граф , который изоморфен своему собственному транспонированному графу , графу, образованному путем обращения всех его ребер при изоморфизме, который является инволюцией без каких-либо неподвижных точек . Кососимметричные графы идентичны графам двойного покрытия двунаправленных графов .
Кососимметричные графы были впервые введены под названием антисимметричных орграфов Таттом (1967), позднее как графы двойного покрытия полярных графов Зелинкой (1976b), а еще позже как графы двойного покрытия двунаправленных графов Заславским (1991). Они возникают при моделировании поиска чередующихся путей и чередующихся циклов в алгоритмах поиска соответствий в графах, при проверке того, можно ли разбить на более простые компоненты узор натюрморта в игре Конвея «Жизнь» , при рисовании графов и в графах импликаций, используемых для эффективного решения проблемы 2-выполнимости .
Как определено, например, Голдбергом и Карзановым (1996), кососимметричный граф G представляет собой ориентированный граф вместе с функцией σ, отображающей вершины G в другие вершины G , удовлетворяющий следующим свойствам:
Третье свойство можно использовать для расширения σ до функции , меняющей ориентацию на ребрах G.
Транспонированный граф графа G — это граф, образованный путем обращения каждого ребра графа G , а σ определяет изоморфизм графа из G в его транспонированный граф. Однако в кососимметричном графе дополнительно требуется, чтобы изоморфизм сопоставлял каждую вершину с другой вершиной, а не позволял вершине отображаться на себя посредством изоморфизма или группировать более двух вершин в цикл изоморфизма.
Путь или цикл в кососимметричном графе называется регулярным , если для каждой вершины v пути или цикла соответствующая вершина σ( v ) не является частью пути или цикла.
Каждый ориентированный граф путей с четным числом вершин является кососимметричным, благодаря симметрии, которая меняет местами два конца пути. Однако графы путей с нечетным числом вершин не являются кососимметричными, поскольку симметрия обращения ориентации этих графов отображает центральную вершину пути на себя, что не допускается для кососимметричных графов.
Аналогично, ориентированный циклический граф кососимметричен тогда и только тогда, когда он имеет четное число вершин. В этом случае число различных отображений σ, реализующих кососимметрию графа, равно половине длины цикла.
Кососимметричный граф может быть эквивалентно определен как двойной покрывающий граф полярного графа или графа переключателей , [1] который является неориентированным графом, в котором ребра, инцидентные каждой вершине, разделены на два подмножества. Каждая вершина полярного графа соответствует двум вершинам кососимметричного графа, а каждое ребро полярного графа соответствует двум ребрам кососимметричного графа. Эта эквивалентность используется Голдбергом и Карзановым (1996) для моделирования проблем соответствия в терминах кососимметричных графов; в этом приложении два подмножества ребер в каждой вершине являются несоответствующими ребрами и сопоставленными ребрами. Зелинка (следуя Ф. Зитеку) и Кук визуализируют вершины полярного графа как точки, где сходятся несколько путей железнодорожного пути : если поезд въезжает на стрелку по пути, который приходит с одного направления, он должен выехать по пути в другом направлении. Проблема поиска несамопересекающихся гладких кривых между заданными точками на железнодорожном пути возникает при проверке допустимости определенных видов графических изображений [2] и может быть смоделирована как поиск регулярного пути в кососимметричном графе.
Близкое к этому понятие — двунаправленный граф или поляризованный граф , [3] граф, в котором каждый из двух концов каждого ребра может быть либо головой, либо хвостом, независимо от другого конца. Двунаправленный граф можно интерпретировать как полярный граф, позволяя разбиению ребер в каждой вершине определяться разбиением конечных точек в этой вершине на головы и хвосты; однако, обмен ролями голов и хвостов в одной вершине («переключение» вершины) создает другой двунаправленный граф, но тот же полярный граф. [4]
Чтобы сформировать двойной покрывающий граф (т. е. соответствующий кососимметричный граф) из полярного графа 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 . Неориентированные ребра в каждой вершине полярного графа можно разбить на два подмножества в соответствии с тем, из какой вершины полярного графа они выходят и в какую вершину входят.
Регулярный путь или цикл кососимметричного графа соответствует пути или циклу в полярном графе, который использует не более одного ребра из каждого подмножества ребер в каждой из своих вершин.
При построении сопоставлений в неориентированных графах важно найти чередующиеся пути , пути вершин, которые начинаются и заканчиваются в несопоставленных вершинах, в которых ребра в нечетных позициях в пути не являются частью заданного частичного сопоставления и в которых ребра в четных позициях в пути являются частью сопоставления. Удаляя сопоставленные ребра такого пути из сопоставления и добавляя несопоставленные ребра, можно увеличить размер сопоставления. Аналогично, циклы, которые чередуются между сопоставленными и несопоставленными ребрами, важны в задачах взвешенного сопоставления. Переменный путь или цикл в неориентированном графе можно смоделировать как обычный путь или цикл в кососимметричном ориентированном графе. [5] Чтобы создать кососимметричный граф из неориентированного графа G с указанным сопоставлением M , рассмотрим G как граф переключателей, в котором ребра в каждой вершине разделены на сопоставленные и несопоставленные ребра; Тогда чередующийся путь в G является регулярным путем в этом графе переключений, а чередующийся цикл в G является регулярным циклом в графе переключений.
Голдберг и Карзанов (1996) обобщили алгоритмы чередующихся путей, чтобы показать, что существование регулярного пути между любыми двумя вершинами кососимметричного графа может быть проверено за линейное время. При наличии дополнительно неотрицательной функции длины на ребрах графа, которая назначает одинаковую длину любому ребру e и σ( e ), кратчайший регулярный путь, соединяющий заданную пару узлов в кососимметричном графе с m ребрами и n вершинами, может быть проверен за время O( m log n ). Если функция длины может иметь отрицательные длины, существование отрицательного регулярного цикла может быть проверено за полиномиальное время.
Наряду с проблемами путей, возникающими при паросочетаниях, также изучались кососимметричные обобщения теоремы о максимальном потоке и минимальном разрезе . [6]
Кук (2003) показывает, что узор натюрморта в игре Конвея «Жизнь» может быть разделен на два меньших натюрморта тогда и только тогда, когда связанный граф переключателей содержит регулярный цикл. Как он показывает, для графов переключателей с максимум тремя ребрами на вершину это можно проверить за полиномиальное время, многократно удаляя мосты (ребра, удаление которых разъединяет граф) и вершины, в которых все ребра принадлежат одному разделу, пока больше нельзя будет выполнять такие упрощения. Если результатом является пустой граф , регулярного цикла нет; в противном случае регулярный цикл может быть найден в любом оставшемся компоненте без мостов. Повторный поиск мостов в этом алгоритме может быть выполнен эффективно с использованием динамического алгоритма графа Торупа (2000).
Аналогичные методы удаления мостиков в контексте сопоставления ранее рассматривались Габовым, Капланом и Тарьяном (1999).
Экземпляр проблемы 2-выполнимости , то есть булево выражение в конъюнктивной нормальной форме с двумя переменными или отрицаниями переменных на предложение, может быть преобразовано в граф импликации путем замены каждого предложения двумя импликациями и . Этот граф имеет вершину для каждой переменной или отрицаемой переменной и направленное ребро для каждой импликации; по построению он кососимметричен с соответствием σ, которое отображает каждую переменную в ее отрицание. Как показали Аспвалл, Пласс и Тарьян (1979), удовлетворяющее назначение экземпляру 2-выполнимости эквивалентно разбиению этого графа импликации на два подмножества вершин, S и σ( S ), таким образом, что ни одно ребро не начинается в S и не заканчивается в σ( S ). Если такое разбиение существует, удовлетворяющее назначение может быть сформировано путем присвоения истинного значения каждой переменной в S и ложного значения каждой переменной в σ( S ). Это можно сделать тогда и только тогда, когда ни один сильно связанный компонент графа не содержит как некоторую вершину v , так и ее дополнительную вершину σ( v ). Если две вершины принадлежат одному и тому же сильно связанному компоненту, соответствующие переменные или отрицательные переменные ограничены равными друг другу в любом удовлетворяющем назначении экземпляра 2-выполнимости. Общее время проверки сильной связности и поиска разбиения графа импликации линейно зависит от размера данного выражения 2-CNF.
NP-полной задачей является определение того, является ли заданный ориентированный граф кососимметричным, по результату Лалонда (1981), что NP-полной задачей является нахождение инволюции, меняющей цвет в двудольном графе . Такая инволюция существует тогда и только тогда, когда ориентированный граф, заданный ориентацией каждого ребра из одного цветового класса в другой, является кососимметричным, поэтому проверка кососимметричности этого ориентированного графа сложна. Эта сложность не влияет на алгоритмы поиска пути для кососимметричных графов, поскольку эти алгоритмы предполагают, что кососимметричная структура задана как часть входных данных для алгоритма, а не требуют, чтобы она была выведена только из графа.
