Цикл (теория графов) - Cycle (graph theory)

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

В теория графов, а цикл в график непустой след в котором только повторяется вершины - первая и последняя вершины. А направленный цикл в ориентированный граф непустой направленный след в котором единственными повторяющимися вершинами являются первая и последняя вершины.

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

Определения

Схема, цикл

  • А цепь непустой след в котором первая вершина равна последней вершине (закрытая тропа).[1]
Позволять г = (V, E, ϕ) быть графом. Схема - это непустой след (е1, е2, …, еп) с последовательностью вершин (v1, v2, …, vп, v1).
  • А цикл или простая схема - схема, в которой единственная повторяющаяся вершина является первой / последней вершиной.[1]
  • В длина схемы или цикла - это количество задействованных ребер.

Направленный контур, цикл

  • А направленная цепь непустой направленный след в котором первая вершина равна последней вершине.[1]
Позволять г = (V, E, ϕ) ориентированный граф. Направленный контур - это непустой направленный след (е1, е2, …, еп) с последовательностью вершин (v1, v2, …, vп, v1).
  • А направленный цикл или простая направленная схема - это направленная схема, в которой единственная повторяющаяся вершина является первой / последней вершиной.[1]

Бесхордовые циклы

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

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

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

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

Цикл пространство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

  1. ^ а б c d Бендер и Уильямсон 2010, п. 164.
  2. ^ Гросс, Джонатан Л .; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN  9781584885054.
  3. ^ Дистель, Рейнхард (2012), «1.9 Некоторая линейная алгебра», Теория графов, Тексты для выпускников по математике, 173, Springer, стр. 23–28..
  4. ^ Такер, Алан (2006). «Глава 2: Покрывающие схемы и раскраски графиков». Прикладная комбинаторика (5-е изд.). Хобокен: Джон Уайли и сыновья. п. 49. ISBN  978-0-471-73507-6.
  5. ^ а б Седжвик, Роберт (1983), «Графические алгоритмы», Алгоритмы, Эддисон – Уэсли, ISBN  0-201-06672-6
  6. ^ Зильбершац, Авраам; Питер Гэлвин; Грег Гань (2003). Понятия операционной системы. John Wiley & Sons, INC. Стр.260. ISBN  0-471-25060-0.
  7. ^ Веблен, Освальд (1912), "Применение модульных уравнений в анализе на месте", Анналы математики, Вторая серия, 14 (1): 86–94, Дои:10.2307/1967604, JSTOR  1967604.
  8. ^ Ричард М. Карп (1972), «Сводимость среди комбинаторных проблем» (PDF), в Р. Э. Миллер и Дж. У. Тэтчер (ред.), Сложность компьютерных вычислений, Нью-Йорк: Пленум, стр. 85–103..
  9. ^ Руда, Ø. (1960), «Заметка о схемах Гамильтона», Американский математический ежемесячный журнал, 67 (1): 55, Дои:10.2307/2308928, JSTOR  2308928.
  10. ^ Jaeger, F. (1985), "Обзор гипотезы о циклическом двойном покрытии", Анналы дискретной математики 27 - Циклы в графах, Математические исследования Северной Голландии, 27, стр. 1–12, Дои:10.1016 / S0304-0208 (08) 72993-1..