Цикл (теория графов)
В теории графов два типа объектов обычно называются циклами.
Один тип циклов, чаще называющиеся замкнутым обходом, состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежны. Другой тип циклов, иногда называемых простыми циклами, — это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Простые циклы можно описать набором рёбер, в отличие от замкнутых обходов, в которых наборы рёбер (с возможным повторением) не определяют однозначно порядок вершин. Ориентированный цикл в орграфе — это последовательность вершин, начинающаяся и завершающаяся в той же самой вершине, и в этой последовательности для любых двух последовательных вершин существует дуга из более ранней в более позднюю. Такое же различие между простыми циклами и обходами, как выше, можно определить и для ориентированных графов[1].
Циклы без хорд
Цикл без хорд в графе, также называемый дырой или порождённым циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. Антидыра — это дополнение дыры. Графы без хорд можно использовать для описания совершенных графов — согласно строгой теореме о совершенных графах граф является совершенным в том и только в том случае, когда он не содержит дыр и антидыр с нечётным числом вершин больше трёх. Хордальный граф — это специальный тип совершенных графов, в котором нет дыр размером больше трёх.
Обхват графа — это длина наименьшего цикла. Этот цикл обязательно не будет иметь хорд. Клетки — это наименьшие регулярные графы с заданной степенью вершин и обхватом.
Периферийный цикл — это цикл в графе со свойством, что любые два ребра, не принадлежащие циклу, можно соединить путём внутренние точки которого не принадлежат циклу. В графе, не образованном добавлением одного ребра к циклу, периферийный цикл должен быть порождённым циклом.
Пространство циклов
Понятие цикл может также относиться к элементам
.Поиск цикла
Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещённой вершине (обратная дуга)[4]. Таким же образом, все обратные рёбра, которые алгоритм DFS обнаруживает, являются частями циклов[5]. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 рёбер могут быть рёбрами дерева.
Ориентированный граф имеет цикл в том и только в том случае, когда DFS находит обратную дугу. Дуги вперёд и поперечные дуги не обязательно говорят о цикле. Многие алгоритмы
Приложения алгоритмов нахождения циклов включают графы ожидания для нахождения взаимных блокировок в системах с параллельными потоками[6].
Покрытие графов циклами
В работе 1736 года о
Задача поиска простого цикла, проходящего через каждую вершину ровно один раз, в отличие от покрытия рёбер, намного сложнее. Такие циклы известны как гамильтоновы циклы, и задача определения существуют ли такие циклы NP-полна[8]. Опубликовано множество исследований относительно классов графов, заведомо содержащих гамильтоновы циклы. Примером может служить теорема Оре о том, что гамильтонов цикл может быть найден в графе всегда, если при сложении степеней любой пары несмежных вершин получим по меньшей мере общее число вершин графа[9].
Гипотеза о двойном покрытии циклами утверждает, что для любого графа без мостов существует мультимножество простых циклов, покрывающих каждое ребро графа в точности два раза. Доказательство гипотезы, либо контрпример пока не найдены[10].
Классы графов, определяемые циклами
Некоторые важные классы графов можно определить или описать их циклами. Это:
- Двудольный граф — граф без нечётных циклов.
- Кактус — граф, в котором любая нетривиальная двусвязная компонента является циклом.
- Граф-цикл— граф, состоящий из единственного цикла.
- Хордальный граф — граф, в котором нет порождённых циклов длиной больше трёх.
- Ориентированный ациклический граф — ориентированный граф без циклов.
- Совершенный граф — граф без порождённых циклов нечётной длины более трёх, либо их дополнений.
- Псевдолес — граф, в котором каждая связная компонента имеет максимум один цикл.
- Сильно связный граф— ориентированный граф, в котором любая дуга входит в какой-либо цикл.
- Граф без треугольников — граф, в котором нет циклов длины три.
Примечания
- ↑ V. K. Balakrishnan. Schaum's outline of theory and problems of graph theory. — McGraw-Hill, 2005. — ISBN 978-0070054899.
- ↑ Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // Graph Theory and Its Applications. — 2nd. — CRC Press, 2005. — С. 197—207. — ISBN 9781584885054.
- ↑ Reinhard Diestel. 1.9 Some linear algebra // Graph Theory. — Springer, 2012. — Т. 173. — С. 23—28. — (Graduate Texts in Mathematics).. Перевод: Рейнгард Дистель. 1.9 Немного линейной алгебры // Теория графов. — Новосибирск: Издательство Института математики, 2002. — С. 35—40. — ISBN 5-86134-101-X..
- ↑ Alan Tucker. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. — 5th. — Hoboken: John Wiley & sons, 2006. — С. 49. — ISBN 978-0-471-73507-6.
- ↑ 1 2 Robert Sedgewick. Graph algorithms. — Addison-Wesley, 1983. — ISBN 0-201-06672-6.
- ↑ Abraham Silberschatz, Peter Galvin, Greg Gagne. Operating System Concepts. — John Wiley & Sons, INC., 2003. — С. 260. — ISBN 0-471-25060-0.
- ↑ Oswald Veblen. An Application of Modular Equations in Analysis Situs // Annals of Mathematics. — 1912. — Т. 14, вып. 1. — С. 86—94. — .
- ↑ Richard M. Karp. Complexity of Computer Computations / R. E. Miller and J. W. Thatcher. — New York: Plenum, 1972. — С. 85—103.
- ↑ Ø. Ore. Note on Hamilton circuits // American Mathematical Monthly. — 1960. — Т. 67, вып. 1. — С. 55. — .
- .
Для улучшения этой статьи желательно:
|