C++ 완전 그래프에서 만들 수 있는 최대 간선 분리 스패닝 트리 개수

문제 개요

완전 그래프(Complete Graph)가 주어졌을 때, 이 그래프에서 만들 수 있는 간선 분리 스패닝 트리(Edge Disjoint Spanning Tree)의 개수를 구하는 문제입니다. 간선 분리 스패닝 트리란, 집합에 속한 어떤 두 스패닝 트리도 서로 공유하는 간선이 단 하나도 없는 경우를 의미합니다.

예를 들어 정점의 개수 N이 4라면, 출력 결과는 2가 됩니다. 4개의 정점으로 구성된 완전 그래프는 다음과 같습니다.

위 그래프에서 추출할 수 있는 두 개의 간선 분리 스패닝 트리는 다음과 같습니다.

핵심 아이디어

N개의 정점을 가진 완전 그래프에서 만들 수 있는 간선 분리 스패닝 트리의 최대 개수는 매우 간단한 공식으로 계산할 수 있습니다.

$[\frac{n}{2}]$

즉, 정점 개수를 2로 나눈 뒤 내림(floor)한 값이 곧 정답입니다. 그 이유는 완전 그래프의 총 간선 수가 n(n-1)/2개이고, 하나의 스패닝 트리를 구성하는 데 n-1개의 간선이 필요하기 때문입니다. 따라서 이론적으로 최대 n/2개의 서로 겹치지 않는 간선 집합으로 스패닝 트리를 만들 수 있습니다.

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;

int maxEdgeDisjointSpanningTree(int n){
    return floor(n/2);
}

int main() {
    int n = 4;
    cout << "Maximum Edge Disjoint Spanning Tree: " <<
        maxEdgeDisjointSpanningTree(n);
}

출력 결과

Maximum Edge Disjoint Spanning Tree: 2

정리

이 접근 방식은 O(1)의 시간 복잡도를 가지므로 매우 효율적입니다. 완전 그래프의 정점 개수만 주어지면 floor(n/2) 연산 한 번으로 간선 분리 스패닝 트리의 최대 개수를 즉시 계산할 수 있습니다. 복잡한 탐색이나 그래프 순회 없이도 수학적 성질만 활용하면 되기 때문에 실전 코딩 테스트에서도 유용하게 적용할 수 있는 패턴입니다.