0
DFS가 실행 된 방향이없는 그래프에서 (DFS 트리를 생성하여 모든 에지를 트리 에지 또는 후면 에지로 분류하기 위해) 그래프에는 후면 에지로만 구성된 사이클이있을 수 있습니까? 나무 가장자리가 없습니까?나무 가장자리가없는 방향이없는 그래프에서 순환합니까?
A
답변
1
확실히. 예를 들어, 큰 파벌을 가져 가라. 클릭에서 하나의 DFS 트리를 삭제하면 막대한 수의 가장자리가 생겨 결과적으로 많은 사이클이 생깁니다.