C++で解く！有向グラフの全ノード削除に必要な操作回数の期待値を求める方法

問題概要

有向グラフ G の隣接行列が与えられているとします。グラフが空になるまで、次の操作を繰り返し実行します。

グラフから任意の頂点を1つ選び、その頂点自身と、その頂点から辺をたどって到達できるすべての頂点をまとめて削除します。頂点を削除するとき、その頂点に接続されている辺も同時に取り除かれます。このとき、グラフが空になるまでに操作を行う回数の期待値を求めるのが目的です。

入力例と出力例

次のようなグラフが入力として与えられた場合を考えてみましょう。

この場合の出力は 1.6667 になります。その理由は以下の通りです。

• 最初に頂点 A を選べば、すべての頂点が一度で削除できる（操作回数 1 回）
• 最初に頂点 B を選ぶと B と C が削除され、2 回目の操作で A を選んで残りを削除する（操作回数 2 回）
• 最初に頂点 C を選んだ場合も同様に 2 回の操作が必要になる

したがって平均は (1 + 2 + 2) / 3 = 1.6667 となります。

アルゴリズムの考え方

この問題は期待値の線形性を利用することで効率的に解けます。

まず、隣接行列に対してワーシャル・フロイド法と同じ要領で推移閉包を計算します。これにより、任意の頂点 i から頂点 j へ到達可能かどうかをすべて求めることができます。あわせて対角成分を 1 に設定しておけば、「自分自身には必ず到達できる」という条件も自然に組み込めます。

その後、各頂点 i について「頂点 i に到達できる頂点の個数 k（自分自身を含む）」を数えます。頂点 i は、その k 個のうちいずれかが初めて選ばれた時点で必ず削除されます。どの頂点が先に選ばれるかは等確率であるため、頂点 i を削除するのに寄与する操作回数の期待値は 1/k となります。

期待値の線形性より、最終的な答えはすべての頂点について 1/k を合計した値になります。

解法の手順

この問題を解くための手順は以下の通りです。

1. n をグラフ G のサイズとします。
2. すべての対角成分 G[i][i] を 1 に設定します。
3. 三重ループで推移閉包を計算します。
4. 各頂点 i について、頂点 i に到達できる頂点の個数 k を数えます。
5. ans に 1.0 / k を加算していきます。
6. 最終的な ans を結果として返します。

n := size of G
for initialize i := 0, when i < n, update (increase i by 1), do:
    G[i, i] := 1
for initialize k := 0, when k < n, update (increase k by 1), do:
    for initialize i := 0, when i < n, update (increase i by 1), do:
        for initialize j := 0, when j < n, update (increase j by 1), do:
            if G[i, k] is non-zero and G[k, j] is non-zero, then:
                G[i, j] := 1
ans := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    k := 0
    for initialize j := 0, when j < n, update (increase j by 1), do:
        if G[j, i] is non-zero, then:
            (increase k by 1)
    ans := ans + 1.0 / k
return ans

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

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

double solve(vector<vector<int>> G){
    int n = G.size();
    for (int i = 0; i < n; ++i)
        G[i][i] = 1;
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (G[i][k] && G[k][j])
                    G[i][j] = 1;
    double ans = 0;
    for (int i = 0; i < n; ++i){
        int k = 0;
        for (int j = 0; j < n; ++j)
            if (G[j][i])
                ++k;
        ans += 1.0 / k;
    }
    return ans;
}
int main(){
    vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
    cout << solve(G) << endl;
}

入力

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

出力

1.66667

計算量について

推移閉包の計算に三重ループを使用しているため、時間計算量は O(n³) となります。また、隣接行列を保持するために空間計算量は O(n²) が必要です。頂点数 n が数百程度までのグラフであれば十分に実用的な速度で動作します。