C++でグラフ内のどのエッジにも含まれないノード数を最大化する方法

ノードとエッジから構成されるグラフが与えられたとき、どのエッジにも接続されていないノードの最大数を求めるのがこの問題の目的です。完全グラフにおいては、ノード数は常にエッジ数以下になるという性質があります。

この問題は、完全グラフの性質を利用することで効率的に解くことができます。ノード数がnの完全グラフにおけるエッジ数は、次の式で表されます。

edge = n(n-1)/2 (nはノード数)
2 × edge = n(n-1)

n(n−1) の値が実際のエッジ数(2×edge)を超えた時点で、その分のノードは「余分」、つまりどのエッジにも使われていないことになります。そこで、i=1から順に i(i−1) と 2×edge を比較していき、初めて i(i−1) ≥ 2×edge となるiを見つければ、それがエッジを構成するために必要な最小ノード数です。答えは n − i として求められます。

それでは、具体例を使って理解を深めましょう。

入出力例

例1

入力: nodes = 5, edges = 2

出力: グラフ内でどのエッジにも含まれないノードの最大数 = 2

説明:
2本のエッジを構成するのに必要なノードは、最少で3個、最大で4個です。
3ノードで2本のエッジを張った場合、エッジに使われずに残るノードは最大で2個となります。

例2

入力: nodes = 2, edges = 1

出力: グラフ内でどのエッジにも含まれないノードの最大数 = 0

説明:
1本のエッジを作るには最低2つのノードが必要です。この場合、2つのノードは両方ともエッジに使用されているため、残りのノードは0個となります。

アルゴリズムの考え方

このプログラムでは、以下の手順で問題を解いています。

• ノード数(nodes)とエッジ数(edges)を入力データとして受け取ります。
• 関数 maximum(int nodes, int edges) は、ノード数とエッジ数を引数として受け取り、グラフ内でどのエッジにも含まれないノードの最大数を返します。
• 変数 i、temp、max を用意します。
• i = 0 から i ≤ nodes までのforループを開始します。
• 各反復で temp = i × (i − 1) を計算します。
• total = 2 × edges を計算します。
• temp ≥ total となった時点でforループを脱出します。
• max = nodes − i を計算します。
• max を結果として返します。

このアルゴリズムの時間計算量は O(√edges)(上限はノード数)程度であり、非常に効率的に動作します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
    int i, temp = 0, max;
    for (i = 0; i <= nodes; i++){
        temp = i * (i - 1);
        int total = 2 * edges;
        if (temp >= total){
            break;
        }
    }
    max = nodes - i;
    return max;
}
int main(){
    int nodes = 10;
    int edges = 5;
    cout<<"グラフ内でどのエッジにも含まれないノードの最大数:"<<maximum(nodes, edges) << endl;
}

出力

上記のコードを実行すると、次のような出力が得られます。

グラフ内でどのエッジにも含まれないノードの最大数: 6