직관 — 되돌아갈 고리가 없는 갈림길
복도의 갈림길을 따라 이동하는데, 어떤 갈림길에서도 다른 길로 돌아서 원래 자리로 되돌아올 수 없다고 하자. 모든 방은 연결되어 있으므로 한 방에서 다른 방으로 가는 길은 존재한다. 돌아오는 고리가 없다는 조건이 그 길을 하나로 만든다.
그래프의 모든 변은 방향 없이 읽는다. 그림을 나무처럼 위아래로 배치했는지가 아니라 연결과 회로의 유무가 핵심이다. 가지 모양으로 그려도 고리가 숨어 있으면 수형도가 아니다.
수형도는 연결되어 있고 회로가 없는 그래프다
수형도는 꼭짓점이 하나 이상인 유한한 단순 무방향그래프 중 연결되어 있고 회로가 없는 것이다. 트리(tree)라고도 한다. 꼭짓점 하나와 변 0개인 경우도 수형도에 포함한다.
수형도에서는 서로 다른 두 꼭짓점 사이의 단순경로가 정확히 하나다. 단순경로는 꼭짓점을 다시 방문하지 않는 길이다. ‘있기는 하고, 둘 이상은 아니다’를 함께 뜻한다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 수형도 | tree | 연결되고 회로가 없는 그래프 | |
| 꼭짓점 수, 변 수 | order, size | 수형도의 점과 연결 개수 | |
| 꼭짓점의 차수 | vertex degree | 에 닿은 변 수 | |
| 잎 | 잎 | leaf | 차수가 1인 꼭짓점 |
| 뿌리 | 뿌리 | root | 읽기의 시작으로 지정한 꼭짓점 |
우리교과서는 꼭짓점 수와 변 수를 로 쓰고, 성질을 ‘두 꼭짓점 사이에 단 하나의 경로’라고 적는다. 교과서의 경로는 변을 반복하지 않는 이동이다. 수형도에서는 그런 경로도 꼭짓점을 다시 지날 수 없어 단순경로와 같다. 같은 점을 다시 지나면 그 사이 구간이 회로가 되기 때문이다.
뿌리는 추가로 지정할 수 있는 역할이지 수형도의 정의에 반드시 들어가는 조건은 아니다. 자료구조에서 말하는 ‘트리’는 보통 뿌리를 정한 수형도다.
그림 1의 수형도는 꼭짓점 와 변 를 갖는다. 에서 로 가는 단순경로는 이고, 길이는 변 4개다. 처럼 를 다시 방문하는 이동은 보행일 수 있지만 단순경로는 아니다.
figures/unique_tree_paths.py꼭짓점 하나도 수형도인가요?
그렇다. 그 점 하나로 연결 조건을 만족하고 회로가 없다. 변은 0개로 꼭짓점 수 1보다 하나 적다. 이때 차수가 0이므로 이 글의 ‘차수 1인 잎’ 정의에는 해당하지 않는다.
단순경로가 유일하다는 말은 왜 같은 조건일까?
연결되어 있으므로 두 점 사이에 단순경로가 적어도 하나 있다. 만약 서로 다른 단순경로가 두 개라면, 두 길이 처음 갈라지는 점부터 다시 만나는 첫 점까지를 따라 고리가 생긴다. 수형도에는 회로가 없으므로 이런 두 경로는 불가능하다.
반대 방향도 확인한다. 서로 다른 모든 두 점 사이에 단순경로가 하나씩 있으면 연결되어 있다. 회로가 있다고 가정하면 그 안에 단순회로를 골라, 그 위 두 점을 양쪽 방향으로 잇는 서로 다른 단순경로를 얻는다. 유일성에 모순이므로 회로가 없다. 일반 회로에서 꼭짓점이 반복되면 그 사이의 더 짧은 회로를 골라 반복하여 단순회로를 얻을 수 있다.
꼭짓점이 하나 늘면 변도 하나 늘어날까?
그렇다. 수형도의 꼭짓점 수가 이면 변 수는 정확히 다음과 같다.
증명의 출발점은 ‘꼭짓점이 2개 이상인 수형도에는 잎이 적어도 2개 있다’는 사실이다. 가장 긴 단순경로를 하나 고르자. 그 끝점에서 다른 변이 나가면, 경로 밖 새 점으로 더 길게 갈 수 있거나 이미 지난 점으로 돌아오는 회로가 생긴다. 둘 다 불가능하므로 끝점의 차수는 1이다. 두 끝점 모두 같은 논리로 잎이다.
잎은 다른 두 점을 잇는 단순경로의 중간에 올 수 없다. 중간 점에는 들어오는 변과 나가는 변이 따로 필요한데, 잎의 변은 하나뿐이다. 그래서 잎과 그 변을 지워도 나머지는 여전히 연결되고 회로도 생기지 않는다. 남은 그래프도 수형도다.
그림 2는 그림 1의 수형도에서 잎을 순서로 지운 것이다. 를 지우면 가 새로 잎이 된다. 한 번 지울 때마다 꼭짓점과 변이 하나씩 줄어든다.
| 지운 횟수 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 꼭짓점 수 | 6 | 5 | 4 | 3 | 2 | 1 |
| 변 수 | 5 | 4 | 3 | 2 | 1 | 0 |
마지막에 남은 점 하나의 변 수는 0이다. 매번 둘의 차가 그대로 1이었으므로 처음에도 이다. 변 위 번호를 거꾸로 읽으면, 점 하나에서 잎과 변을 하나씩 붙여 수형도를 키우는 순서가 된다.
figures/leaf_pruning.py교과서는 같은 식을 평면그래프의 오일러 공식 로도 얻는다. 회로가 없으면 면은 바깥 면 하나뿐이라 이고, 에서 식 (2)가 나온다.
차수 합으로 잎의 개수를 구할 수 있을까?
구할 수 있다. 차수의 합은 변 수의 두 배이고 수형도의 변은 개이므로 다음이 성립한다.
차수가 3인 꼭짓점이 3개이고 나머지가 모두 잎인 수형도의 잎 수 을 구하자. 꼭짓점은 개다. 식 (3)의 왼쪽은 차수 3인 점과 잎의 차수를 더한 값이다.
실제로 차수 3인 세 점을 일렬로 잇고, 양 끝 점에 잎을 2개씩, 가운데 점에 잎을 1개 달면 이 수형도가 된다. 잎의 수는 점들의 배치가 아니라 차수만으로 정해진다.
변의 개수만으로 수형도를 판정할 수 있을까?
없다. 꼭짓점이 개인 그래프에서 ‘연결되어 있다’, ‘회로가 없다’, ‘변이 개다’ 가운데 두 조건이 성립하면 수형도다. 한 조건만으로는 부족하다.
그림 3의 위 왼쪽은 세 조건을 모두 만족한다. 위 오른쪽은 연결되었지만 변이 5개이고 회로 가 있다. 아래 왼쪽은 회로가 없지만 두 덩어리로 떨어져 변이 3개다. 아래 오른쪽은 변이 개인데 연결되지 않고 회로 도 있다.
figures/tree_tests.py연결과 식 (2)가 성립하면 회로가 없다. 회로가 있다면 회로 위 변 하나를 지워도 연결이 남는다. 회로가 사라질 때까지 지우면 수형도가 남아 변이 개인데, 이미 하나 이상 지웠으니 처음 변은 개 이상이어야 한다. 모순이다.
회로가 없고 식 (2)가 성립하면 연결이다. 떨어진 덩어리가 개라면 각 덩어리가 수형도이므로 변은 모두 개다. 에서 이다.
교과서가 생각 열기로 쓰는 알케인 가 이 판정의 예다. 원자를 꼭짓점, 결합을 변으로 두면 탄소의 차수는 4, 수소의 차수는 1이다. 꼭짓점은 개, 차수 합은 이므로 변은 개다. 하나로 연결된 분자에 변이 꼭짓점보다 하나 적으니 알케인의 그래프는 수형도다.
프로페인 은 꼭짓점 11개, 변 10개다. 반면 사이클로헥세인 는 꼭짓점 18개, 차수 합 36, 변 18개다. 연결되어 있는데 변이 보다 많으므로 회로, 곧 탄소 고리가 있다. 연결그래프에서 변을 개만 남겨 모든 점을 잇는 방법은 생성수형도에서 다룬다.
뿌리를 정하면 의사결정을 어떻게 읽을까?
한 꼭짓점을 뿌리로 정하면 수형도는 선택을 차례로 펼친 그림이 된다. 뿌리에서 각 잎까지 단순경로가 하나뿐이므로 잎 하나가 선택의 순서 하나와 정확히 대응한다.
그림 4는 출발 에서 이동 방법 중 하나를 고르고, 이어서 두 갈래 중 하나를 고르는 가상 계획이다. 변 위 숫자는 걸리는 시간(분)이다. 잎까지 경로가 하나라서 잎마다 총시간이 하나로 정해진다.
| 잎 | ||||||
|---|---|---|---|---|---|---|
| 경로 | ||||||
| 총시간(분) |
가장 짧은 것은 의 25분이다. 첫 갈림길에서 가장 짧은 가지 (5분)를 고르면 그 아래 최선이 27분이라, 한 단계만 보고 고르면 놓친다. 잎을 모두 비교해야 하는 이유다. 그림 4도 꼭짓점 10개, 변 9개로 식 (2)를 만족한다.
figures/decision_tree.py그림 1 아래처럼 를 뿌리로 놓아도 변 목록은 그림 1 위와 같다. 뿌리의 위치를 바꾸어도 변 목록·회로의 부재·수형도 여부는 바뀌지 않는다. 서로 다른 선택이 같은 상태로 합쳐지는 절차는 회로가 생길 수 있어, 모든 절차도를 무조건 수형도라고 부르지는 않는다. 확률을 붙이지 않은 가지 그림만으로 각 결과의 가능성이 같다고 말할 수도 없다.
경우의 수의 수형도도 그래프의 수형도인가요?
그렇다. 결과마다 다른 꼭짓점으로 그리면 출발점을 뿌리로 정한 수형도다. 상의 3개와 하의 2개를 고르는 곱의 법칙의 수형도는 꼭짓점 개, 변 9개이고, 잎 6개가 차림 6가지다. 같은 하의 이름이 여러 가지 끝에 나와도 서로 다른 꼭짓점으로 센다.
수형도에 변을 더하거나 빼면 어떻게 될까?
수형도는 모든 점을 잇는 데 꼭 필요한 변만 가진 그래프다. 변을 하나 빼면 연결이 끊어지고, 하나 더하면 회로가 생긴다. 이 두 성질이 다음 글에서 생성수형도를 고르는 기준이 된다.
수형도에서 변 하나를 지우면 어떻게 되나요?
수형도에서 변 하나를 지우면 연결이 끊어진다. 두 끝점을 잇던 유일한 단순경로가 사라지기 때문이다. 그림 1에서 를 지우면 가 떨어져 꼭짓점 6개에 변 4개가 남는다.
수형도에 없는 변 하나를 추가하면 어떻게 되나요?
수형도에 변 하나를 더하면 단순회로가 정확히 하나 생긴다. 새 변과 두 끝점 사이의 원래 단순경로가 합쳐지기 때문이다. 그림 1에 를 더하면 길이 5인 회로 가 생긴다.
수형도는 연결되어 있고 회로가 없는 단순 무방향그래프다. 두 점 사이 단순경로가 정확히 하나이고 꼭짓점 n개에 변 n−1개지만, 변 수 하나만으로는 판정할 수 없다.
수형도의 흔한 오해
- 변이 꼭짓점보다 하나 적거나 회로가 없으면 수형도다. — 그림 3 아래 오른쪽은 변이 4개라도 끊겨 있고 회로가 있으며, 아래 왼쪽은 회로가 없어도 두 덩어리다. 세 조건 중 둘이 필요하다.
- 그림에서 제일 위의 점이 바뀌면 다른 수형도다. — 그림 1처럼 배치나 뿌리 선택을 바꾸어도 연결 목록은 유지할 수 있다.
직접 해보기
- 꼭짓점이 9개인 수형도의 변 수와 차수 합을 구하시오.
- 변 를 가진 그래프에서 에서 로 가는 단순경로와 모든 잎을 구하시오. 여기에 변 를 추가하면 생기는 단순회로도 쓰시오.
- 삼각형 과 그와 떨어진 경로 의 꼭짓점·변 수를 구하고, 수형도 여부를 세 조건으로 판단하시오.
- 차수가 4인 꼭짓점 1개, 차수가 3인 꼭짓점 2개가 있고 나머지는 모두 잎인 수형도의 잎 수, 꼭짓점 수, 변 수를 구하시오.
- 꼭짓점이 인 수형도 중 잎이 정확히 3개인 것과 정확히 2개인 것은 각각 몇 개인가?
답과 풀이
- 변은 개다. 차수 합 정리에 따라 합은 이다.
- 가 길이 3의 유일한 단순경로다. 차수는 순서로 이므로 잎은 다. 를 더하면 원래 단순경로와 새 변이 합쳐져 가 생긴다.
- 꼭짓점은 6개, 변은 개라 만 만족한다. 두 부분이 연결되지 않고 삼각형 회로도 있으므로 수형도가 아니다. 그림 3 아래 오른쪽과 같은 경우다.
- 잎을 개라 하면 이다. 식 (3)에서 , 곧 이므로 이다. 꼭짓점은 9개, 변은 8개다. 차수 4인 점에 차수 3인 두 점과 잎 2개를 달고, 차수 3인 두 점에 잎을 2개씩 달면 실제로 만들어진다.
- 잎이 3개면 나머지 한 점이 다른 세 점과 모두 이어진 별 모양이다. 가운데 점을 고르는 방법이 4가지다. 잎이 2개면 네 점이 일렬로 놓인 모양이다. 일렬 순서 가지 중 뒤집은 것이 같은 수형도라 개다. 합한 16개가 네 점의 모든 수형도다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-06]의 수형도와 의사결정.
- 우리교과서 이산 수학 공개본 — 인쇄 150~151쪽의 수형도 정의, 알케인 생각 열기, 성질 과 ‘단 하나의 경로’·‘잎 2개 이상’을 대조했다. 본문의 예와 연습은 별도로 구성했다.
- Levin, Trees — 명제 4.2.1·4.2.3·4.2.4의 유일한 경로·잎 2개·변 수 논증을 대조했다. 영어 path를 이 글에서는 단순경로로 구별한다.
영상 노트
- 00:00 갈림길과 되돌아오는 고리 구별하기
- 00:40 그림 1에서 두 배치의 변 목록과 유일한 단순경로 비교하기
- 01:30 식 (1)의 양방향 이유와 그림 2의 잎 지우기로 식 (2) 설명하기
- 02:30 식 (3)·(4)로 차수 3인 점이 셋일 때 잎 5개 구하기
- 03:20 그림 3의 네 그래프로 세 조건 중 둘이 필요한 이유, 알케인과 사이클로헥세인 비교
- 04:30 그림 4의 이동 계획에서 잎마다 총시간을 구하고 25분 고르기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 식 (1)의 ‘정확히 하나’ 명확화, 세 조건 판정·차수 합으로 잎 세기·알케인·의사결정 예제와 해보기 보강 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림