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 , ..., en ) с последовательностью вершин ( v 1 , v 2 , ..., v n , v 1 ) .

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

Пусть G = ( V , E , Φ ) — ориентированный граф. Ориентированная цепь — это непустая направленная трасса ( e 1 , e 2 , ..., en ) с последовательностью вершин ( 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: посещение(v) = завершено(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, заархивировано из оригинала 4 февраля 2023 г. , получено 27 сентября 2016 г..
  3. ^ Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры», Теория графов , Тексты для выпускников по математике, том. 173, Springer, стр. 23–28, заархивировано из оригинала 4 февраля 2023 г. , получено 27 сентября 2016 г..
  4. ^ Такер, Алан (2006). «Глава 2: Покрытие схем и раскраски графов». Прикладная комбинаторика (5-е изд.). Хобокен: Джон Уайли и сыновья. п. 49. ИСБН 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), «Применение модульных уравнений в анализе ситуации», Анналы математики , вторая серия, 14 (1): 86–94, doi : 10.2307/1967604, JSTOR  1967604.
  8. ^ Ричард М. Карп (1972), «Сводимость среди комбинаторных задач» (PDF) , в Р.Э. Миллере и Дж. Тэтчере (ред.), Сложность компьютерных вычислений , Нью-Йорк: Пленум, стр. 85–103, в архиве (PDF) из оригинала от 10 февраля 2021 г. , получено 12 марта 2014 г..
  9. ^ Руда, Ø. (1960), «Заметки о схемах Гамильтона», American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928, JSTOR  2308928.
  10. ^ Джагер, Ф. (1985), «Обзор гипотезы о двойном покрытии цикла», Анналы дискретной математики 27 – Циклы в графиках , Математические исследования Северной Голландии, том. 27, стр. 1–12, номер документа : 10.1016/S0304-0208(08)72993-1..