현상금 이 달린 문제 |
|||||
|---|---|---|---|---|---|
| 작성자 | 최병성 | 등록일 | 09.09.23 | 조회수 | 63 |
|
20.우아한 트리 유한 개의 점과, 그 점들을 잇는 선들로 이루어진 도형을 "그래프(graph)"라고 합니다. 이 때, 이 그래프의 점을 "버텍스(vertex)"라고 하고, 버텍스들을 잇는 선을 "에지(edge)"라고 합니다. 그래프 가운데, 한 버텍스에서 다른 버텍스로 에지를 따라 가는 방법이 유일할 때, 이런 그래프를 특별히 "트리(tree)"라고 합니다. 전산이나 컴퓨터 프로그래밍을 공부한 분이라면 "트리 구조"라는 걸 아실 겁니다. n 개의 버텍스를 갖는 트리에, 1부터 n까지 숫자를 준 다음, 각 에지에는 양 끝의 두 버텍스에 주어진 숫자들의 차를 줍니다. 이렇게 했을 때, 만약 에지의 숫자들이 모두 다르다면, 이 트리는 "우아하다(graceful)"고 정의합니다. 예를 들어, 9 개의 버텍스를 가진 트리에 다음 그림처럼 숫자를 줍니다. 5 1----4 / / 7----3----9----2 \ \ 6 8 이 트리의 에지는 1부터 8까지의 서로 다른 숫자를 갖습니다. 따라서, 이 트리는 우아한 트리(graceful tree)입니다. 그런데, 혹시 모든 트리는 다 우아하지 않을까요? 아직 아무도 증명이나 반증을 하지 못했습니다. 21.마법의 나이트 경로 8x8 체스판 위에서 나이트(knight)가 어떤 칸도 꼭 한 번만 방문하도록 움직이면서, 방문하는 칸마다 1부터 64까지 차례대로 번호를 붙입니다. 이 때, 그 결과가 마방진이 되게 할 수 있을까요? |
|||||
| 이전글 | 이것은 무엇일까? |
|---|---|
| 다음글 | 현상금 이 달린 문제 (3) |