我有个问题。我正在尝试计算图中的所有生成树（它没有多重边）。我知道有基尔霍夫定理，它让我可以很容易地计算它，但我更喜欢在此图中使用循环的解决方案。
我试图弄清楚循环如何影响生成树的数量，我发现当有一个循环（没有额外的边）时，我们可以简单地删除其中一个边，我们将得到一棵生成树。当有 n 个循环仅由一个节点连接时，我们可以将每个循环中的边数相乘，这就是我们的结果。问题是当两个循环与多个节点（例如 1 或 3 条边）连接时。我试图写一个等式，它可以让我计算这个数字，我唯一得到的是c1*c2-s^2，其中 c1 是循环 nr 的大小。1，c2是循环nr.2的大小，s是它们的公共边的数量。但是在某些情况下它不起作用。我在下面附上一个例子：完整的图表
我们知道一个完整图中的生成树的数量是n^(n-2)，所以我们知道它有16个可能的生成树。但是我的算法找到了其中的 20 个。原因如下：
我发现 3 个周期：(3,4,2),(4,2,1) 和 (3,4,2,1)。然后我只是将我的方程用于循环 nr 1 和 2 (3* 3-1)，它给了我 8，最后我在最后一个循环中再使用一次（8*3-4 [它有 2 个常见的edge]) 这给了我 20。我还必须补充一点，我的循环查找算法并不总能找到一个简单的循环。
有人可以告诉我错误在哪里，以及如何解决吗？提前致谢。