https://arca.live/b/math/22485561
어떤 국가에 50000개의 도시가 있다. 이 국가는 산업화 이전에 이 도시들 사이에 임의로 도로를 놓아서, 그 어떤 두 도시를 고르더라도 서로 간의 이동이 가능하게 하였다. (단, 그 어떤 두 도시 사이에도 도로를 두 개 이상 놓지 않았다.) 그러나 아스팔트로 도로를 포장하는 기술이 발명된 현재, 국가는 이미 놓아진 도로 중 몇 개를 포장도로로 바꾸려고 한다.
(1) 모든 도시에 홀수개의 포장도로가 연결되도록 할 수 있는가?(단, 포장도로가 연결되지 않은 것은 0개로서, 짝수개로 간주한다.)
(2) (1)의 답을 증명하여라.
==========================================================================
직접 올려주신 답( https://arca.live/b/math/22494415 )은 수학과의 느낌이 강하군요. 제 해답은 컴퓨터과학 느낌이 좀 더 강하지 않을까 합니다. ㅎ
5000개의 vertex 로 이루어진 그래프가 연결되어 있으므로 Depth-First Search 를 이용해서 (BFS 라도 상관은 없습니다) 모든 vertex를 포함하면서 원래 그래프의 부분집합인 Tree를 구성할 수 있습니다.
이제 Tree의 Leaf node 와 연결된 모든 edge 들을 선택합니다. 그러면 Leaf node 는 모두 한 개의 edge 와 연결됩니다.
이 Tree 는 다음의 세 조건을 만족합니다.
- 모든 Leaf node는 parent node 와 연결된 edge 가 선택되어 있습니다.
- 모든 Leaf node는 (Tree에 포함되는 edge와 포함되지 않는 edge를 통틀어서) 연결된 edge 중 홀수개의 edge 가 선택되어 있습니다.
- Tree 의 node 숫자는 짝수입니다.
이제 다음과 같은 과정을 통해서, 이 Tree 가 위의 세 조건을 만족하는 상태를 유지하면서 이 Tree 에서 짝수개씩의 node를 제거해나갑니다.
Node 제거 과정은 다음과 같습니다. 모든 children이 Leaf node 인 node (그림에서는 2개 있습니다) 중에서 그 children의 숫자가 홀수개인 경우에는 그 parent node 와 연결되는 edge 를 선택하지 않고 해당 node와 그 children 을 모두 그래프에서 제거합니다.
Children 숫자가 짝수개인 경우에는 그 parent node 와 연결되는 edge 를 선택하고, 해당 node는 그래프에 남기고 children 만을 제거합니다.
이 과정을 거치면 Leaf로 변하거나 제거된 node에 연결된 edge 중 홀수개의 edge 가 선택된 상태가 되며, 제거되는 node 숫자는 항상 짝수이므로 전체 Tree 의 node 숫자도 짝수입니다.
Tree 에는 항상 Leaf node 들이 존재하므로, 이 과정을 거치면 모든 node를 Tree에서 제거할 수 있으며, 이렇게 제거된 node들은 모두 홀수개의 '선택된' edge와 연결되어 있게 됩니다.
