무 방향 그래프의주기 정의

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

이

는 CLRS 정의이다

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

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

출처

2011-09-18 Simone

ABCBA가 순환이 아닌 이유는 무엇입니까? – Leopd

가장자리를 두 번 이상 사용하지 않는다는 조건을 추가합니다. (이것은 정점이 뚜렷한 경우 당연히 함축되어 있으므로 단순 사이클에 명시 적으로 지정되지 않습니다.) –

@ 언뜻보기에 이것이 작동해야합니다. 그러나 인터넷에서 찾을 수 없기 때문에이 개념에 대해 일반적으로 받아 들여지는 정의가 존재하는지 여부는 의심 스럽다. 나는 시험을 위해 공부하고있어. 그래서 이걸 확실히해야 해. – Simone

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

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

출처

2011-09-18 18:01:20

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

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

출처

2011-09-19 08:48:11 Ante

답변

관련 문제