Pythonでn個のノードを持つすべての単純無向グラフのコスト合計を求めるプログラム

問題の概要

n個のノードを持つ無向グラフGを考えます。単純無向グラフのコストは、そのグラフに含まれるすべてのノードのコストの合計として定義されます。さらに、各ノードのコストは D^k で表されます。ここで D はそのノードの次数(接続されているエッジの本数)です。

このとき、n と k の値が与えられるので、n個のノードから構成可能なすべての単純無向グラフについて、コストの合計を求めます。結果は非常に大きな数になる可能性があるため、1005060097 で割った余りを返します。

具体例

たとえば、入力が n = 3、k = 2 の場合、出力は 36 になります。これは、3つのノードを持つ単純グラフが全部で8通り存在するためです。

• エッジが3本あるグラフが1つ。コストは 2^2 + 2^2 + 2^2 = 12
• エッジが2本あるグラフが3つ。それぞれのコストは 1^2 + 1^2 + 2^2 = 6
• エッジが1本あるグラフが3つ。それぞれのコストは 0^2 + 1^2 + 1^2 = 2
• エッジが1本もないグラフが1つ。コストは 0^2 + 0^2 + 0^2 = 0

したがって、合計は 12×1 + 6×3 + 2×3 + 0×1 = 36 となります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• 二項係数を計算する関数 choose(n, k) を定義します。
• product := 1 と初期化します。
• i を n から n-k+1 まで1ずつ減らしながら、product := product × i を実行します。
• 続いて i を 1 から k まで1ずつ増やしながら、product := product ÷ i を実行します。
• product を整数として返します。
• 次に、関数 util(d, n) を定義します。これは「特定の1つのノードの次数がちょうど d となるグラフ」の総数を返す関数です。
• choose(n-1, d) × 2^(choose(n-1, 2)) を返します。
• メイン処理では、以下を実行します。
• total := 0 と初期化します。
• d を 0 から n-1 までループさせます。
  • total := total + util(d, n) × d^k
  • total := total mod 1005060097
• (total × n) mod 1005060097 を返します。

なぜこの式が成り立つのか

この解法のポイントは、グラフ内のすべてのノードが対称な立場にある点です。「あるノードの次数が d であるグラフの数」と「別の任意のノードの次数が d であるグラフの数」は必ず一致します。

util(d, n) は、ある特定のノードに注目したとき、その次数がちょうど d となるグラフの数を数えています。

• 残り n-1 個のノードから d 個を選んでエッジで結ぶ方法は C(n-1, d) 通りあります。
• それ以外のノード間(n-1 個のノード同士)のエッジは自由に張れるため、2^(C(n-1, 2)) 通りあります。

両者を掛け合わせたものが util(d, n) です。最後に全体に n を掛けるのは、どのノードに注目しても計算結果が同じになるため、全ノード分を一括して足し上げられるからです。

Python実装例

それでは、実際の実装を見てみましょう。

def choose(n, k):
    product = 1
    for i in range(n, n-k, -1):
        product *= i
    for i in range(1, k+1):
        product /= i
    return int(product)

def util(d, n):
    return choose(n-1, d) * 2 ** (choose(n-1, 2))

def solve(n, k):
    total = 0
    for d in range(n):
        total += util(d, n) * d ** k
        total %= 1005060097
    return (total * n) % 1005060097

n = 3
k = 2
print(solve(n, k))

入力

3, 2

出力

36

まとめ

本記事では、n個のノードを持つすべての単純無向グラフのコスト合計を、組合せ論と剰余演算を組み合わせて効率的に求める方法を紹介しました。次数ごとにグラフの数を数え上げ、各ノードのコスト D^k を掛けて集計するという、シンプルながら強力なアプローチです。