기초수학수형도#360

수형도

Trees

수형도는 연결되어 있고 회로가 없는 유한한 단순 무방향그래프다. 서로 다른 두 꼭짓점 사이의 단순경로가 정확히 하나이고, 꼭짓점이 n개이면 변은 n−1개다. 세 조건 중 둘로 판정하는 법, 차수 합으로 잎을 세는 법, 의사결정에 쓰는 법을 익힌다.

읽는 시간
약 8분
선수 개념
그래프의 뜻

직관 — 되돌아갈 고리가 없는 갈림길

직관

복도의 갈림길을 따라 이동하는데, 어떤 갈림길에서도 다른 길로 돌아서 원래 자리로 되돌아올 수 없다고 하자. 모든 방은 연결되어 있으므로 한 방에서 다른 방으로 가는 길은 존재한다. 돌아오는 고리가 없다는 조건이 그 길을 하나로 만든다.

그래프의 모든 변은 방향 없이 읽는다. 그림을 나무처럼 위아래로 배치했는지가 아니라 연결과 회로의 유무가 핵심이다. 가지 모양으로 그려도 고리가 숨어 있으면 수형도가 아니다.

수형도는 연결되어 있고 회로가 없는 그래프다

수형도는 꼭짓점이 하나 이상인 유한한 단순 무방향그래프 중 연결되어 있고 회로가 없는 것이다. 트리(tree)라고도 한다. 꼭짓점 하나와 변 0개인 경우도 수형도에 포함한다.

수형도에서는 서로 다른 두 꼭짓점 사이의 단순경로가 정확히 하나다. 단순경로는 꼭짓점을 다시 방문하지 않는 길이다. ‘있기는 하고, 둘 이상은 아니다’를 함께 뜻한다.

수형도⟺서로 다른 두 꼭짓점 사이의 단순경로가 정확히 하나.(1)\text{수형도}\quad\Longleftrightarrow\quad \text{서로 다른 두 꼭짓점 사이의 단순경로가 정확히 하나}. \tag{1}
정의
기호이름원어뜻
TT수형도tree연결되고 회로가 없는 그래프
n,mn,m꼭짓점 수, 변 수order, size수형도의 점과 연결 개수
deg⁡(v)\deg(v)꼭짓점의 차수vertex degreevv에 닿은 변 수
잎잎leaf차수가 1인 꼭짓점
뿌리뿌리root읽기의 시작으로 지정한 꼭짓점

우리교과서는 꼭짓점 수와 변 수를 v,ev,e로 쓰고, 성질을 ‘두 꼭짓점 사이에 단 하나의 경로’라고 적는다. 교과서의 경로는 변을 반복하지 않는 이동이다. 수형도에서는 그런 경로도 꼭짓점을 다시 지날 수 없어 단순경로와 같다. 같은 점을 다시 지나면 그 사이 구간이 회로가 되기 때문이다.

뿌리는 추가로 지정할 수 있는 역할이지 수형도의 정의에 반드시 들어가는 조건은 아니다. 자료구조에서 말하는 ‘트리’는 보통 뿌리를 정한 수형도다.

그림 1의 수형도는 꼭짓점 A,B,C,D,E,FA,B,C,D,E,F와 변 AB,AC,BD,BE,CFAB,AC,BD,BE,CF를 갖는다. DD에서 FF로 가는 단순경로는 D,B,A,C,FD,B,A,C,F이고, 길이는 변 4개다. D,B,E,B,A,C,FD,B,E,B,A,C,F처럼 BB를 다시 방문하는 이동은 보행일 수 있지만 단순경로는 아니다.

위는 여섯 꼭짓점과 다섯 변의 수형도이며 D에서 F로 가는 유일한 단순경로를 실선으로 강조하고 나머지 변은 점선으로 표시했다. 아래는 같은 변 목록을 A를 뿌리로 정해 다시 배치한 그림이다. D,E,F가 잎이다.
그림 1 위는 여섯 꼭짓점과 다섯 변의 수형도이며 D에서 F로 가는 유일한 단순경로를 실선으로 강조하고 나머지 변은 점선으로 표시했다. 아래는 같은 변 목록을 A를 뿌리로 정해 다시 배치한 그림이다. D,E,F가 잎이다. figures/unique_tree_paths.py

꼭짓점 하나도 수형도인가요?

그렇다. 그 점 하나로 연결 조건을 만족하고 회로가 없다. 변은 0개로 꼭짓점 수 1보다 하나 적다. 이때 차수가 0이므로 이 글의 ‘차수 1인 잎’ 정의에는 해당하지 않는다.

단순경로가 유일하다는 말은 왜 같은 조건일까?

연결되어 있으므로 두 점 사이에 단순경로가 적어도 하나 있다. 만약 서로 다른 단순경로가 두 개라면, 두 길이 처음 갈라지는 점부터 다시 만나는 첫 점까지를 따라 고리가 생긴다. 수형도에는 회로가 없으므로 이런 두 경로는 불가능하다.

반대 방향도 확인한다. 서로 다른 모든 두 점 사이에 단순경로가 하나씩 있으면 연결되어 있다. 회로가 있다고 가정하면 그 안에 단순회로를 골라, 그 위 두 점을 양쪽 방향으로 잇는 서로 다른 단순경로를 얻는다. 유일성에 모순이므로 회로가 없다. 일반 회로에서 꼭짓점이 반복되면 그 사이의 더 짧은 회로를 골라 반복하여 단순회로를 얻을 수 있다.

꼭짓점이 하나 늘면 변도 하나 늘어날까?

그렇다. 수형도의 꼭짓점 수가 nn이면 변 수는 정확히 다음과 같다.

m=n−1(n≥1).(2)m=n-1\qquad(n\ge1). \tag{2}

증명의 출발점은 ‘꼭짓점이 2개 이상인 수형도에는 잎이 적어도 2개 있다’는 사실이다. 가장 긴 단순경로를 하나 고르자. 그 끝점에서 다른 변이 나가면, 경로 밖 새 점으로 더 길게 갈 수 있거나 이미 지난 점으로 돌아오는 회로가 생긴다. 둘 다 불가능하므로 끝점의 차수는 1이다. 두 끝점 모두 같은 논리로 잎이다.

잎은 다른 두 점을 잇는 단순경로의 중간에 올 수 없다. 중간 점에는 들어오는 변과 나가는 변이 따로 필요한데, 잎의 변은 하나뿐이다. 그래서 잎과 그 변을 지워도 나머지는 여전히 연결되고 회로도 생기지 않는다. 남은 그래프도 수형도다.

그림 2는 그림 1의 수형도에서 잎을 D,E,F,B,CD,E,F,B,C 순서로 지운 것이다. D,E,FD,E,F를 지우면 B,CB,C가 새로 잎이 된다. 한 번 지울 때마다 꼭짓점과 변이 하나씩 줄어든다.

지운 횟수012345
꼭짓점 수 nn654321
변 수 mm543210

마지막에 남은 점 하나의 변 수는 0이다. 매번 둘의 차가 그대로 1이었으므로 처음에도 m=n−1m=n-1이다. 변 위 번호를 거꾸로 읽으면, 점 AA 하나에서 잎과 변을 하나씩 붙여 수형도를 키우는 순서가 된다.

그림 1의 수형도에서 잎을 하나씩 지우는 순서. 변 위의 숫자는 그 변을 잎과 함께 지우는 단계이고, 마지막까지 남는 점은 A다.
그림 2 그림 1의 수형도에서 잎을 하나씩 지우는 순서. 변 위의 숫자는 그 변을 잎과 함께 지우는 단계이고, 마지막까지 남는 점은 A다. figures/leaf_pruning.py

교과서는 같은 식을 평면그래프의 오일러 공식 n−m+f=2n-m+f=2로도 얻는다. 회로가 없으면 면은 바깥 면 하나뿐이라 f=1f=1이고, n−m+1=2n-m+1=2에서 식 (2)가 나온다.

차수 합으로 잎의 개수를 구할 수 있을까?

구할 수 있다. 차수의 합은 변 수의 두 배이고 수형도의 변은 n−1n-1개이므로 다음이 성립한다.

∑vdeg⁡(v)=2(n−1).(3)\sum_{v}\deg(v)=2(n-1). \tag{3}

차수가 3인 꼭짓점이 3개이고 나머지가 모두 잎인 수형도의 잎 수 LL을 구하자. 꼭짓점은 n=3+Ln=3+L개다. 식 (3)의 왼쪽은 차수 3인 점과 잎의 차수를 더한 값이다.

3×3+1×L=2{(3+L)−1}(4)3\times3+1\times L=2\{(3+L)-1\} \tag{4} 9+L=2L+49+L=2L+4 L=5,n=8,m=7L=5,\qquad n=8,\qquad m=7

실제로 차수 3인 세 점을 일렬로 잇고, 양 끝 점에 잎을 2개씩, 가운데 점에 잎을 1개 달면 이 수형도가 된다. 잎의 수는 점들의 배치가 아니라 차수만으로 정해진다.

변의 개수만으로 수형도를 판정할 수 있을까?

없다. 꼭짓점이 nn개인 그래프에서 ‘연결되어 있다’, ‘회로가 없다’, ‘변이 n−1n-1개다’ 가운데 두 조건이 성립하면 수형도다. 한 조건만으로는 부족하다.

그림 3의 위 왼쪽은 세 조건을 모두 만족한다. 위 오른쪽은 연결되었지만 변이 5개이고 회로 Q,S,T,QQ,S,T,Q가 있다. 아래 왼쪽은 회로가 없지만 두 덩어리로 떨어져 변이 3개다. 아래 오른쪽은 변이 5−1=45-1=4개인데 연결되지 않고 회로 P,Q,S,PP,Q,S,P도 있다.

꼭짓점이 5개인 네 그래프. 위 왼쪽만 연결·회로 없음·변 4개를 모두 만족하는 수형도이고, 나머지는 셋 중 하나씩만 만족한다. 회로 위의 변은 경고색으로 표시했다.
그림 3 꼭짓점이 5개인 네 그래프. 위 왼쪽만 연결·회로 없음·변 4개를 모두 만족하는 수형도이고, 나머지는 셋 중 하나씩만 만족한다. 회로 위의 변은 경고색으로 표시했다. figures/tree_tests.py

연결과 식 (2)가 성립하면 회로가 없다. 회로가 있다면 회로 위 변 하나를 지워도 연결이 남는다. 회로가 사라질 때까지 지우면 수형도가 남아 변이 n−1n-1개인데, 이미 하나 이상 지웠으니 처음 변은 nn개 이상이어야 한다. 모순이다.

회로가 없고 식 (2)가 성립하면 연결이다. 떨어진 덩어리가 cc개라면 각 덩어리가 수형도이므로 변은 모두 n−cn-c개다. n−c=n−1n-c=n-1에서 c=1c=1이다.

교과서가 생각 열기로 쓰는 알케인 CkH2k+2\mathrm{C}_k\mathrm{H}_{2k+2}가 이 판정의 예다. 원자를 꼭짓점, 결합을 변으로 두면 탄소의 차수는 4, 수소의 차수는 1이다. 꼭짓점은 k+(2k+2)=3k+2k+(2k+2)=3k+2개, 차수 합은 6k+26k+2이므로 변은 3k+13k+1개다. 하나로 연결된 분자에 변이 꼭짓점보다 하나 적으니 알케인의 그래프는 수형도다.

프로페인 C3H8\mathrm{C}_3\mathrm{H}_8은 꼭짓점 11개, 변 10개다. 반면 사이클로헥세인 C6H12\mathrm{C}_6\mathrm{H}_{12}는 꼭짓점 18개, 차수 합 36, 변 18개다. 연결되어 있는데 변이 n−1n-1보다 많으므로 회로, 곧 탄소 고리가 있다. 연결그래프에서 변을 n−1n-1개만 남겨 모든 점을 잇는 방법은 생성수형도에서 다룬다.

뿌리를 정하면 의사결정을 어떻게 읽을까?

한 꼭짓점을 뿌리로 정하면 수형도는 선택을 차례로 펼친 그림이 된다. 뿌리에서 각 잎까지 단순경로가 하나뿐이므로 잎 하나가 선택의 순서 하나와 정확히 대응한다.

그림 4는 출발 SS에서 이동 방법 A,B,CA,B,C 중 하나를 고르고, 이어서 두 갈래 중 하나를 고르는 가상 계획이다. 변 위 숫자는 걸리는 시간(분)이다. 잎까지 경로가 하나라서 잎마다 총시간이 하나로 정해진다.

잎DDEEFFGGHHII
경로S,A,DS,A,DS,A,ES,A,ES,B,FS,B,FS,B,GS,B,GS,C,HS,C,HS,C,IS,C,I
총시간(분)10+20=3010+20=3010+25=3510+25=3515+10=2515+10=2515+12=2715+12=275+30=355+30=355+22=275+22=27

가장 짧은 것은 FF의 25분이다. 첫 갈림길에서 가장 짧은 가지 CC(5분)를 고르면 그 아래 최선이 27분이라, 한 단계만 보고 고르면 놓친다. 잎을 모두 비교해야 하는 이유다. 그림 4도 꼭짓점 10개, 변 9개로 식 (2)를 만족한다.

출발 S에서 두 번 선택하는 가상 이동 계획의 수형도. 변 위 숫자는 걸리는 분, 잎 아래 숫자는 뿌리에서 그 잎까지의 총시간이며 가장 짧은 S, B, F의 25분을 강조했다.
그림 4 출발 S에서 두 번 선택하는 가상 이동 계획의 수형도. 변 위 숫자는 걸리는 분, 잎 아래 숫자는 뿌리에서 그 잎까지의 총시간이며 가장 짧은 S, B, F의 25분을 강조했다. figures/decision_tree.py

그림 1 아래처럼 AA를 뿌리로 놓아도 변 목록은 그림 1 위와 같다. 뿌리의 위치를 바꾸어도 변 목록·회로의 부재·수형도 여부는 바뀌지 않는다. 서로 다른 선택이 같은 상태로 합쳐지는 절차는 회로가 생길 수 있어, 모든 절차도를 무조건 수형도라고 부르지는 않는다. 확률을 붙이지 않은 가지 그림만으로 각 결과의 가능성이 같다고 말할 수도 없다.

경우의 수의 수형도도 그래프의 수형도인가요?

그렇다. 결과마다 다른 꼭짓점으로 그리면 출발점을 뿌리로 정한 수형도다. 상의 3개와 하의 2개를 고르는 곱의 법칙의 수형도는 꼭짓점 1+3+6=101+3+6=10개, 변 9개이고, 잎 6개가 차림 6가지다. 같은 하의 이름이 여러 가지 끝에 나와도 서로 다른 꼭짓점으로 센다.

수형도에 변을 더하거나 빼면 어떻게 될까?

수형도는 모든 점을 잇는 데 꼭 필요한 변만 가진 그래프다. 변을 하나 빼면 연결이 끊어지고, 하나 더하면 회로가 생긴다. 이 두 성질이 다음 글에서 생성수형도를 고르는 기준이 된다.

수형도에서 변 하나를 지우면 어떻게 되나요?

수형도에서 변 하나를 지우면 연결이 끊어진다. 두 끝점을 잇던 유일한 단순경로가 사라지기 때문이다. 그림 1에서 BEBE를 지우면 EE가 떨어져 꼭짓점 6개에 변 4개가 남는다.

수형도에 없는 변 하나를 추가하면 어떻게 되나요?

수형도에 변 하나를 더하면 단순회로가 정확히 하나 생긴다. 새 변과 두 끝점 사이의 원래 단순경로가 합쳐지기 때문이다. 그림 1에 DFDF를 더하면 길이 5인 회로 D,B,A,C,F,DD,B,A,C,F,D가 생긴다.

핵심

수형도는 연결되어 있고 회로가 없는 단순 무방향그래프다. 두 점 사이 단순경로가 정확히 하나이고 꼭짓점 n개에 변 n−1개지만, 변 수 하나만으로는 판정할 수 없다.

수형도의 흔한 오해

  • 변이 꼭짓점보다 하나 적거나 회로가 없으면 수형도다. — 그림 3 아래 오른쪽은 변이 4개라도 끊겨 있고 회로가 있으며, 아래 왼쪽은 회로가 없어도 두 덩어리다. 세 조건 중 둘이 필요하다.
  • 그림에서 제일 위의 점이 바뀌면 다른 수형도다. — 그림 1처럼 배치나 뿌리 선택을 바꾸어도 연결 목록은 유지할 수 있다.

직접 해보기

  1. 꼭짓점이 9개인 수형도의 변 수와 차수 합을 구하시오.
  2. 변 PQ,QR,RS,QTPQ,QR,RS,QT를 가진 그래프에서 PP에서 SS로 가는 단순경로와 모든 잎을 구하시오. 여기에 변 PSPS를 추가하면 생기는 단순회로도 쓰시오.
  3. 삼각형 PQRPQR과 그와 떨어진 경로 S−T−US-T-U의 꼭짓점·변 수를 구하고, 수형도 여부를 세 조건으로 판단하시오.
  4. 차수가 4인 꼭짓점 1개, 차수가 3인 꼭짓점 2개가 있고 나머지는 모두 잎인 수형도의 잎 수, 꼭짓점 수, 변 수를 구하시오.
  5. 꼭짓점이 a,b,c,da,b,c,d인 수형도 중 잎이 정확히 3개인 것과 정확히 2개인 것은 각각 몇 개인가?
답과 풀이
  1. 변은 9−1=89-1=8개다. 차수 합 정리에 따라 합은 2×8=162\times8=16이다.
  2. P,Q,R,SP,Q,R,S가 길이 3의 유일한 단순경로다. 차수는 P,Q,R,S,TP,Q,R,S,T 순서로 1,3,2,1,11,3,2,1,1이므로 잎은 P,S,TP,S,T다. PSPS를 더하면 원래 단순경로와 새 변이 합쳐져 P,Q,R,S,PP,Q,R,S,P가 생긴다.
  3. 꼭짓점은 6개, 변은 3+2=53+2=5개라 m=n−1m=n-1만 만족한다. 두 부분이 연결되지 않고 삼각형 회로도 있으므로 수형도가 아니다. 그림 3 아래 오른쪽과 같은 경우다.
  4. 잎을 LL개라 하면 n=3+Ln=3+L이다. 식 (3)에서 4+3+3+L=2{(3+L)−1}4+3+3+L=2\{(3+L)-1\}, 곧 10+L=2L+410+L=2L+4이므로 L=6L=6이다. 꼭짓점은 9개, 변은 8개다. 차수 4인 점에 차수 3인 두 점과 잎 2개를 달고, 차수 3인 두 점에 잎을 2개씩 달면 실제로 만들어진다.
  5. 잎이 3개면 나머지 한 점이 다른 세 점과 모두 이어진 별 모양이다. 가운데 점을 고르는 방법이 4가지다. 잎이 2개면 네 점이 일렬로 놓인 모양이다. 일렬 순서 4!=244!=24가지 중 뒤집은 것이 같은 수형도라 24÷2=1224\div2=12개다. 합한 16개가 네 점의 모든 수형도다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-06]의 수형도와 의사결정.
  • 우리교과서 이산 수학 공개본 — 인쇄 150~151쪽의 수형도 정의, 알케인 생각 열기, 성질 e=v−1e=v-1과 ‘단 하나의 경로’·‘잎 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분 고르기

지도에서의 위치

완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 식 (1)의 ‘정확히 하나’ 명확화, 세 조건 판정·차수 합으로 잎 세기·알케인·의사결정 예제와 해보기 보강 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림