기초수학생성수형도#361

생성수형도

Spanning Trees

생성수형도는 원래 그래프의 모든 꼭짓점을 포함하는 수형도인 부분그래프다. 연결그래프에서만 만들 수 있으며, 회로를 끊는 방법으로 개수를 세고 변의 비용 합이 가장 작은 최소 생성수형도를 크루스칼·프림 알고리즘으로 구한다.

읽는 시간
약 8분
선수 개념
수형도

직관 — 필요한 연결만 남긴다

직관

여러 건물에 통신선을 연결한다고 하자. 어느 두 건물 사이든 다른 건물을 거쳐 통신할 수 있으면 되고, 같은 곳을 도는 고리는 필수가 아니다. 가능한 선 중 일부만 골라 모두 연결한 뒤, 선마다 비용이 다르면 총비용도 비교한다.

건물과 가능한 연결을 나타낸 유한한 단순 무방향그래프를 사용한다. 실제 공사 비용이 아니라 각 변에 제시한 가상 비용만 더하는 모형이다. 한 출발점에서 각 건물까지 가장 가까운 길을 찾는 문제와도 구별한다.

생성수형도는 모든 꼭짓점을 남긴 수형도다

생성수형도는 원래 그래프의 모든 꼭짓점과 일부 변으로 이루어진 수형도다. 신장 트리(spanning tree) 또는 스패닝 트리라고도 한다. 변을 고를 때 원래 없던 변을 새로 넣을 수 없다.

V(T)=V(G),E(T)⊆E(G),T는 수형도.(1)V(T)=V(G),\qquad E(T)\subseteq E(G),\qquad T\text{는 수형도}. \tag{1}
정의
기호이름원어뜻
GG원래 그래프graph사용 가능한 연결 전체
TT생성수형도spanning tree모든 꼭짓점을 잇는 수형도
V(G),E(G)V(G),E(G)꼭짓점·변 집합vertex set, edge set그래프의 대상과 연결 목록
w(e)w(e)변의 가중치edge weight변 ee에 붙인 비용
W(T)W(T)총가중치total weight고른 변의 가중치 합
nn꼭짓점 수number of vertices반드시 포함할 대상 수

교과서는 ‘연결된 그래프 GG의 모든 꼭짓점과 변의 일부분으로 이루어진 수형도’라고 정의한다. 식 (1)의 세 조건과 같은 말이다. ‘최소 신장 트리’는 비용까지 최소인 대상의 이름이지 모든 생성수형도의 다른 이름은 아니다. 먼저 식 (1)의 연결 구조를 만족하는지, 그다음 비용이 최소인지 따로 확인한다.

원래 그래프가 연결되어야 생성수형도가 존재한다. 떨어진 두 부분은 원래 변만으로 연결할 수 없기 때문이다. 반대로 연결되어 있으면 회로 위의 변을 하나씩 지워도 나머지 길로 연결이 유지된다. 유한 번 지워 회로가 없어지면 모든 점이 남은 수형도가 되므로 생성수형도가 존재한다. 꼭짓점이 하나인 경우에도 변을 하나도 고르지 않은 생성수형도가 있다.

생성수형도는 몇 개나 만들 수 있을까?

회로를 끊는 방법의 수를 세면 된다. 꼭짓점이 nn개면 어느 생성수형도든 변이 n−1n-1개이므로, 원래 변이 mm개면 정확히 m−(n−1)m-(n-1)개를 지운다. 단순회로가 하나뿐인 연결그래프라면 그 회로의 변 하나를 지우는 방법만큼, 곧 회로의 길이만큼 생성수형도가 있다.

그림 1은 두 사각형이 변 QTQT를 함께 쓰는 그래프다. 꼭짓점 6개, 변 7개라서 7−5=27-5=2개를 지운다. 아무 두 변이나 지우면 안 된다. PQPQ와 PSPS를 함께 지우면 PP가 떨어진다.

함께 쓰는 변 QTQT를 기준으로 경우를 나눈다. QTQT를 지우면 바깥 둘레 P,Q,R,U,T,S,PP,Q,R,U,T,S,P 하나만 단순회로로 남으므로 둘레 여섯 변 중 하나를 더 지운다. QTQT를 남기면 왼쪽 사각형의 나머지 세 변 중 하나, 오른쪽 사각형의 나머지 세 변 중 하나를 지워야 한다.

6+3×3=15(2)6+3\times3=15 \tag{2}
두 사각형이 변 QT를 함께 쓰는 그래프의 생성수형도 세기. 위는 원래 그래프이고, 가운데는 QT를 지운 경우의 한 예(6가지), 아래는 QT를 남긴 경우의 한 예(3×3가지)다. 점선이 지운 변이다.
그림 1 두 사각형이 변 QT를 함께 쓰는 그래프의 생성수형도 세기. 위는 원래 그래프이고, 가운데는 QT를 지운 경우의 한 예(6가지), 아래는 QT를 남긴 경우의 한 예(3×3가지)다. 점선이 지운 변이다. figures/spanning_count_cases.py

한 변을 ‘지운다·남긴다’로 나누면 두 경우가 겹치지도 빠지지도 않아 합의 법칙으로 더할 수 있다. 남긴 경우 안에서는 왼쪽과 오른쪽의 선택이 따로 정해져 곱의 법칙을 쓴다.11 모든 두 점이 이어진 네 점 그래프(그림 2 위)는 생성수형도가 16개다. 꼭짓점이 nn개인 완전그래프는 nn−2n^{n-2}개라는 케일리 공식이 알려져 있다.

원래 그래프가 이미 수형도라면 무엇을 고르나요?

원래 그래프가 수형도이면 생성수형도는 자기 자신 하나뿐이다. 변이 m=n−1m=n-1개라 지울 변이 m−(n−1)=0m-(n-1)=0개이고, 수형도의 변은 하나만 지워도 연결이 끊어진다. 예를 들어 네 점을 일렬로 이은 변 3개는 모두 그대로 고른다.

가장 싼 변부터 고르면 언제 정답이 될까?

그냥 싼 변을 n−1n-1개 고르는 것만으로는 부족하다. 이미 고른 변들과 회로를 만드는 변을 제외해야 한다. 가중치가 작은 순서로 보면서 이 조건을 지키는 절차가 크루스칼 알고리즘이다. 같은 비용이면 어느 것을 먼저 시험해도 된다.

그림 2의 네 건물에서 비용을 다음과 같이 정했다. 단위는 모두 만 원이다.

변ABABBCBCACACCDCDBDBDADAD
비용123456
  1. 가장 싼 ABAB를 고른다. 아직 회로가 없다.
  2. BCBC를 고르면 A,B,CA,B,C가 연결된다.
  3. ACAC는 A,B,C,AA,B,C,A라는 회로를 만들므로 건너뛴다.
  4. CDCD를 고르면 DD까지 연결되고 변이 4−1=34-1=3개가 되어 끝난다.
W(T)=∑e∈E(T)w(e)=1+2+4=7만 원.(3)W(T)=\sum_{e\in E(T)}w(e)=1+2+4=7\text{만 원}. \tag{3}
위는 여섯 변의 가상 비용, 아래는 AB·BC·CD를 선택한 생성수형도다. 아래 점선은 원래 가능했지만 선택하지 않은 변이며, 선택한 세 변의 비용 합은 7이다.
그림 2 위는 여섯 변의 가상 비용, 아래는 AB·BC·CD를 선택한 생성수형도다. 아래 점선은 원래 가능했지만 선택하지 않은 변이며, 선택한 세 변의 비용 합은 7이다. figures/minimum_connections.py

가장 싼 세 변 AB,BC,ACAB,BC,AC만 고르면 비용 6이지만 DD가 떨어져 있어 생성수형도가 아니다. 식 (3)은 비용 비교 전에 모든 점을 연결했다는 조건을 만족한다. 교과서는 이렇게 변의 값의 합이 최소인 생성수형도를 찾는 일을 의사 결정 문제로 다룬다.

최소 총비용이면 각 두 점 사이도 가장 가까운가요?

그렇지는 않다. 그림 2에서 선택된 길로 AA에서 DD까지 가면 비용이 1+2+4=71+2+4=7이지만 직접 변 ADAD는 6이다. 모든 시설의 연결 비용 합을 줄이는 목표와 각 경로의 비용을 줄이는 목표는 다르다.

왜 이 절차가 전체 최소를 놓치지 않을까?

지금까지 고른 변들을 포함하는 최소 생성수형도가 하나 있다고 하자. 처음에는 아무 변도 고르지 않았으므로 가능하다. 다음에 고를 변 ee가 그 최소 수형도에 이미 있으면 그대로 진행한다.

없다면 최소 수형도에 ee를 넣어 회로 하나를 만든다. ee는 지금 서로 다른 두 연결 묶음을 잇는다. 회로의 나머지 길도 ee의 한 끝이 속한 묶음 밖으로 나가야 하므로, 그 길에서 묶음의 경계를 건너는 변 ff가 있다. 묶음 안의 변만 골라 왔으므로 ff는 아직 고르지 않은 변이다.

ff가 ee보다 쌌다면 ee보다 먼저 시험했을 것이다. 묶음은 합쳐지기만 하므로 그때도 ff의 두 끝은 다른 묶음이었고, ff는 선택되었어야 한다. 그렇지 않았으니 w(e)≤w(f)w(e)\le w(f)다.

ff를 빼고 ee를 넣으면 연결은 유지되고 회로는 없어져 다시 생성수형도가 된다. 총비용은 늘지 않으므로 여전히 최소이며, 이번 선택까지 포함한다. 이 교환을 매 단계 적용하면 마지막 선택 전체도 최소다. 서로 다른 묶음이 남아 있으면 그 사이를 잇는 변이 있으므로 모든 점을 잇기 전에 멈추지도 않는다.

이것은 그림 한 개의 비용을 비교한 실험보다 강한 일반 이유다. 가중치가 같은 변도 ≤\le로 비교하므로 처리할 수 있다.

프림 알고리즘은 크루스칼 알고리즘과 무엇이 다를까?

프림 알고리즘은 한 점에서 시작해 수형도 하나를 키운다. 지금까지 이은 점들의 집합 UU와 나머지 점을 잇는 변 가운데 가장 싼 것을 골라 UU에 새 점을 더한다. 크루스칼이 떨어진 조각들을 합쳐 가는 것과 달리, 프림은 늘 한 덩어리만 키운다. 우리교과서는 이 프림 알고리즘으로 최소 생성수형도를 구한다.

그림 3은 그림 2의 비용으로 DD에서 시작한 과정이다. 각 단계에서 경계를 건너는 변만 후보가 된다.

단계UU경계를 건너는 변(비용)고른 변
1{D}\{D\}CD 4, BD 5, AD 6CD\,4,\ BD\,5,\ AD\,6CDCD
2{C,D}\{C,D\}BC 2, AC 3, BD 5, AD 6BC\,2,\ AC\,3,\ BD\,5,\ AD\,6BCBC
3{B,C,D}\{B,C,D\}AB 1, AC 3, AD 6AB\,1,\ AC\,3,\ AD\,6ABAB
그림 2의 비용으로 D에서 시작한 프림 알고리즘의 세 단계. 위에서부터 1~3단계다. 칠한 점은 지금까지 이은 집합 U, 강조색이 아닌 실선은 U의 경계를 건너는 후보, 굵은 강조 변은 그 단계에서 고른 가장 싼 변, 가는 강조 변은 앞 단계에서 고른 변이다. 점선은 후보가 아닌 변이다.
그림 3 그림 2의 비용으로 D에서 시작한 프림 알고리즘의 세 단계. 위에서부터 1~3단계다. 칠한 점은 지금까지 이은 집합 U, 강조색이 아닌 실선은 U의 경계를 건너는 후보, 굵은 강조 변은 그 단계에서 고른 가장 싼 변, 가는 강조 변은 앞 단계에서 고른 변이다. 점선은 후보가 아닌 변이다. figures/prim_growth.py

고른 변은 크루스칼과 같은 AB,BC,CDAB,BC,CD이고 총비용도 7이다. 고른 순서만 CD,BC,ABCD,BC,AB로 다르다. 경계를 건너는 가장 싼 변을 넣어도 손해가 없다는 이유는 앞 절의 교환과 같다.

교과서의 창의력 문제처럼 거꾸로 비싼 변부터 지우는 방법도 있다. 지워도 연결이 유지되는 변만 지운다. 그림 2에서는 AD(6)AD(6), BD(5)BD(5), AC(3)AC(3)가 지워진다. CD(4)CD(4)와 BC(2)BC(2)는 지우면 연결이 끊어지므로 남고, 결과는 같은 AB,BC,CDAB,BC,CD다.

프림 알고리즘과 크루스칼 알고리즘의 결과는 같나요?

프림 알고리즘과 크루스칼 알고리즘의 총비용은 언제나 같다. 둘 다 최소 생성수형도를 만들기 때문이다. 그림 2처럼 여섯 변의 비용이 모두 다르면 최소 생성수형도가 하나뿐이라 고른 변도 같지만, 비용이 같은 변이 있으면 고른 변은 달라질 수 있다.

비용이 같은 변이 있으면 최소 생성수형도는 하나일까?

하나가 아닐 수 있다. 그림 4처럼 네 점을 둘레로 잇는 네 변의 비용이 모두 1이면, 어느 한 변을 지워도 총비용 3인 생성수형도가 된다. 서로 다른 네 결과가 모두 최소다.

둘레 네 변의 비용이 모두 1인 사각형에서 한 변씩 지운 네 생성수형도. 점선이 지운 변이고, 네 경우 모두 총비용이 3으로 최소다.
그림 4 둘레 네 변의 비용이 모두 1인 사각형에서 한 변씩 지운 네 생성수형도. 점선이 지운 변이고, 네 경우 모두 총비용이 3으로 최소다. figures/tied_msts.py

크루스칼에서 같은 비용의 변을 어느 순서로 시험하든, 프림에서 어느 점에서 시작하든 총비용은 같다. 답으로 고른 변을 쓸 때는 여러 최소 생성수형도 중 하나임을 밝힌다. 반대로 모든 변의 비용이 서로 다르면 최소 생성수형도는 하나뿐이라는 사실이 알려져 있다.

핵심

생성수형도는 모든 꼭짓점을 잇는 수형도인 부분그래프다. 연결된 단순 그래프에서 비용이 작은 변부터 회로를 만들지 않게 고르면 최소 생성수형도를 얻는다.

생성수형도의 흔한 오해

  • 변을 적게 고를수록 생성수형도가 더 작다. — 모든 생성수형도의 변은 같은 개수, n−1n-1개다. 그림 1의 15개도 모두 변이 5개이고, 최소화하는 것은 변 개수가 아니라 주어진 비용 합이다.
  • 싼 변은 무조건 골라야 한다. — 그림 2의 비용 3인 ACAC를 고르면 회로가 생기므로 건너뛴다. 값만 정렬하고 연결 조건을 빼면 안 된다.
  • 가장 비싼 변은 고르지 않는다. — 그림 2에 점 EE를 비용 10인 변 DEDE 하나로만 이으면, 그 변 없이는 EE를 연결할 수 없어 최소 비용이 7+10=177+10=17이다. 빼도 되는 것은 회로 위의 변뿐이다.

직접 해보기

  1. 꼭짓점 P,Q,RP,Q,R의 세 변 PQ,QR,PRPQ,QR,PR 비용이 각각 2,5,6이다. 최소 생성수형도와 비용을 구하시오.
  2. 네 점에 변 PQ,RSPQ,RS만 있다. 생성수형도가 존재하는지 설명하시오.
  3. 삼각형 PQRPQR과 삼각형 PRSPRS가 변 PRPR을 함께 쓰는 그래프(변 PQ,QR,RS,SP,PRPQ,QR,RS,SP,PR)의 생성수형도는 몇 개인가?
  4. 꼭짓점 P,Q,R,S,TP,Q,R,S,T와 변의 비용이 PR 1PR\,1, QS 2QS\,2, PQ 3PQ\,3, QR 4QR\,4, RS 5RS\,5, RT 6RT\,6, ST 7ST\,7이다. 크루스칼 알고리즘으로 최소 생성수형도와 총비용을 구하고, TT에서 시작한 프림 알고리즘이 변을 고르는 순서를 쓰시오.
  5. 문제 1의 최소 생성수형도에서 PP에서 RR로 가는 비용과 원래 그래프의 가장 싼 경로 비용을 비교하시오.
답과 풀이
  1. PQ,QRPQ,QR을 고르면 회로 없이 세 점을 연결하며 비용은 2+5=72+5=7이다. 다른 조합은 2+6=82+6=8, 5+6=115+6=11이므로 직접 비교해도 최소다.
  2. 두 연결 부분 사이의 변이 없으므로 불가능하다. 새 변을 만드는 것은 원래 그래프의 생성수형도를 고르는 일이 아니다.
  3. 꼭짓점 4개, 변 5개라 2개를 지운다. PRPR을 지우면 둘레 P,Q,R,S,PP,Q,R,S,P에서 한 변을 더 지워 4가지다. PRPR을 남기면 PQ,QRPQ,QR 중 하나와 RS,SPRS,SP 중 하나를 지워 2×2=42\times2=4가지다. 합은 4+4=84+4=8개다.
  4. 크루스칼은 PR(1)PR(1), QS(2)QS(2), PQ(3)PQ(3)을 고른다. QR(4)QR(4)는 P,Q,RP,Q,R의 회로를, RS(5)RS(5)는 P,Q,S,RP,Q,S,R의 회로를 만들어 건너뛰고 RT(6)RT(6)을 고른다. 총비용은 1+2+3+6=121+2+3+6=12다. TT에서 시작하면 후보 RT 6RT\,6, ST 7ST\,7 중 RTRT, 이어서 PRPR, PQPQ, QSQS 순서로 고른다. 같은 네 변이다.
  5. 고른 수형도에서는 P,Q,RP,Q,R의 비용 7이다. 원래는 직접 변 PRPR의 6이 더 싸다. 총연결 비용 최소와 두 점 사이의 최단 경로는 다른 목표다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-06]의 생성수형도와 의사결정.
  • 우리교과서 이산 수학 공개본 — 인쇄 152~154쪽의 생성수형도 정의, 생성수형도 개수 세기 예제, 프림 알고리즘 절차와 창의력 문제를 대조했다. 본문의 그래프와 비용은 별도로 구성했다.
  • Levin, Trees — Spanning Trees 절에서 꼭짓점은 그대로 두고 회로 위 변을 지워 생성수형도를 얻는 이유와 프림·크루스칼 알고리즘을 설명한다.
  • Garg, The Minimum Spanning Tree Problem — Setting·Key properties·Kruskal's·Prim's Algorithm 절. 비용이 모두 다르면 최소 생성수형도가 하나라는 사실과 경계를 건너는 가장 싼 변의 성질을 대조했다. 자료구조·시간 복잡도는 이 글의 선수가 아니다.

영상 노트

영상 노트
  • 00:00 모든 건물을 잇는 조건과 총비용 구별하기
  • 00:40 그림 1에서 함께 쓰는 변 QT로 경우를 나눠 식 (2)의 15개 세기
  • 01:40 그림 2의 변을 비용 순서로 골라 식 (3) 계산하고 회로를 만드는 AC 건너뛰기
  • 02:40 최소 수형도의 변을 교환해 선택이 안전함을 설명하기
  • 03:30 그림 3에서 D에서 시작한 프림 알고리즘과 크루스칼의 순서 비교, 거꾸로 지우기
  • 04:30 그림 4의 동률 네 가지와 비용 10인 다리 변의 경계 사례

지도에서의 위치

그래프의 뜻기초수학수형도기초수학생성수형도지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 생성수형도 개수 세기·프림 알고리즘·동률과 가장 비싼 변의 경계 사례 추가, 교환 논증과 오해 문장 정리, 해보기 보강 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림