Цикл (теория графов)

Не следует путать с Цикл (граф) и Граф циклов (алгебра).

В теории графов два типа объектов обычно называются циклами.

Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H

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

Циклы без хорд

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

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

Периферийный цикл — это цикл в графе со свойством, что любые два ребра, не принадлежащие циклу, можно соединить путём внутренние точки которого не принадлежат циклу. В графе, не образованном добавлением одного ребра к циклу, периферийный цикл должен быть порождённым циклом.

Пространство циклов

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

Поиск цикла

Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещённой вершине (обратная дуга). Таким же образом, все обратные рёбра, которые алгоритм DFS обнаруживает, являются частями циклов. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 рёбер могут быть рёбрами дерева.

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

Приложения алгоритмов нахождения циклов включают графы ожидания для нахождения взаимных блокировок в системах с параллельными потоками.

Покрытие графов циклами

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

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

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

Классы графов, определяемые циклами

Некоторые важные классы графов можно определить или описать их циклами. Это:

• Двудольный граф — граф без нечётных циклов.
• Кактус — граф, в котором любая нетривиальная двусвязная компонента является циклом.
• Граф-цикл — граф, состоящий из единственного цикла.
• Хордальный граф — граф, в котором нет порождённых циклов длиной больше трёх.
• Ориентированный ациклический граф — ориентированный граф без циклов.
• Совершенный граф — граф без порождённых циклов нечётной длины более трёх, либо их дополнений.
• Псевдолес — граф, в котором каждая связная компонента имеет максимум один цикл.
• Сильно связный граф — ориентированный граф, в котором любая дуга входит в какой-либо цикл.
• Граф без треугольников — граф, в котором нет циклов длины три.