コンポーネント数が増えると、取り得る依存構造の候補は急増します。しかし、構成可能なグラフの総数と、実際に採用したグラフの辺数は異なる量です。ソフトウェアの依存関係を確認する際は、候補総数ではなく、採用した構造に存在する接続を調べます。
この記事では、Python の標準ライブラリで完全グラフとパスグラフを構築し、同じ頂点数でも辺数が変わることを確認します。
依存グラフの候補数と実際の辺数を区別する
依存グラフは、コンポーネントを頂点、コンポーネント間の関係を辺として表したものです。まずは計数条件を揃えるため、頂点に名前が付いており、自己ループと多重辺がなく、辺に方向がない単純無向グラフを扱います。この単純化による候補総数と実際の辺数の区別は、ソフトウェアの依存構造を考える際にも必要です[1]。
頂点が n 個なら、異なる 2 頂点を選ぶ方法は次の数です。
\binom{n}{2}=\frac{n(n-1)}{2}
それぞれの頂点対に辺を「置く」「置かない」の 2 通りがあるため、構成可能なグラフの総数は次のようになります。
G(n)=2^{\binom{n}{2}}
一方、すべての頂点対に辺を置く完全グラフの辺数は、次の式で求まります。
E_{\mathrm{complete}}(n)=\binom{n}{2}
連結で閉路を持たない木構造の辺数は、次のとおりです。
E_{\mathrm{tree}}(n)=n-1
例えば n=10 の場合、構成可能なグラフは 2^45 個ですが、完全グラフの辺数は 45 本、木構造の辺数は 9 本です。グラフ候補総数は選べる構造の数、辺数は選んだ一つの構造に存在する接続の数を表します。
実行環境
Python 3.12 を想定します。使用するのは標準ライブラリの itertools と math だけです。math.comb() は Python 3.8 以降で利用できます。
$ python3 --version
Python 3.13.5
上記は検証に使用した環境の出力です。以下のコードは Python 3.12 の標準ライブラリで提供される機能だけを使用しています。
Python で完全グラフとパスグラフを構築する
完全グラフでは、itertools.combinations(range(n), 2) を使って重複のない頂点対を列挙できます。combinations() は同じ組を順序違いで再出力しません[2]。組み合わせ数の計算には math.comb(n, 2) を使用します[3]。
木構造の一例には、頂点 0 から n-1 を順番につないだパスグラフを採用します。これにより、完全グラフのすべての辺と、木構造の n-1 本の辺を実際に生成して比較できます。
from itertools import combinations
from math import comb
def complete_graph_edges(n):
return list(combinations(range(n), 2))
def path_graph_edges(n):
return [(i, i + 1) for i in range(n - 1)]
def compare(n):
possible_edges = comb(n, 2)
graph_candidates = 2 ** possible_edges
complete = complete_graph_edges(n)
path = path_graph_edges(n)
assert len(complete) == possible_edges
assert len(path) == n - 1
assert len(set(complete)) == len(complete)
assert len(set(path)) == len(path)
assert all(0 <= a < b < n for a, b in complete + path)
assert all(b == a + 1 for a, b in path)
print(
f"{n:>2} | {graph_candidates} | "
f"{len(complete):>3} | {len(path):>3}"
)
print(" n | graph_candidates | complete_edges | path_edges")
for n in (4, 10, 20):
compare(n)
graph_candidates は 2 ** possible_edges により数式から求めます。候補となるグラフすべてを生成する処理はありません。生成するのは、各 n について完全グラフとパスグラフの 2 構造だけです。
assert は生成結果に対する確認です。辺数に加え、重複、自己ループ、頂点範囲、パスグラフの隣接関係を調べます。検証時には -O を付けずに実行します。
グラフ候補総数と辺数を比較する
次のコマンドで実行します。
$ python3 graph_comparison.py
実行結果は次のとおりです。
n | graph_candidates | complete_edges | path_edges
4 | 64 | 6 | 3
10 | 35184372088832 | 45 | 9
20 | 1569275433846670190958947355801916604025588861116008628224 | 190 | 19
| 頂点数 | グラフ候補総数 | 完全グラフの辺数 | パスグラフの辺数 |
|---|---|---|---|
| 4 | $2^6=64$ | 6 | 3 |
| 10 | $2^{45}$ | 45 | 9 |
| 20 | $2^{190}$ | 190 | 19 |
n=20 ではグラフの候補総数が 2^190 個まで増えます。しかし、今回生成した完全グラフは 190 本、パスグラフは 19 本の辺を持ちます。
実行したコードでは、候補総数は数式から計算し、辺数は実際に生成した配列の長さから取得しています。異なる方法で求めた値が assert によって一致することも確認できます。
辺数から判断できる範囲を確認する
この検証で確定するのは、同じ頂点数でも依存構造の選び方によって辺数が異なるという事実です。実システムに適用する際は、次の区別が必要です。
-
依存の方向：実際のソフトウェアでは
AがBを使用する関係と、その逆は異なります。無向グラフの辺数だけでは、変更が伝播する方向を識別できません。 - 公開インターフェース：同じ辺数であっても、実装の詳細へ直接依存する場合と、公開されたインターフェースだけに依存する場合では、変更時に見直す箇所が異なります。
- 影響範囲：辺数は直接接続の数です。変更が到達する頂点の範囲を求めるには、有向依存グラフと依存経路の調査が必要です。
例えば、10 個のコンポーネントがあれば、無向グラフとしての完全グラフには 45 本の辺を置けます。一方、実際に必要な関係だけを持つ構造では、採用された辺を数える必要があります。辺数の比較から変更工数や障害発生率まで直接推定することはできません。
依存構造の評価では採用した辺を確認する
コンポーネント数 n が決まると、単純無向グラフの候補総数 2 ** comb(n, 2) は計算できます。しかし、実際に管理する接続数は、採用したグラフの辺を調べて確定します。
Python で n=4,10,20 の完全グラフとパスグラフを生成した結果、完全グラフの辺数は n(n-1)/2、パスグラフの辺数は n-1 に一致しました。設計を評価する場合は、まず実際の依存関係を抽出し、辺数、依存方向、公開インターフェースを確認することが、候補総数から複雑性を推定するより具体的な判断につながります。
参考文献
- id774, ソフトウェアの複雑性はどこへ移るのか（2026-11-06）. https://blog.id774.net/entry/2026/11/06/5613/
- Python Software Foundation, itertools — Functions creating iterators for efficient looping. https://docs.python.org/3.12/library/itertools.html
- Python Software Foundation, math — Mathematical functions. https://docs.python.org/3.12/library/math.html