C++でグラフの孤立頂点の最大数と最小数を求める方法

孤立頂点とは？

グラフ理論において孤立頂点（isolated vertex）とは、どの辺にも接続されていない頂点のことを指します。この記事では、辺の数と頂点の数が与えられたとき、そのグラフに存在しうる孤立頂点の最小数と最大数を求める方法を、C++のコードとともに分かりやすく解説します。

孤立頂点の最小数を求める

孤立頂点を最小化するには、すべての辺が互いに異なる頂点を使うように配置します（どの2つの辺も頂点を共有しない状態）。各辺が必要とする頂点は2つだけなので、次のように計算できます。

非孤立頂点の数 = 2 × 辺の数
孤立頂点の数 = 全頂点数 − 非孤立頂点の数

もし頂点数 ≤ 2 × 辺の数であれば、すべての頂点を何らかの辺に接続できるため、孤立頂点の数は 0 になります。

孤立頂点の最大数を求める

逆に孤立頂点を最大化するには、できるだけ少ない頂点ですべての辺を接続する構造を作ります。具体的には、各頂点ペアの間にも対角線が張られた多角形（完全グラフに近い形状）を考えると実現できます。

たとえば、5つの頂点と6つの辺が与えられた場合、4つの頂点からなる四角形に2本の対角線を加えれば6本の辺を実現できます。このとき使用される頂点は4つだけであり、残りの1つの頂点が孤立します。これが孤立頂点の最大数です。

n角形において、1つの頂点から他の頂点へ引ける対角線の数は n×(n−3)/2、全辺数は n×(n−1)/2 で表されます。つまり、i 個の頂点で作れる最大の辺数は i×(i−1)/2 であり、この値が与えられた辺数以上になる最小の i を見つければよいことになります。

入力例と出力例

例1

入力： 頂点数 5、辺数 6

孤立頂点の最小数： 0
孤立頂点の最大数： 1

説明： 上記の図の通り、4つの頂点で6本の辺を構成できるため、残りの1頂点が孤立します。

例2

入力： 頂点数 2、辺数 1

孤立頂点の最小数： 0
孤立頂点の最大数： 0

説明： 1本の辺は必ず2つの頂点の間に形成されるため、両方の頂点が使われます。

アルゴリズムのアプローチ

• 整数 noe と nov に、それぞれ辺の数と頂点の数を格納します。
• 関数 findisolatedvertices(int v, int e) は、辺の数と頂点の数を引数として受け取り、可能な孤立頂点の最小数と最大数を出力します。
• 頂点数が 2×e 以下の場合、孤立頂点は存在しません。それ以外の場合、非孤立頂点は最大で 2×e 個となるため、孤立頂点の最小数は v − 2×e です。
• 孤立頂点の最大数を求めるには、i を 1 から頂点数まで増やしながらループし、「i × (i − 1) / 2 ≥ e」となる最初の i で break します。e 本の辺には i 個の頂点で十分だからです。
• ループを抜けた時点の i を用いて、最大の孤立頂点数は v − i として求められます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e){
    // 1本の辺には2つの頂点が必要
    if (v <= 2 * e) // すべての頂点が辺に接続可能
        cout << "孤立頂点の最小数： " << 0 << endl;
    else {
        int niso = 2 * e; // 非孤立頂点の最大数
        cout << "孤立頂点の最小数： " << v - niso << endl;
    }
    // 孤立頂点の最大数を求める
    // 接続に必要な頂点数を見つけるループ
    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

このように、辺と頂点の数さえ分かれば、実際にグラフを構築することなく、単純な計算だけで孤立頂点の最小数・最大数を効率的に求められます。計算量は O(V) と非常に軽量である点も、このアプローチの大きな利点です。