신장 트리 개수(행렬-트리 정리) 계산기
그래프의 신장 트리가 몇 개인지를 라플라시안의 여인수 하나로 셉니다. 어느 행·열을 지워도 같은 값이 나오는 것을 여러 조합으로 확인하고, 완전그래프에서는 케일리 공식 n^(n−2)와 대조합니다.
줄마다 「정점 정점」 — 지금 6개
신장 트리 개수
16개
정점 4개 · 간선 6개
라플라시안 L = D − A
| A | B | C | D | |
|---|---|---|---|---|
| A | 3 | -1 | -1 | -1 |
| B | -1 | 3 | -1 | -1 |
| C | -1 | -1 | 3 | -1 |
| D | -1 | -1 | -1 | 3 |
신장 트리 수 = L에서 한 행과 한 열을 지운 행렬의 행렬식 = 16간선 부분집합을 전부 훑지 않고 행렬식 하나로 셉니다. 정점이 12개면 부분집합이 2⁶⁶ 개나 되므로 전수 탐색은 애초에 불가능합니다.
계산 방법
- 1간선을 줄마다 「정점 정점」으로 넣습니다.
- 2신장 트리 개수를 봅니다. 끊긴 그래프면 0입니다.
- 3여러 행·열을 지운 여인수가 모두 같은지 확인합니다.
- 4완전그래프를 넣으면 케일리 공식과 자동으로 대조합니다.
자주 묻는 질문
그래프의 신장 트리 개수가 라플라시안 행렬 L = D − A에서 한 행과 한 열을 지운 행렬의 행렬식과 같다는 정리입니다. 키르히호프가 전기회로망을 다루다 발견했습니다. 간선 부분집합을 전부 훑지 않고 행렬식 하나로 셀 수 있게 해 줍니다.
아무거나 지워도 같은 값이 나옵니다. 라플라시안은 모든 행의 합과 모든 열의 합이 0이라 행렬식 자체는 0이지만, 모든 여인수가 서로 같습니다. 이 계산기는 여러 조합을 실제로 계산해 그것을 확인합니다.
완전그래프 Kₙ에 이 정리를 적용하면 n^(n−2)가 나오는데 그것이 케일리 공식입니다. K4는 16개, K5는 125개입니다. 라벨이 붙은 트리를 세는 문제의 고전이며 프뤼퍼 수열로 다르게 증명하기도 합니다.
0이 나옵니다. 모든 정점을 잇는 트리가 아예 없기 때문입니다. 그래서 이 값이 0인지 아닌지로 연결 여부를 판정할 수도 있습니다.
두 정점 사이에 간선이 둘이면 어느 것을 쓰느냐가 서로 다른 트리이므로 신장 트리 수가 그만큼 늘어납니다. 라플라시안에도 그만큼 쌓입니다. 반대로 자기 고리는 트리에 절대 못 들어가므로 아예 무시합니다.
정확합니다. 보통의 가우스 소거는 나눗셈 때문에 부동소수점 오차가 끼어 반올림해야 하는데, K15만 되어도 값이 1.9×10¹⁵이라 그 반올림이 틀립니다. 이 계산기는 나눗셈이 늘 나누어떨어지는 바레이스 알고리즘에 큰 정수 연산을 붙여 아무리 커도 정확합니다.
최소 신장 트리는 가중치가 있는 그래프에서 가장 싼 트리 하나를 찾는 문제이고, 여기서는 가중치 없이 「트리가 몇 개나 되는가」를 셉니다. 신뢰도 분석, 격자 그래프의 개수 세기, 전기회로망의 저항 계산에 쓰입니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.
알아두면 좋은 점
- 방향 없는 그래프만 다룹니다. 방향이 있으면 유향 신장 트리(투트의 정리)가 됩니다.
- 자기 고리는 무시합니다. 신장 트리에 들어갈 수 없기 때문입니다.
- 다중 간선은 서로 다른 간선으로 세어 신장 트리 수가 늘어납니다.
- 가중치는 다루지 않습니다. 가중 버전은 가중 라플라시안을 씁니다.
- 값이 0이면 그래프가 끊겨 있다는 뜻입니다.
- 정점 20개·간선 400개까지 다룹니다.
- 바레이스 정수 소거와 큰 정수 연산을 써서 반올림 오차가 없습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.