グラフ列挙

組み合わせ論は数学の一分野であり、グラフ列挙は、特定の種類の無向グラフまたは有向グラフを、通常はグラフの頂点の数の関数として数える組み合わせ列挙問題のクラスを記述します。 ^{[ 1 ]}これらの問題は、厳密に（代数列挙問題として）解くことも、漸近的に解くこともできます。この数学分野の先駆者は、ジョージ・ポリア^{[ 2 ]}、アーサー・ケイリー^{[ 3 ]}、J・ハワード・レッドフィールド^{[ 4 ]}でした。

グラフ列挙問題の中には、グラフの頂点が互いに区別できるようにラベル付けされているとみなされるものもあれば、頂点の任意の順列が同じグラフを形成するとみなされ、頂点が同一またはラベルなしとみなされるものもある。一般に、ラベル付き問題の方が簡単である傾向がある。^{[ 5 ]}組み合わせ列挙全般と同様に、ポリア列挙定理はラベルなし問題をラベル付き問題に還元するための重要なツールである。各ラベルなしクラスは、ラベル付きオブジェクトの対称クラスとみなされる。

ラベルなしグラフの数${\displaystyle n}$頂点数は閉形式の解ではまだ知られていないが、^{[ 6 ]}ほとんどすべてのグラフは非対称であるため、この数は漸近的に^{[ 7 ]となる。}$${\displaystyle {\frac {2^{\tbinom {n}{2}}}{n!}}.}$$

この分野における重要な成果には、以下のようなものがある。

• ラベル付きn頂点単純無向グラフの数は2 ^{n ( n −1)/2}である。^{[ 8 ]}
• ラベル付きn頂点単純有向グラフの数は2 ^{n ( n −1)}である。^{[ 9 ]}
• 連結されたラベル付きn頂点無向グラフの数C _nは、漸化式^{[ 10 ]を満たす。}

${\displaystyle C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.}$

これから、n = 1, 2, 3, ... の場合、 C _nの値は容易 に計算できる。

1、1、4、38、728、26704、1866256、... （OEISのシーケンスA001187）

• ラベル付きn頂点フリーツリーの数はn ^{n −2}（ケイリーの公式）です。
• ラベルのないn頂点の毛虫の数は^{[ 11 ]}

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

さまざまな研究グループが、特定の特性を持つ小規模グラフを一覧表示する検索可能なデータベースを提供している。例えば

• グラフの家
• 小規模グラフデータベース