6개의 댓글이 있습니다.
-
-
JongMan -
에.. 답변이 늦어서 죄송합니다. 제가 책에 썼을 때 의도한 것은 실제로 변환을 해서 문제를 풀라는 것이 아니라, 그렇게 문제를 변형했다고 생각만 한다는 뜻이었습니다. ^^; 이것은 오일러 트레일의 존재 여부가 오일러 서킷의 존재 여부와 밀접하게 관련되어 있다는 것을 나타내기 위한 도구일 뿐, 실제로 오일러 트레일을 찾을 때 간선을 추가하고, 나중에 찾아진 서킷을 끊는 번거로운 일을 할 필요는 없습니다.
(B,A)를 연결헀을 때 오일러 서킷이 존재한다고 하지요. 그러면 이것은 하나의 거대한 사이클이 됩니다. 이것을 (B,A)에서 끊으면 트레일이 되겠죠. 따라서 이 간선을 추가했을 때 서킷이 존재한다면 트레일도 반드시 존재하죠.
반대로 A에서 시작하고 B에서 끝나는 오일러 트레일이 존재한다면, 이 추가된 그래프에서는 반드시 서킷이 존재하겠죠?
따라서 두 간선을 이은 가상의 그래프에서 서킷의 존재 여부는 원래 그래프에서 트레일의 존재 여부와 동치가 됩니다. 이것을 말하고 싶었던 것이지요.
어떤 서킷이 찾아지느냐에 따라 실제 트레일을 찾을 수 없다고 생각하실 수도 있는데, 서킷은 사이클이기 때문에 시작점 끝점이 없습니다. 따라서 찾으신
A - B - E - F - B - A - C - D - A
이 서킷은 사실 다음 서킷과 같은 서킷이지요.
A - C - D - A - B - E - F - B - A
이것은 끊어도 되겠죠? ^^; 이 방법으로 실제 구현하고 싶다면 해당 간선이 처음이나 끝에 가도록 서킷을 회전해야겠습니다만, 실제로는 그럴 필요가 없습니다. 존재성을 증명하기 위해 사용한 일종의 트릭일 뿐이니까요.
실제로 트레일 또는 서킷을 찾는 코드 28.6의 경우 서킷이건 트레일이건 간에 그냥 서킷을 찾는 코드를 사용함을 알 수 있지요. 트레일의 경우에도 이 코드가 왜 잘 동작하는지 한번 생각해 보세요.
제가 밤 늦은 중에 써서 정신이 없는데, 이해 안 가시는 부분 있으면 추가 질문 주세요.
10년 전 link
-
-
-
mihaly -
JongMan//
답변 감사합니다.
사이클에서 시작점과 끝점이 정해져있지 않다는 사실을 간과했었네요.
어떤 말씀이신지 알 것 같습니다.
결국 가상의 그래프에서 서킷이 존재한다는 것은 실제 그래프에서 트레일이 있다는 것이고 실제 그래프에서 트레일이 있다는 것은 가상의 서킷이 있다는 것이므로 가상 그래프의 서킷의 존재여부와 실제 그래프에서 트레일의 존재여부가 동치라는 말이군요.위 사실이 서킷과 트레일을 찾는 알고리즘이 같다는 것을 뒷받침하는지는 모르겠으나 왜 같은 알고리즘으로 찾을 수 있는지에 대해서는 조금 더 생각해보도록 하겠습니다.
감사합니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
mihaly
JMBook에 보면 오일러 트레일을 구하는 방식에서 오일러 서킷을 구하는 방법을 이용하죠.
정점A에서 정점B로 끝이 나는 오일러 트레일을 구할 때 (B, A) 간선을 임의로 추가하여 정점A에서 오일러 서킷을 만들고 (B, A)로 인한 경로를 삭제한다고 되어있습니다.
이 때 만약 A와 B가 이미 연결되어있어도 하나 더 추가를 해주나요?
그리고 오일러 서킷에서 추가된 간선으로 인한 경로를 삭제한다고 하셨는데 이것이 왜 타당한지 이해가 가지 않습니다.
어떻게 간선을 추가해서 오일러 서킷을 만들었다고 하면 그 서킷은
A - ... - A 가 될 것입니다. 서킷이기 때문이죠.
여기서 특정 경로를 삭제해야한다면 마지막이어야 할 것입니다. 경로 삭제 후에는 마지막이 B가 되어야하니까요.
그렇다면
A - ... - B - A 였다고 생각할 수 있겠네요.
근데 궁금한 것은 항상 B - A을 마지막으로 하는 서킷이 구해질까라는 것입니다.
예를 들어 다음과 같은 그래프를 생각해봅시다.
A->B
A->C
C->D
D->A
B->E
E->F
F->B
이 때 (B, A) 간선을 추가해서 오일러 서킷을 만들어보면
A - C - D - A - B - E - F - B - A
인데 (B, A) 간선 때문에 생긴 경로는 B - A이고 이를 삭제하면
A - C - D - A - B - E - F - B
가 되고 이는 제대로 된 A에서 B로의 오일러 트레일이 됩니다.
근데 오일러 서킷이 다음과 같이 나왔다고 해보죠.
A - B - E - F - B - A - C - D - A
이것도 (B, A)가 추가되고 나서는 타당한 오일러 서킷입니다.
그리고 (B, A) 때문에 생긴 경로는 B - A 이고 이를 서킷에서 삭제하면
A - B - E - F - B - C - D - A지만,
이는 원래 그래프에서는 절대 만들어질 수 없는 트레일이죠.
왜냐하면 이 서킷은 B - A로 끝나지 않았기 때문입니다.
그렇다면 제 생각에는 책에 있는 방법대로 오일러 트레일이 구해지려면
오일러 서킷이 B - A가 마지막에 되도록 구해져야하는데 이것이 맞는 방법인가요?
아니면 책에서 말하는 오일러 서킷을 구하는 알고리즘을 사용하면 무조건 B - A로 끝나면 서킷만 만드는 건가요?
만약 그렇다면 그 부분도 이해가 잘 안 됩니다. 왜 B - A 로 끝나는 것만 찾을 수 있나요?
혹시 여기까지 제 생각이 잘못되었거나 지적받을 곳이 있다면 말씀하시고 고쳐주세요. 제가 이해력이 많이 좋지 않습니다.
감사합니다.
p.s. JMBook 정말 잘 보고 있어요. 어렵네요.
10년 전