7개의 댓글이 있습니다.
-
-
infoefficiency -
답변 주신것에 감사드립니다.
제가 뭔가 아주 당연한 것 같은것을 이해하지 못하고 있는것 같아요 ㅠㅠ
오일러 트레일로 주어진 간선들도 결국은 그냥 오일러 서킷과 같은 코드를 이용하여 푸는것 맞나요? ㅠㅠ
책이나 Being 님께서 설명하신게 오일러 트레일을 구하려면
오일러서킷에서 간선 하나만 제거하면 그것이 오일러 트레일이 된다
라고 저는 이해했거든요 ㅎㅎ감사합니다 ^^
10년 전 link
-
-
-
JongMan -
네 같은 코드를 이용해 푸는 것이 맞습니다. 말씀하신 그래프에서 경로 1-3-4-1-4-2-1은 서킷이기 때문에 시작점을 달리 하면 다양한 방법으로 표현할 수 있습니다. 3-4-1-4-2-1-3, 4-1-4-2-1-3-4 등도 모두 같은 서킷을 나타낸다고 할 수 있지요. 따라서 우리가 추가한 경로 4-1이 맨 앞에 오도록 한 뒤 이 간선을 끊으면 오일러 트레일을 얻을 수 있지요.
그런데 사실 끝점에서 시작점으로 간선을 연결한다는 것은 설명을 쉽게 하기 위한 도구에 가깝습니다. 말씀하신 대로 간선을 추가하지 않고 오일러 서킷 찾는 코드를 돌려도 오일러 트레일을 얻을 수 있지요. 왜일까요? 시작점과 끝점 외의 모든 점은 짝수점이므로 여기에서 끝날 수는 없죠. 시작점은 홀수점이므로, 여기서 끝날 수도 없습니다. (예를 들어 시작점의 차수가 3이라면, 처음에 나갈 때 간선을 하나 쓰고, 다음에 시작점에 도착하면 반드시 나가는데 쓸 간선도 하나 있게 되죠.) 따라서 항상 경로는 끝점에서 끝나게 됩니다. 그 후의 동작은 서킷을 찾는 경우와 똑같죠.
혼란을 드려서 죄송하고, 다음 쇄에서는 좀더 개선해 보도록 하겠습니다. ^^;
10년 전 link
-
-
-
infoefficiency -
아 이해했습니다 ㅎㅎ 정말 감사합니다 ^^
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
infoefficiency
스터디 사람들과 고민 끝에 질문드립니다.
책에 있는 오일러 트레일의 설명에서는
만약 a에서 시작하고 b에서 끝나는 오일일러 트레일에
(b,a)의 간선을 실제로 인접행렬에 추가하여
오일러 서킷을 만든 뒤 나중에 간선을 제거하는 작업을 한다고
하였습니다.
그런데 간선을 제거하는 작업이 정확히 어떤 것인지 모르겠습니다.
예를 들어
1 -> 3
3 -> 4
4 -> 2
2 -> 1
1 -> 4
의 간선을 가지는 오일러 트레일이 있다고 하였을 때
책의 지시대로 4 -> 1을 추가한뒤 오일러 서킷을 구하면
1 -> 3 -> 4 -> 1-> 4 -> 2 ->1 가 되는데
애초에 구해야 하는 오일러 트레일은
1 -> 3 -> 4-> 2-> 1-> 4 가 되어야 합니다.
마지막 간선을 제거하는 작업이 정확히 어떻게 해야 하는지 몰라서
트레일을 구현을 못하겠습니다.
cf)
간선을 실제로 추가하는 작업을 하지 않고 오일러 서킷을 돌리니
1 -> 3 -> 4-> 2-> 1-> 4 로 정확히 트레일이 나왔습니다.
정확히 이해를 못한 것 같은데
설명좀 부탁드립니다. ㅠㅠ
감사합니다
10년 전