fixedpoint.jp

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

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

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

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

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

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

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

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

• 上の図で最上段のDAGが辺の数が最大(6つ)ですが、他のDAGはこのDAGからうまく辺を除いたものと必ず同型になります。これは、DAGの頂点を常にトポロジカルソートできるという事実から導かれます。
• 同じ辺の数を持つ2つのDAGが同型かどうかは、各頂点に対し出次数および入次数のペアをラベルとして付けてみます。このペアによるラベルの集合が2つのDAGで等しければ同型になります。また、どのDAGもエッジの向きを入れ換えてもまたDAGになりますが、このペアによるラベルで出次数と入次数を入れ換えることに相当します。

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

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