Определение цикла в неориентированном графе

Question

Я не могу найти формальное определение цикла в неориентированном графе.CLRS сообщает только определение симплексных циклов, которые мне не удается обобщить для универсального цикла.

Это определение CLRS: симплексный цикл в неориентированном графе - это путь <v0,v1,..,vk>, так что:

1. k >= 3
2. v0 = vk
3. v1,..,vk различаются

Поэтому я попытался удалить 3условие для определения общего цикла, но это не может работать, потому что у нас может быть что-то вроде этого: <a, b, c, b, a> это явно не цикл.

Answer 1

Я думаю, что вы можете обобщить 3 следующим образом:

1. Либо v1, ..., vk различны , либо они содержат простой цикл (непрерывный список вершин, удовлетворяющих 1,2, & 3).

Answer 2

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

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