图的似然性

简单图的似然性定义为从集合 开始。然后迭代以下过程以产生阶数为 的图的集合 。在步骤 中，从集合 中随机选择一个整数 。现在随机选择 中的一个图（保持其在步骤 中构建的概率），并从中添加一个新的顶点，该顶点连接到其现有顶点的 个随机选择的所有顶点。现在合并此过程产生的任何同构图，方法是将其概率相加。则 在 个顶点上的图的似然性定义为 出现在 中的概率。

此过程的第 次迭代产生 个节点上的每个可能的图。上面说明了 到 4 个节点的图的结果。E. Weisstein（2013 年 12 月 23 日）已经计算了最多 10 个节点的所有简单图的似然性。

，其中 是 图的补图 。 和 因此是同等可能的。

由于这些值是概率，因此所有 节点图的似然性之和为 1，并且单个似然性满足

其中 仅对 成立。 也满足更强的不等式

其中 是 图的自同构群 的阶数 (Banerji et al. 2014)。

下表总结了许多特殊类别的成员的似然性。

具有已知闭式值的类别包括

其中 是一个 完全图， 是一个 空图， 是一个 星图， 是一个 梯子横档图， 是一个 阶乘，并且 是一个 次阶乘。此外，循环图 的 和 路径图 的 之间存在关系，由下式给出

(Banerji et al. 2014)。

一般来说，具有 个顶点和 个孤立边的图的似然性为

给出特殊情况

其中 是一个 调和数。

上面绘制了 对于 节点图的值。

对于 的所有值，除了 、3 和 5（对于它们，最小值分别出现在 、 和 时）， 的最小值出现在 完全二部图 及其 图的补图。对于 ，, 2, ... 的最小值分别为 1, 1/2, 1/6, 1/36, 1/270, 23/259200, 319/54432000, 319/15240960000, ... (OEIS A234234 和 A234235)。

最大值 作为 的函数的情况不太清楚，对于 , 2, ...，最大值出现在 、、、爪形图、镖形图、... 及其补图。相应的最大值是 1, 1/2, 1/3, 13/72, 307/4320, 1927/86400, 39211/6804000, 27797639/22861440000, ... (OEIS A234236 和 A234237)。