Depth First Search에 대한 걱정

Question

G가 방향이없는 연결된 그래프 인 경우 각 가장자리가 깊이 우선 검색 트리에 있거나 뒤쪽 가장자리에 있음을 증명합니다.

스티븐 스키 나 (Steven Skiena)의 직감과 강의에서, 나는 완전히 아래로 뛰어 내린 다음 이전의 정점으로 로프를 던지기 때문에 위의 내용이 사실임을 알고 있습니다. 또한 DFS가주기를 찾는 데 뛰어나다는 것도 알고 있습니다.

그러나 여기 내 문제는 가장자리가 나무 가장자리인지 아니면 뒤 가장자리인지 '증명'하는 방법을 모른다는 것입니다.

Answer 1

가능한 4 가지 경우 (이론적으로)를 고려하십시오. 에지가 될 수 있습니다

이

1. 나무 가장자리는
2. 백 가장자리
3. 나무 가장자리와 뒤쪽 가장자리 두
4. 나무 가장자리 또는 뒤쪽 가장자리 어느

증명하기 위해 무엇이 필요한지, 당신은 사건 3과 4가 일어날 수 없다는 것을 보여줄 필요가있다. 즉, 모순으로 이어진다.