连通图的计数

Question

我试着用K来计算简单连通图的个数 边和N个明显标记的顶点。我在下面写了这段代码，但它似乎不起作用。在

这种图没有孤立的顶点，所以我 对N个顶点和K个边执行此操作。在

Connected(N,K):
1) Total = all possible graphs, including disconnected ones.
2) Disconnected = Sum from i=1 to i=N-1 [(Connected(i,K)*(number of ways to
    choose i vertices from all N vertices)]
3) return Total-Disconnected

Python代码：

^{pr2}$

Answer 1

你的断开连接公式实际上是不正确的。在

我们将顶点标记为1，2，…，N。在公式中，项：

[（已连接（i，K）*（从所有N个顶点中选择i个顶点的方法数）]

假设计算图的个数，使顶点1的连通分量包含i个顶点。但是这个产品只给出了可能连接的组件的数量。对于每一个这样的连接组件的选择，仍然有很多方法来安排其余（N-i）顶点之间的边。在

为了得到正确的公式，还应考虑连接构件中的边数。在

设Conn（i，j）是具有i标记顶点和j条边的连通图的个数。然后我们有：

choose（N*（N-1）/2，K）=和（i=1到N，j=0到K）choose（N-1，i-1）*Conn（i，j）*choose（（N-i）*（N-i-1）/2，K-j）

左边是有N个顶点和K个边的图的总数。右边的和是有N个顶点，K个边的图的个数，并且顶点1的连通分量有i个顶点和j个边。在

对求和的进一步解释：首先从除顶点1以外的N-1顶点中选择i-1顶点，然后乘以与i顶点和j边形成连通图的方法数，最后从剩余的N-i顶点中添加任何K-j边。在

从这个公式你应该能够写一个DP算法来计算所有的Conn（i，j）。在

虽然这可能很慢，但它会给你正确的答案。你可以稍后考虑更好的算法。在