직관 — 필요한 연결만 남긴다
여러 건물에 통신선을 연결한다고 하자. 어느 두 건물 사이든 다른 건물을 거쳐 통신할 수 있으면 되고, 같은 곳을 도는 고리는 필수가 아니다. 가능한 선 중 일부만 골라 모두 연결한 뒤, 선마다 비용이 다르면 총비용도 비교한다.
건물과 가능한 연결을 나타낸 유한한 단순 무방향그래프를 사용한다. 실제 공사 비용이 아니라 각 변에 제시한 가상 비용만 더하는 모형이다. 한 출발점에서 각 건물까지 가장 가까운 길을 찾는 문제와도 구별한다.
생성수형도는 모든 꼭짓점을 남긴 수형도다
생성수형도는 원래 그래프의 모든 꼭짓점과 일부 변으로 이루어진 수형도다. 신장 트리(spanning tree) 또는 스패닝 트리라고도 한다. 변을 고를 때 원래 없던 변을 새로 넣을 수 없다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 원래 그래프 | graph | 사용 가능한 연결 전체 | |
| 생성수형도 | spanning tree | 모든 꼭짓점을 잇는 수형도 | |
| 꼭짓점·변 집합 | vertex set, edge set | 그래프의 대상과 연결 목록 | |
| 변의 가중치 | edge weight | 변 에 붙인 비용 | |
| 총가중치 | total weight | 고른 변의 가중치 합 | |
| 꼭짓점 수 | number of vertices | 반드시 포함할 대상 수 |
교과서는 ‘연결된 그래프 의 모든 꼭짓점과 변의 일부분으로 이루어진 수형도’라고 정의한다. 식 (1)의 세 조건과 같은 말이다. ‘최소 신장 트리’는 비용까지 최소인 대상의 이름이지 모든 생성수형도의 다른 이름은 아니다. 먼저 식 (1)의 연결 구조를 만족하는지, 그다음 비용이 최소인지 따로 확인한다.
원래 그래프가 연결되어야 생성수형도가 존재한다. 떨어진 두 부분은 원래 변만으로 연결할 수 없기 때문이다. 반대로 연결되어 있으면 회로 위의 변을 하나씩 지워도 나머지 길로 연결이 유지된다. 유한 번 지워 회로가 없어지면 모든 점이 남은 수형도가 되므로 생성수형도가 존재한다. 꼭짓점이 하나인 경우에도 변을 하나도 고르지 않은 생성수형도가 있다.
생성수형도는 몇 개나 만들 수 있을까?
회로를 끊는 방법의 수를 세면 된다. 꼭짓점이 개면 어느 생성수형도든 변이 개이므로, 원래 변이 개면 정확히 개를 지운다. 단순회로가 하나뿐인 연결그래프라면 그 회로의 변 하나를 지우는 방법만큼, 곧 회로의 길이만큼 생성수형도가 있다.
그림 1은 두 사각형이 변 를 함께 쓰는 그래프다. 꼭짓점 6개, 변 7개라서 개를 지운다. 아무 두 변이나 지우면 안 된다. 와 를 함께 지우면 가 떨어진다.
함께 쓰는 변 를 기준으로 경우를 나눈다. 를 지우면 바깥 둘레 하나만 단순회로로 남으므로 둘레 여섯 변 중 하나를 더 지운다. 를 남기면 왼쪽 사각형의 나머지 세 변 중 하나, 오른쪽 사각형의 나머지 세 변 중 하나를 지워야 한다.
figures/spanning_count_cases.py한 변을 ‘지운다·남긴다’로 나누면 두 경우가 겹치지도 빠지지도 않아 합의 법칙으로 더할 수 있다. 남긴 경우 안에서는 왼쪽과 오른쪽의 선택이 따로 정해져 곱의 법칙을 쓴다.11 모든 두 점이 이어진 네 점 그래프(그림 2 위)는 생성수형도가 16개다. 꼭짓점이 개인 완전그래프는 개라는 케일리 공식이 알려져 있다.
원래 그래프가 이미 수형도라면 무엇을 고르나요?
원래 그래프가 수형도이면 생성수형도는 자기 자신 하나뿐이다. 변이 개라 지울 변이 개이고, 수형도의 변은 하나만 지워도 연결이 끊어진다. 예를 들어 네 점을 일렬로 이은 변 3개는 모두 그대로 고른다.
가장 싼 변부터 고르면 언제 정답이 될까?
그냥 싼 변을 개 고르는 것만으로는 부족하다. 이미 고른 변들과 회로를 만드는 변을 제외해야 한다. 가중치가 작은 순서로 보면서 이 조건을 지키는 절차가 크루스칼 알고리즘이다. 같은 비용이면 어느 것을 먼저 시험해도 된다.
그림 2의 네 건물에서 비용을 다음과 같이 정했다. 단위는 모두 만 원이다.
| 변 | ||||||
|---|---|---|---|---|---|---|
| 비용 | 1 | 2 | 3 | 4 | 5 | 6 |
- 가장 싼 를 고른다. 아직 회로가 없다.
- 를 고르면 가 연결된다.
- 는 라는 회로를 만들므로 건너뛴다.
- 를 고르면 까지 연결되고 변이 개가 되어 끝난다.
figures/minimum_connections.py가장 싼 세 변 만 고르면 비용 6이지만 가 떨어져 있어 생성수형도가 아니다. 식 (3)은 비용 비교 전에 모든 점을 연결했다는 조건을 만족한다. 교과서는 이렇게 변의 값의 합이 최소인 생성수형도를 찾는 일을 의사 결정 문제로 다룬다.
최소 총비용이면 각 두 점 사이도 가장 가까운가요?
그렇지는 않다. 그림 2에서 선택된 길로 에서 까지 가면 비용이 이지만 직접 변 는 6이다. 모든 시설의 연결 비용 합을 줄이는 목표와 각 경로의 비용을 줄이는 목표는 다르다.
왜 이 절차가 전체 최소를 놓치지 않을까?
지금까지 고른 변들을 포함하는 최소 생성수형도가 하나 있다고 하자. 처음에는 아무 변도 고르지 않았으므로 가능하다. 다음에 고를 변 가 그 최소 수형도에 이미 있으면 그대로 진행한다.
없다면 최소 수형도에 를 넣어 회로 하나를 만든다. 는 지금 서로 다른 두 연결 묶음을 잇는다. 회로의 나머지 길도 의 한 끝이 속한 묶음 밖으로 나가야 하므로, 그 길에서 묶음의 경계를 건너는 변 가 있다. 묶음 안의 변만 골라 왔으므로 는 아직 고르지 않은 변이다.
가 보다 쌌다면 보다 먼저 시험했을 것이다. 묶음은 합쳐지기만 하므로 그때도 의 두 끝은 다른 묶음이었고, 는 선택되었어야 한다. 그렇지 않았으니 다.
를 빼고 를 넣으면 연결은 유지되고 회로는 없어져 다시 생성수형도가 된다. 총비용은 늘지 않으므로 여전히 최소이며, 이번 선택까지 포함한다. 이 교환을 매 단계 적용하면 마지막 선택 전체도 최소다. 서로 다른 묶음이 남아 있으면 그 사이를 잇는 변이 있으므로 모든 점을 잇기 전에 멈추지도 않는다.
이것은 그림 한 개의 비용을 비교한 실험보다 강한 일반 이유다. 가중치가 같은 변도 로 비교하므로 처리할 수 있다.
프림 알고리즘은 크루스칼 알고리즘과 무엇이 다를까?
프림 알고리즘은 한 점에서 시작해 수형도 하나를 키운다. 지금까지 이은 점들의 집합 와 나머지 점을 잇는 변 가운데 가장 싼 것을 골라 에 새 점을 더한다. 크루스칼이 떨어진 조각들을 합쳐 가는 것과 달리, 프림은 늘 한 덩어리만 키운다. 우리교과서는 이 프림 알고리즘으로 최소 생성수형도를 구한다.
그림 3은 그림 2의 비용으로 에서 시작한 과정이다. 각 단계에서 경계를 건너는 변만 후보가 된다.
| 단계 | 경계를 건너는 변(비용) | 고른 변 | |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
figures/prim_growth.py고른 변은 크루스칼과 같은 이고 총비용도 7이다. 고른 순서만 로 다르다. 경계를 건너는 가장 싼 변을 넣어도 손해가 없다는 이유는 앞 절의 교환과 같다.
교과서의 창의력 문제처럼 거꾸로 비싼 변부터 지우는 방법도 있다. 지워도 연결이 유지되는 변만 지운다. 그림 2에서는 , , 가 지워진다. 와 는 지우면 연결이 끊어지므로 남고, 결과는 같은 다.
프림 알고리즘과 크루스칼 알고리즘의 결과는 같나요?
프림 알고리즘과 크루스칼 알고리즘의 총비용은 언제나 같다. 둘 다 최소 생성수형도를 만들기 때문이다. 그림 2처럼 여섯 변의 비용이 모두 다르면 최소 생성수형도가 하나뿐이라 고른 변도 같지만, 비용이 같은 변이 있으면 고른 변은 달라질 수 있다.
비용이 같은 변이 있으면 최소 생성수형도는 하나일까?
하나가 아닐 수 있다. 그림 4처럼 네 점을 둘레로 잇는 네 변의 비용이 모두 1이면, 어느 한 변을 지워도 총비용 3인 생성수형도가 된다. 서로 다른 네 결과가 모두 최소다.
figures/tied_msts.py크루스칼에서 같은 비용의 변을 어느 순서로 시험하든, 프림에서 어느 점에서 시작하든 총비용은 같다. 답으로 고른 변을 쓸 때는 여러 최소 생성수형도 중 하나임을 밝힌다. 반대로 모든 변의 비용이 서로 다르면 최소 생성수형도는 하나뿐이라는 사실이 알려져 있다.
생성수형도는 모든 꼭짓점을 잇는 수형도인 부분그래프다. 연결된 단순 그래프에서 비용이 작은 변부터 회로를 만들지 않게 고르면 최소 생성수형도를 얻는다.
생성수형도의 흔한 오해
- 변을 적게 고를수록 생성수형도가 더 작다. — 모든 생성수형도의 변은 같은 개수, 개다. 그림 1의 15개도 모두 변이 5개이고, 최소화하는 것은 변 개수가 아니라 주어진 비용 합이다.
- 싼 변은 무조건 골라야 한다. — 그림 2의 비용 3인 를 고르면 회로가 생기므로 건너뛴다. 값만 정렬하고 연결 조건을 빼면 안 된다.
- 가장 비싼 변은 고르지 않는다. — 그림 2에 점 를 비용 10인 변 하나로만 이으면, 그 변 없이는 를 연결할 수 없어 최소 비용이 이다. 빼도 되는 것은 회로 위의 변뿐이다.
직접 해보기
- 꼭짓점 의 세 변 비용이 각각 2,5,6이다. 최소 생성수형도와 비용을 구하시오.
- 네 점에 변 만 있다. 생성수형도가 존재하는지 설명하시오.
- 삼각형 과 삼각형 가 변 을 함께 쓰는 그래프(변 )의 생성수형도는 몇 개인가?
- 꼭짓점 와 변의 비용이 , , , , , , 이다. 크루스칼 알고리즘으로 최소 생성수형도와 총비용을 구하고, 에서 시작한 프림 알고리즘이 변을 고르는 순서를 쓰시오.
- 문제 1의 최소 생성수형도에서 에서 로 가는 비용과 원래 그래프의 가장 싼 경로 비용을 비교하시오.
답과 풀이
- 을 고르면 회로 없이 세 점을 연결하며 비용은 이다. 다른 조합은 , 이므로 직접 비교해도 최소다.
- 두 연결 부분 사이의 변이 없으므로 불가능하다. 새 변을 만드는 것은 원래 그래프의 생성수형도를 고르는 일이 아니다.
- 꼭짓점 4개, 변 5개라 2개를 지운다. 을 지우면 둘레 에서 한 변을 더 지워 4가지다. 을 남기면 중 하나와 중 하나를 지워 가지다. 합은 개다.
- 크루스칼은 , , 을 고른다. 는 의 회로를, 는 의 회로를 만들어 건너뛰고 을 고른다. 총비용은 다. 에서 시작하면 후보 , 중 , 이어서 , , 순서로 고른다. 같은 네 변이다.
- 고른 수형도에서는 의 비용 7이다. 원래는 직접 변 의 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인 다리 변의 경계 사례
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 생성수형도 개수 세기·프림 알고리즘·동률과 가장 비싼 변의 경계 사례 추가, 교환 논증과 오해 문장 정리, 해보기 보강 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림