グラフ内のノードを削除することによって形成できるツリーの数

Question

0 
| 
0__1__0 
| | | 
1__1__0 
    | 
    1 

無向グラフがあるとします。

1. 「1」とラベル付けされたノードのみを削除することができます。任意のノードの

2. 削除グラフ我々は、複数のノードを削除するために許可されている森林

てはならないが、上記の条件が満たされなければなりません。

上記のプロセスで作成できる異なるツリーの数をカウントします（ルーティングされていない）。ここには「ルート」というものはありません。私たちは、異なる構造だけを数えます。私はヘルプやヒントのいずれかの種類をいただければ幸いです

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 

：ため、上記の、答えを

は4です。

（グラフがすでに木である場合には、我々はまだ上記の条件に従う、新しい木を取得するには、ノードを削除することが許可されている）

Answer 1

すでに指摘したように、ナイーブ指数ソリューションをするだろう1ノードのすべてのサブセットを取り、それぞれのノードを削除するとツリーグラフが得られるかどうかを確認します。いくつかのサブセットをどのようにプルーニングすることができるか2つの考え方：

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ノードのみで構成されている場合を除き、これらの1ノードコンポーネントをすべて削除すると有効な解決方法が得られる可能性があります）。

2. ツリーを取得する1ノードのサブセットを見つけたら、さらに1ノードを削除すると、グラフが分割されていない限りツリーが得られます。たとえば、

、Aを除去することによって、私たちは木を取得：

0 
| 
0  0 
|  | 
C__B__0 
    | 
    D 

我々はさらにノードを除去することによって、追加の木を生成することができます。これらを削除することによって、グラフを分割しないことを確認するだけです。そうでない場合は、グラフがツリーのままであることを確認できます。この例のDを削除すると、そのアイデアが示されます。

これらの最適化は、おそらく最悪の場合指数関数よりも優れたアルゴリズムにはなりませんが、合理的に小さな入力に対しては実用的になります。