C++로 그래프의 최대·최소 고립 정점 개수 구하기

그래프 이론에서 고립 정점(isolated vertex)이란 어떤 간선에도 연결되어 있지 않은 정점을 의미합니다. 이 글에서는 정점의 수(nov)와 간선의 수(noe)가 주어졌을 때, 해당 조건으로 그래프를 구성할 경우 나타날 수 있는 고립 정점의 최솟값과 최댓값을 C++로 구하는 방법을 알아보겠습니다.

최소 고립 정점 구하기

고립 정점을 최소화하려면 모든 간선이 서로 다른 정점을 사용하도록 배치해야 합니다. 즉, 두 간선이 같은 정점을 공유하지 않게 하는 것입니다. 하나의 간선은 두 개의 정점만 필요로 하므로 다음과 같이 계산할 수 있습니다.

연결된(비고립) 정점 수 = 2 × 간선 수
고립 정점 수 = 전체 정점 수 − 연결된 정점 수

만약 정점 수가 2 × 간선 수보다 작거나 같다면, 모든 정점이 간선에 연결될 수 있으므로 고립 정점의 최솟값은 0이 됩니다.

최대 고립 정점 구하기

고립 정점을 최대화하려면 반대로 가능한 한 적은 수의 정점만으로 모든 간선을 소진해야 합니다. 가장 효율적인 방법은 각 정점 쌍 사이에 변과 대각선이 모두 존재하는 완전 그래프(complete graph) 형태의 다각형을 만드는 것입니다.

C++로 그래프의 최대·최소 고립 정점 개수 구하기

예를 들어 정점 5개와 간선 6개가 주어진 경우를 살펴보겠습니다. 사각형의 네 변에 대각선 2개를 추가하면 단 4개의 정점만으로 6개의 간선을 모두 만들 수 있습니다. 따라서 남은 1개의 정점이 고립되며, 이것이 가능한 최댓값입니다.

n각형에서 한 정점에서 뻗어 나가는 대각선의 수는 n×(n−3)/2이며, n개의 정점으로 만들 수 있는 전체 간선(변 + 대각선)의 수는 n×(n−1)/2입니다. 이 공식이 최대 고립 정점을 계산하는 핵심 원리입니다.

입력 및 출력 예시

입력

정점 수 5, 간선 수 6

출력

최소 고립 정점 0, 최대 고립 정점 1

설명

위 그림에서 설명한 것처럼 4개의 정점만으로 6개의 간선을 모두 배치할 수 있으므로, 나머지 1개의 정점이 고립됩니다.

입력 − 정점 수 2, 간선 수 1
출력 − 최소 고립 정점 0, 최대 고립 정점 0
설명 − 하나의 간선을 만들려면 최소 두 개의 정점이 필요하므로, 두 정점 모두 간선에 연결됩니다.

알고리즘 접근 방식

정수 noe와 nov는 각각 간선의 수와 정점의 수를 저장합니다.
함수 findisolatedvertices(int v, int e)는 정점 수와 간선 수를 매개변수로 받아 가능한 최소 및 최대 고립 정점 수를 출력합니다.
최솟값 계산: 정점 수(v)가 2×e 이하이면 고립 정점은 없습니다. 그렇지 않으면 연결될 수 있는 정점은 최대 2×e개이므로, 최소 고립 정점 수는 v − 2×e입니다.
최댓값 계산: i를 1부터 정점 수까지 증가시키며, i×(i−1)/2 ≥ e가 되는 첫 번째 i에서 반복을 멈춥니다. 이는 i개의 정점만으로 e개의 간선을 모두 배치할 수 있다는 의미입니다.
따라서 최대 고립 정점 수는 v − i가 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void findisolatedvertices(int v, int e){
    // 하나의 간선에는 2개의 정점이 필요합니다
    if (v <= 2 * e) { // 모든 정점이 간선에 연결되어 있는 경우
        cout << "최소 고립 정점 수: " << 0 << endl;
    } else {
        int niso = 2 * e; // 연결 가능한 최대 정점 수
        cout << "최소 고립 정점 수: " << v - niso << endl;
    }
    // 고립 정점의 최대 개수를 구합니다
    // e개의 간선을 모두 배치하는 데 필요한
    // 최소 정점 수를 찾는 루프입니다
    int i;
    for (i = 1; i <= v; i++) {
        if (i * (i - 1) / 2 >= e)
            break;
    }
    cout << endl << "최대 고립 정점 수: " << v - i;
}

int main(){
    // 정점의 수
    int nov = 5;
    // 간선의 수
    int noe = 2;
    // 최대 및 최소 고립 정점 수를 계산하는 함수 호출
    findisolatedvertices(nov, noe);
    return 0;
}

실행 결과

최소 고립 정점 수: 1
최대 고립 정점 수: 2

정점 5개와 간선 2개가 주어진 경우, 간선 하나당 정점 2개씩 사용하면 4개의 정점이 연결되고 1개의 정점이 고립됩니다(최솟값). 반면, 3개의 정점만으로도 2개의 간선을 모두 배치할 수 있으므로 나머지 2개의 정점이 고립될 수 있습니다(최댓값).