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

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

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

Циклы без хорд[править | править вики-текст]

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

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

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

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

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

Поиск цикла[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

  1. V.K Balakrishnan Schaum's outline of theory and problems of graph theory. — McGraw-Hill, 2005. — ISBN 978-0070054899.
  2. Jonathan L. Gross, Jay Yellen Graph Theory and Its Applications. — CRC Press, 2005. — С. 197–207. — ISBN 9781584885054..
  3. Reinhard Diestel Graph Theory. — Springer, 2012. — Т. 173. — С. 23–28. — (Graduate Texts in Mathematics).. Перевод: Рейнгард Дистель 1.9 Немного линейной алгебры // Теория графов. — Новосибирск: Издательство Института математики, 2002. — С. 35–40. — ISBN 5-86134-101-X..
  4. Alan Tucker Applied Combinatorics. — 5th. — Hoboken: John Wiley & sons, 2006. — С. 49. — ISBN 978-0-471-73507-6.
  5. 1 2 Robert Sedgewick Graph algorithms. — Addison-Wesley, 1983. — ISBN 0-201-06672-6.
  6. Abraham Silberschatz, Peter Galvin, Greg Gagne Operating System Concepts. — John Wiley & Sons, INC., 2003. — С. 260. — ISBN 0-471-25060-0.
  7. Oswald Veblen An Application of Modular Equations in Analysis Situs // Annals of Mathematics. — 1912. — В. 1. — Т. 14. — С. 86–94..
  8. Richard M. Karp Complexity of Computer Computations / R. E. Miller and J. W. Thatcher. — New York: Plenum, 1972. — С. 85–103..
  9. Note on Hamilton circuits // American Mathematical Monthly. — 1960. — В. 1. — Т. 67. — С. 55..
  10. F. Jaeger Annals of Discrete Mathematics 27 – Cycles in Graphs. — 1985. — Т. 27. — С. 1–12. — (North-Holland Mathematics Studies). — DOI:10.1016/S0304-0208(08)72993-1