헤밀턴 회로에 대해

헤밀턴 회로는 모든 정점을 꼭 한번씩 거쳐서 출발점으로 다시 돌아오는 경로이다.
책에서 헤밀턴 회로를 구하는 문제를 보았다.

이분은 헤밀턴회로를 DFS로 구현하였는데 각각의 노드에 도달할 때마다 이전에 방문한 정점을 방문하지 않으려고 방문한 정점과 방금 지나온 간선을 검색대상에서 제외하였다.

for( i =0;i<n;i++){

if(a[vertex][i]&&!check[i]){

a[vertex][i]=a[i][vertex]=0;
check[i]=true;
hamiltonCircuit(i);

a[vertex][i]=a[i][vertex]=0;
check[i]=false;
}
}

이런 식이다.

그러나.

헤밀턴 회로의 정의를 보면 지나간 간선을 다시 사용할 수 없다는 말은 없다.
다만 사용할수 없는 건 이러한 관계가 성립하기 때문이다.

각각의 정점을 꼭 한번씩 지난다->각각의 간선을 한번씩만 지난다.(물론 오일러의 경우처럼 모든 간선을 꼭 사용한다는 뜻은 아니다. 간선이 남을 수도 있다)

각각의 정점을 한번씩만 지나는 경우를 생각해 보자,
정점C에서 3번간선을 지나 정점 A에 도달 했다고 하자, 그렇다면 다신 3번 간선을 사용할 수 가 없다. 왜냐하면 이미 정점 C를 거쳐왔기 때문이다.


반대로 각각의 간선을 한번씩만 지나는 경우를 생각해보자.
정점 B에서 5번간선를 지나 정점 G에 도달한 상황에서 G에서 또다른 간선들을 이용하여 충분히B에 도달할 수 있다.

이러한 논리를 일반화 시키면 위의 관계가 성립함을 알 수 있다.

그리고 이러한 이유로
굳이 지나간 간선을 검색에서 제외할 이유가 없다.

어짜피 지나온 정점들을 방문하지 않는다는 조건은 지나온 간선들을 다시 방문하지 않는다는 조건을 포함하고 있다.

따라서 나는 다음과 같이 사용하는게 더 합리적이라고 본다.

for( i =0;i<n;i++){

if(a[vertex][i]&&!check[i]){

check[i]=true;
hamiltonCircuit(i);

check[i]=false;
}
}

http://khgkjg12.blogspot.kr/2016/08/dfs-hamilton-circuit-c.html