グラフ列挙

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

いくつかのグラフィカル列挙問題では、グラフの頂点は互いに区別できるようにラベルが付けられていると見なされますが、他の問題では、頂点の任意の順列は同じグラフを形成すると見なされるため、頂点は同一またはラベルなしと見なされます。一般に、ラベル付きの問題はより容易な傾向があります。^[5]より一般的な組み合わせ列挙と同様に、ポリア列挙定理は、ラベルなしの問題をラベル付きの問題に縮小するための重要なツールです。ラベルなしのクラスはそれぞれ、ラベル付きオブジェクトの対称クラスと見なされます。

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

この分野における重要な成果としては、以下のものが挙げられます。

• ラベル付きn頂点単純無向グラフの数は^{2n ( n  −1)/2}である。^[8]
• ラベル付きn頂点単純有向グラフの数は^{2n ( 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^{nk \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 }.}$

さまざまな研究グループが、小さなサイズの特定の特性を持つグラフをリストした検索可能なデータベースを提供しています。たとえば、

• グラフの家
• 小さなグラフデータベース