C++でN頂点の2部グラフが持てる最大の辺数を求める方法

問題文

頂点の数を表す整数 N が与えられます。このとき、N 個の頂点からなる2部グラフ(バイパータイトグラフ)に含められる最大の辺数を求めるのが課題です。

2部グラフとは

2部グラフとは、頂点が2つの集合に分けられたグラフのことです。重要な性質として、同じ集合に属する頂点同士は決して辺で結ばれません。すべての辺は、必ず片方の集合の頂点ともう片方の集合の頂点を結びます。

具体例

N = 10 の場合を考えてみましょう。このとき最大で 25 本の辺が存在できます。

• 両方の集合にそれぞれ 5 つの頂点が入り、第1集合のすべての頂点が、第2集合のすべての頂点と辺で結ばれます。
• したがって、総辺数は 5 × 5 = 25 本となります。

アルゴリズム

• 辺数が最大になるのは、一方の集合のすべての頂点が、もう一方の集合のすべての頂点と辺で結ばれる場合です。つまり、辺数 = m × n(m、n はそれぞれの集合の頂点数)となります。
• 積 m × n を最大化するには、m を n と等しくするか、できるだけ近い値にする必要があります。これは「和が一定のとき、2つの数が等しいほど積は大きくなる」という性質によるものです。
• したがって、最大辺数は次の式で計算できます。

(N × N) / 4

N が奇数の場合も、整数除算(切り捨て)によって正しく処理されます。例えば N = 7 の場合は、7 × 7 / 4 = 12.25 → 12 本となります。

実装例(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 頂点の2部グラフにおける最大辺数は、頂点をできるだけ均等に2つの集合へ分割することで実現でき、公式 (N × N) / 4 を使えば O(1) で即座に計算できます。