무 방향 그래프의주기 정의

Question

무 방향 그래프에서 공식적인주기 정의를 찾을 수 없습니다. CLRS는 일반적인 사이클을 일반화 할 수없는 심플 사이클의 정의만을보고합니다.

이

는 CLRS 정의이다

1. k >= 3
2. v0 = vk
3. v1,..,vk는

그래서 해봤 특색있는 같습니다 무향 그래프에 symple 사이클 경로 <v0,v1,..,vk>되도록 인 일반 사이클을 정의하기 위해 3 조건을 제거하지만 우리가 somet를 가질 수 있기 때문에 이것이 작동하지 않습니다. hing 같은이 : <a, b, c, b, a> 분명히 사이클이 아닙니다.

Answer 1

내가 다음과 같이 3을 일반화 할 수 있다고 생각 :

1. 어느 v1이, ..., VK는 또는들이 간단한 사이클을 포함 별개 (정점의 연속 목록, 1, 2를 만족 & 3).

Answer 2

그래프 이론의 경로는 일부 연결 조건을 만족하는 가장자리 및/또는 꼭지점 목록을 의미합니다. 사이클은 닫힌 경로이며 첫 번째 및 마지막 목록 요소는 동일합니다. Wikipedia article

시작점과 끝점 이외의 반복 된 정점이나 가장자리가없는 경우 경로 또는주기를 간단하게 부릅니다. 귀하의 예는 순환이지만 단순한 순환은 아닙니다.