Цикл (теория графов)
- В теории графов цикл — это непустой путь с равными первой и последней вершинами.
- Направленный цикл в ориентированном графе — это непустой направленный маршрут с равными первой и последней вершинами.
- Граф без циклов называется ациклическим графом, а направленный ациклический граф — направленным ациклическим графом.
- Связный граф без циклов называется деревом.
- Циклы без аккордов в графе могут быть использованы для характеристики совершенных графов.
- Обнаружение цикла в направленных и неориентированных графах может быть определено по поиску в глубину (DFS).
- Для ориентированных графов можно использовать алгоритмы, основанные на распределенных сообщениях для обнаружения циклов.
- Несколько важных классов графов могут быть определены или охарактеризованы их циклами, включая двудольный граф, граф кактуса и другие.
Полный текст статьи: