グラフのエッジカバー（辺被覆）を求めるC++プログラムの解説

グラフの頂点数 n が与えられたとき、そのグラフのエッジカバー（辺被覆）を計算するのが本記事のテーマです。エッジカバーとは、グラフのすべての頂点を覆うために必要な最小の辺の数を見つける問題を指します。

エッジカバーとは

例として、頂点数 n = 5 のグラフを考えてみましょう。グラフは次のようになります。

このグラフのエッジカバーは 3 です。つまり、3本の辺を選ぶことで、5つの頂点すべてを覆うことができます。

次に、頂点数 n = 8 の場合を見てみましょう。

この場合のエッジカバーは 4 になります。

入出力例

入力: n = 5
出力: 3
入力: n = 8
出力: 4

計算のアプローチ

この問題は実は非常にシンプルな公式で解くことができます。エッジカバーの最小値は、頂点数を2で割った値を切り上げ（天井関数）したものになります。

エッジカバー = ⌈n / 2⌉

手順は以下のとおりです。

• 頂点数 n を入力として受け取る
• n を 2.0 で割った結果の天井値（切り上げ）を求める
• その結果を返して出力する

アルゴリズム

開始
ステップ1 → グラフのエッジカバーを計算する関数を宣言する
    int edge(int n)
        float val = 0 とする
        val = ceil(n / 2.0) とする
        val を返す
ステップ2 → main() 内で
        int n = 10 とする
        edge(n) を呼び出す
終了

C++による実装例

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

// エッジカバーを計算する関数
int edge(int n) {
    float val = 0;
    val = ceil(n / 2.0);  // 切り上げて最小の辺の数を求める
    return val;
}

int main() {
    int n = 10;
    cout << "必要な最小の辺の数は : " << edge(n);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

必要な最小の辺の数は : 5

まとめ

グラフのエッジカバーは、頂点数 n を2で割って切り上げるだけで求められる、非常にシンプルな問題です。標準ライブラリの ceil 関数を使うことで、数行のコードで効率的に計算できます。計算量は O(1) であり、頂点数が大きくなっても高速に動作する点が魅力です。