Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Граф с краями, окрашенными для иллюстрации пути HAB (зеленый), замкнутого пути или обхода с повторяющейся вершиной BDEFDCB (синий) и цикла без повторяющегося ребра или вершины HDGH (красный).

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

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

Определения [ править ]

Схема, цикл [ править ]

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

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

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

Бесхордовые циклы [ править ]

На этом графике зеленый цикл (ABCDEFA) не имеет хорды, а красный цикл (GHIJKLG) - нет. Это потому, что край KI - это хорда.

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

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

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

Пространство цикла [ править ]

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

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

Обнаружение цикла [ править ]

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

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

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

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

Покрытие графиков циклами [ править ]

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

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

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

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

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

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

См. Также [ править ]

  • Цикл пространство
  • Основа цикла
  • Обнаружение цикла в последовательности повторяющихся значений функции

Ссылки [ править ]

  1. ^ а б в г Бендер и Уильямсон 2010 , стр. 164.
  2. ^ Гросс, Джонатан Л .; Йеллен, Джей (2005), «4.6 Графы и векторные пространства» , Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054.
  3. ^ Diestel Рейнхард (2012), "1,9 Некоторые линейная алгебра" , Теория графов , Graduate тексты по математике, 173 , Springer, стр. 23-28.
  4. ^ Такер, Алан (2006). «Глава 2: Покрывающие схемы и раскраски графиков». Прикладная комбинаторика (5-е изд.). Хобокен: Джон Уайли и сыновья. п. 49. ISBN 978-0-471-73507-6.
  5. ^ a b Седжвик, Роберт (1983), «Графические алгоритмы», Алгоритмы , Аддисон – Уэсли, ISBN 0-201-06672-6
  6. ^ Зильбершац, Авраам; Питер Гэлвин; Грег Гань (2003). Понятия операционной системы . John Wiley & Sons, INC. Стр.  260 . ISBN 0-471-25060-0.
  7. ^ Веблен, Освальд (1912), "Применение модульных уравнений в анализе Situs", Анналы математики , вторая серия 14 (1): 86-94, DOI : 10,2307 / 1967604 , JSTOR 1967604 .
  8. ^ Ричард М. Карп (1972), «Сводимость среди комбинаторных проблем» (PDF) , в RE Miller and JW Thatcher (ed.), Complexity of Computer Computations , New York: Plenum, pp. 85–103 .
  9. ^ Руда, Ø. (1960), "Замечание о контурах Гамильтон", American Mathematical Monthly , 67 (1): 55, DOI : 10,2307 / 2308928 , JSTOR 2308928 .
  10. ^ Jaeger, F. (1985), "Обзор цикла накрытия гипотезы", Annals дискретной математики 27 - Циклы в графах , Северная Голландия Математика исследований, 27 , стр. 1-12, DOI : 10.1016 / S0304- 0208 (08) 72993-1..
  • Балакришнан, ВК (2005). Очерк теории и проблем теории графов Шаума ([Nachdr.] Ed.). Макгроу-Хилл. ISBN 978-0070054899.
  • Бендер, Эдвард А .; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .