计算包含特定边缘的跨越树的总数

Question

我尝试了以下方法：

首先，我对给定边缘中所有边缘的所有边缘进行边缘收缩，以形成修改的图形。

然后，我从修改的图中使用矩阵树定理来计算跨越树的总数。

我想知道此方法是否正确以及是否还有其他更好的方法。

Answer 1

令G为图形，让E为边缘，然后g/e与e缩合在一起的图形相同。然后，

命题：含有E的G的跨树木与G/E的跨越树之间有一份生物。

这个主张不难证明。您最好自己理解证明，而不是仅仅问别人是否正确。显然，如果您有一个包含e的g树，则T/e是g/e的跨度树。要考虑的是您也可以向后走。

而且，正如亚当指出的那样，您必须小心地正确处理带有从顶点到自身的边缘的平行边缘和图形的图形。

Answer 2

我不知道这是否正确，但是您必须注意边缘收缩可能导致平行边缘的事实。您必须确保仅使用平行边缘的树木与众不同。