通过删除图中的节点可以形成的树数

Question

0
|
0__1__0
|  |  |
1__1__0
   |
   1

假设我有一个无向图.我们有这些条件:

1. 您只能删除标记为"1"的节点.

2. 删除任何节点都不能使图形成为林

我们被允许删除多个节点,但必须满足上述条件.

计算上述过程可以生成的不同树(无根)的数量.请注意,这里没有"root"这样的东西.我们只计算不同的结构.

对于上述情况,答案是4,因为:

0
|
0     0
|     |
1__1__0        ------> #1
   |
   1

0
|
0     0
|     |        -------> #2
1__1__0


0
|
0__1__0
|     |       ---------> #3
1     0

0
|
0__1__0       ---------> #4
      |
      0

我将不胜感激任何帮助或提示.

(如果图形已经是树,我们仍然可以删除节点以获取新树,但需遵守上述条件)

Answer 1

正如您已经指出的，一个朴素的指数解决方案是获取 1 节点的所有子集，并为每个子集检查删除节点是否会获得树形图。如何修剪一些子集的两个想法：

1. 从最小到最大逐步构建 1 节点子集。如果您找到一个对图进行分区的图，则无需检查其任何超集。

让我表示示例 A、B、C、D 中的 1 节点：

0
|
0__A__0
|  |  |
C__B__0
   |
   D

删除{A, B}图的分区。因此，显然删除{A, B, C}或{A, B, D}也{A, B, C, D}分割了图。您不需要明确检查其中任何一个。

（除非除了一个分区图组件之外的所有组件都仅由 1 节点组成。然后删除所有这些 1 节点组件也可以获得有效的解决方案。您可能需要将其作为特殊情况进行检查。）

2. 一旦找到获得一棵树的 1 节点子集；然后，只要图没有分区，删除任何进一步的 1-节点也将获得一棵树。

例如，通过删除A我们得到一棵树：

0
|
0     0
|     |
C__B__0
   |
   D

我们可以通过删除更多节点来生成更多树。对于这些，我们只需要通过删除它们来检查我们不会对图进行分区。如果不是，我们可以确定该图仍然是一棵树。在这个例子中删除D说明了这个想法。

在最坏的情况下，这些优化可能不会使算法比指数算法更好，但它们可以使其对于相当小的输入变得实用。