C++로 계산하는 이분 그래프(Bipartite Graph)의 최대 간선 수

문제 설명

정수 N이 주어지며, 이 값은 정점(Vertex)의 개수를 나타냅니다. 이 문제의 목표는 N개의 정점을 가진 이분 그래프(Bipartite Graph)에서 만들 수 있는 최대 간선(Edge) 수를 구하는 것입니다.

이분 그래프란?

이분 그래프는 그래프의 모든 정점을 서로 겹치지 않는 두 개의 집합으로 나눌 수 있는 그래프를 말합니다.

• 그래프의 정점들이 두 개의 집합으로 분할됩니다.
• 같은 집합에 속한 정점들 사이에는 간선이 절대 존재하지 않으며, 모든 간선은 반드시 서로 다른 집합에 속한 정점들을 연결합니다.

예시

N = 10인 경우, 만들 수 있는 최대 간선 수는 25개입니다.

• 두 집합이 각각 5개씩의 정점을 가질 때, 첫 번째 집합의 모든 정점이 두 번째 집합의 모든 정점과 간선으로 연결됩니다.
• 따라서 총 간선 수는 5 × 5 = 25가 됩니다.

접근 방법 및 알고리즘

• 간선 수는 한 집합의 모든 정점이 다른 집합의 모든 정점과 연결될 때 최대가 됩니다. 즉, 각 집합의 정점 수를 m, n이라 할 때 edges = m × n 입니다.
• 전체 정점 수(m + n = N)가 고정된 상태에서 곱 m × n을 최대화하려면, m과 n이 서로 같거나 최대한 비슷해야 합니다.
• 따라서 최대 간선 수는 다음 공식으로 계산할 수 있습니다.

최대 간선 수 = ⌊(N × N) / 4⌋

정점 수 N이 홀수인 경우 나눗셈 결과가 정수가 되지 않으므로, 내림(floor) 처리하여 정수 값을 얻습니다.

C++ 구현 예제

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

int getMaxEdges(int n) {
    return floor((n * n) / 4);
}

int main() {
    int n = 7;
    cout << "Maximum edges = " << getMaxEdges(n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Maximum edges = 12

N = 7일 경우, 7 × 7 / 4 = 12.25이므로 내림하여 최대 간선 수는 12가 됩니다. 이는 한쪽 집합에 3개, 다른쪽 집합에 4개의 정점을 배치했을 때 3 × 4 = 12개의 간선이 만들어지는 것과 일치합니다.