stringtranslate.com

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

Граф с ребрами, окрашенными для иллюстрации замкнутого пути , H–A–B–A–H, зеленым цветом; контур, представляющий собой замкнутый путь, в котором все ребра различны, B–D–E–F–D–C–B, синим цветом; и цикл, представляющий собой замкнутый путь, в котором все вершины различны, H–D–G–H, красным цветом.

В теории графов цикл в графе — это непустой путь, в котором равны только первая и последняя вершины . Направленный цикл в ориентированном графе — это непустой направленный путь , в котором равны только первая и последняя вершины.

Граф без циклов называется ациклическим графом . Ориентированный граф без направленных циклов называется ориентированным ациклическим графом . Связный граф без циклов называется деревом .

Определения

Цепь и цикл

Пусть G = ( V , E , Φ ) — граф. Контур — это непустой путь ( e 1 , e 2 , ..., e n ) с последовательностью вершин ( v 1 , v 2 , ..., v n , v 1 ) .

Направленная цепь и направленный цикл

Пусть G = ( V , E , Φ ) — ориентированный граф. Направленный контур — это непустой направленный путь ( e 1 , e 2 , ..., e n ) с последовательностью вершин ( v 1 , v 2 , ..., v n , v 1 ) .

Цикл без аккорда

В этом графе зеленый цикл A–B–C–D–E–F–A не имеет хорды, тогда как красный цикл G–H–I–J–K–L–G не имеет. Это потому, что ребро {K, I} является хордой.

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

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

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

Пространство для велосипедов

Термин цикл может также относиться к элементу пространства циклов графа. Существует много пространств циклов, по одному для каждого поля коэффициентов или кольца. Наиболее распространенным является бинарное пространство циклов (обычно называемое просто пространством циклов ), которое состоит из наборов ребер, которые имеют четную степень в каждой вершине; оно образует векторное пространство над двухэлементным полем . По теореме Веблена каждый элемент пространства циклов может быть образован как объединение простых циклов без пересечений ребер. Базис циклов графа — это набор простых циклов, который образует базис пространства циклов. [2]

Используя идеи алгебраической топологии , бинарное циклическое пространство обобщается до векторных пространств или модулей над другими кольцами, такими как целые числа, рациональные или действительные числа и т. д. [3]

Обнаружение цикла

Существование цикла в ориентированных и неориентированных графах можно определить по тому, находит ли поиск в глубину (DFS) ребро, указывающее на предка текущей вершины (т. е. содержит ли оно обратное ребро ). [4] Все обратные ребра, которые пропускает DFS, являются частью циклов. [5] В неориентированном графе ребро к родителю узла не должно считаться обратным ребром, но нахождение любой другой уже посещенной вершины будет указывать на обратное ребро. В случае неориентированных графов для нахождения цикла в графе с n вершинами требуется всего O ( n ) времени , поскольку не более n  − 1 ребра могут быть ребрами дерева.

Многие алгоритмы топологической сортировки также обнаружат циклы, поскольку они являются препятствиями для существования топологического порядка. Кроме того, если направленный граф был разделен на сильно связанные компоненты , циклы существуют только внутри компонентов, а не между ними, поскольку циклы сильно связаны. [5]

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

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

Алгоритм

Вышеупомянутое использование поиска в глубину для нахождения цикла можно описать следующим образом:

Для каждой вершины v: visit(v) =finished(v) = falseДля каждой вершины v: DFS(v)

где

ДФС(v) = если закончено(v): возврат если посетил(а): "Цикл найден" возвращаться посетил(v) = правда для каждого соседа w: DFS(w) завершено(v) = правда

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

Вариант, использующий поиск в ширину , найдет цикл минимально возможной длины.

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ abcd Бендер и Уильямсон 2010, с. 164.
  2. ^ Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054, заархивировано из оригинала 2023-02-04 , извлечено 2016-09-27.
  3. ^ Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory , Graduate Texts in Mathematics, т. 173, Springer, стр. 23–28, архивировано из оригинала 2023-02-04 , извлечено 2016-09-27.
  4. ^ Такер, Алан (2006). "Глава 2: Покрытие цепей и раскраска графов". Прикладная комбинаторика (5-е изд.). Хобокен: John Wiley & sons. стр. 49. ISBN 978-0-471-73507-6.
  5. ^ ab Седжвик, Роберт (1983), «Графовые алгоритмы», Алгоритмы , Эддисон–Уэсли, ISBN 0-201-06672-6
  6. ^ Зильбершатц, Абрахам; Питер Гэлвин; Грег Ганье (2003). Концепции операционных систем . John Wiley & Sons, INC. стр. 260. ISBN 0-471-25060-0.
  7. ^ Веблен, Освальд (1912), «Применение модульных уравнений в анализе Situs», Annals of Mathematics , вторая серия, 14 (1): 86–94, doi :10.2307/1967604, JSTOR  1967604.
  8. ^ Ричард М. Карп (1972), «Сводимость среди комбинаторных проблем» (PDF) , в RE Miller и JW Thatcher (ред.), Complexity of Computer Computations , Нью-Йорк: Plenum, стр. 85–103, архивировано (PDF) из оригинала 2021-02-10 , извлечено 2014-03-12.
  9. ^ Оре, О. (1960), «Заметка о схемах Гамильтона», American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928, JSTOR  2308928.
  10. ^ Jaeger, F. (1985), «Обзор гипотезы о двойном покрытии цикла», Annals of Discrete Mathematics 27 – Cycles in Graphs , North-Holland Mathematics Studies, т. 27, стр. 1–12, doi :10.1016/S0304-0208(08)72993-1.