문제 개요
정점(vertex) 목록과 각 정점의 차수(degree, 해당 정점에 연결된 간선의 수)가 주어져 있다고 가정해 보겠습니다. 이 차수 수열로부터 하나의 무방향 그래프(undirected graph)를 생성해야 하며, 그래프에는 루프(loop, 자기 자신으로 향하는 간선)나 중복 간선(multiple edge)이 포함되어서는 안 됩니다.
예를 들어 차수 수열이 [2, 2, 1, 1]이라면, 다음과 같은 그래프를 만들 수 있습니다.
해결 접근 방법
이 문제는 탐욕(greedy) 방식으로 해결할 수 있습니다. 차수가 아직 남아 있는 정점들을 차례대로 연결하면서 각 정점의 남은 차수를 1씩 줄여 나가는 것입니다. 구체적인 알고리즘은 다음과 같습니다.
그래프를 저장할 인접 행렬(adjacency matrix)
adj를 정의하고 모든 값을 0으로 초기화합니다.각 정점
i에 대해 다음을 반복합니다.i보다 번호가 뒤인 정점j(i+1부터 n-1까지)를 순회합니다.정점
i와j의 차수가 모두 0보다 크면 두 정점을 연결하고(adj_mat[i][j] = adj_mat[j][i] = 1), 두 정점의 차수를 각각 1씩 감소시킵니다.
모든 연결 작업이 끝나면 완성된 인접 행렬을 출력합니다.
j를 항상 i보다 큰 값부터 순회하므로 같은 쌍의 정점이 두 번 연결되는 일이 없고, 자기 자신과의 연결(루프)도 발생하지 않습니다.
C++ 구현 예제
#include <iostream>
#include <iomanip>
using namespace std;
void generateGraph(int vert_degree[], int n) {
int adj_mat[n][n];
for(int i = 0; i<n; i++){
for(int j = 0; j < n; j++){
adj_mat[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (vert_degree[i] > 0 && vert_degree[j] > 0) {
vert_degree[i]--; vert_degree[j]--;
adj_mat[i][j] = adj_mat[j][i] = 1;
}
}
}
cout << endl << setw(3) << " ";
for (int i = 0; i < n; i++)
cout << setw(3) << "(" << i << ")";
cout << endl << endl;
for (int i = 0; i < n; i++) {
cout << setw(4) << "(" << i << ")";
for (int j = 0; j < n; j++)
cout << setw(5) << adj_mat[i][j];
cout << endl;
}
}
int main() {
int vert_degree[] = { 2, 2, 1, 1, 1 };
int n = sizeof(vert_degree) / sizeof(vert_degree[0]);
generateGraph(vert_degree, n);
}출력 결과
(0) (1) (2) (3) (4) (0) 0 1 1 0 0 (1) 1 0 0 1 0 (2) 1 0 0 0 0 (3) 0 1 0 0 0 (4) 0 0 0 0 0
동작 분석 및 참고 사항
위 실행 결과에서 정점 0은 정점 1, 2와 연결되어 차수 2를 만족하고, 정점 1은 정점 3과 연결되어 차수 2를 만족합니다. 반면 정점 4는 차수 1이 주어졌음에도 앞선 정점들이 이미 자신의 차수를 모두 소진한 상태라 연결되지 못한 채 고립된 것을 볼 수 있습니다.
이처럼 단순 탐욕 방식은 차수 수열이 그래프 가능(graphical)한 수열이더라도, 정점 처리 순서에 따라 요구된 차수를 모두 충족하지 못하는 그래프를 만들 수 있다는 한계가 있습니다. 따라서 실제 응용에서는 입력 수열이 유효한 차수 수열인지 먼저 검증하는 것이 좋습니다. 대표적인 검증 방법으로는 에르되시-갈라이(Erdős–Gallai) 정리나 하벨-하키미(Havel–Hakimi) 알고리즘이 있으며, 특히 하벨-하키미 알고리즘은 검증과 동시에 실제 그래프를 구성할 수도 있습니다.
이 알고리즘의 시간 복잡도는 모든 정점 쌍을 한 번씩 확인하므로 O(n²)이며, 공간 복잡도 역시 인접 행렬 저장에 O(n²)입니다.