fixedpoint.jp


ラベル付けされていない4頂点からなる有向非巡回グラフはいくつあるか (2021-06-19)

有向非巡回グラフ(DAG)は、計算タスクの依存関係因果関係のグラフィカル表現等に用いられる有向グラフの一種です。この記事では、与えられた個数\(n\)の頂点を持つDAGが何種類あるかを数えてみます。

各頂点に区別できるラベルが付いているDAGを数える場合には、漸化式を考えることで(\(n\)が増えると急激に大きくなりますが)比較的単純な式で表せます。

では、頂点がラベル付けされておらず、数えるときに頂点を区別せず同型なものはまとめて1つにする場合はどうでしょうか。例えば、以下の2つのDAGはそれぞれの頂点を赤い点線で示したように対応させると同じ形になるので、重複して数えないようにします。

同型になる2つのラベル付けされていないDAG

例えば、頂点が3つの場合は、以下のような6つのDAGがあり、これが全てです。

同型になる2つのラベル付けされていないDAG

では4つの頂点をもつDAGを数え上げるとどうでしょうか。紙と鉛筆を使って考えてみると分かるように、同型なものを重複して数えないようにしながら網羅するのはそれなりに大変です。

正解は以下のような31個になります。

4つの頂点をもつラベルされていないDAGの集合

数え上げる場合のヒントは以下のとおりです。

最後に、一般に正整数\(n\)個の頂点からなるラベル付けされていなDAGの個数はいくつになるでしょうか。この組み合わせ論的問題の解を手短に説明している論文が次のものです: R. W. Robinson, Enumeration of acyclic digraphs, Manuscript.

具体的な数列としてOEISA003087として登録されています。


© 2006-2021 fixedpoint.jp