Liczba drzew, które można utworzyć przez usunięcie węzłów na wykresie

Question

0 
| 
0__1__0 
| | | 
1__1__0 
    | 
    1 

Załóżmy, że mam nieukierunkowany wykres. Mamy następujące warunki:

1. Można kasować tylko węzły oznaczone jako "1".

2. Usunięcie dowolnego węzła nie może sprawić, że wykres las

Wolno nam usunąć wiele węzłów, ale powyższe warunki muszą być spełnione.

Policz liczbę różnych drzewek (nieużywanych), które można wykonać w powyższym procesie. Zauważ, że nie ma tutaj czegoś takiego jak "root". Liczymy tylko różne struktury.

Dla powyższego, odpowiedź wynosi 4, ponieważ:

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 

Będę wdzięczny za każdą pomoc i podpowiedzi.

(W przypadku, gdy wykres jest już drzewem, wciąż wolno usuwać węzły, aby uzyskać nowe drzewa, z zastrzeżeniem powyższych warunków)

Answer 1

Jak już wspomniano, naiwne rozwiązanie wykładniczy byłoby weź wszystkie podzbiory 1-węzłów i dla każdego, sprawdzając, czy usunięcie węzłów daje wykres drzewa. Dwie myśli, jak można przycinać niektóre podzbiory:

1. Zbuduj podzbiory jednego węzła przyrostowo od najmniejszego do największego. Jeśli znajdziesz taki, który dzieli wykres, nie musisz sprawdzać żadnego z jego supersetów.

Pozwól oznaczać 1-węzłów w przykładzie A, B, C, D:

0 
| 
0__A__0 
| | | 
C__B__0 
    | 
    D 

Usuwanie {A, B} partycje wykresie. Dlatego oczywiście usunięcie lub {A, B, D} lub {A, B, C, D} również dzieli się na wykres. Nie musisz dokładnie sprawdzać żadnego z nich.

(O ile wszystkie komponenty graficzne z jednym podziałem nie składają się wyłącznie z 1-węzłów, a następnie usunięcie wszystkich tych komponentów z jednym węzłem może również uzyskać prawidłowe rozwiązanie.) Może być konieczne sprawdzenie tego jako specjalnego przypadku.)

2. Po znalezieniu podzestawu z 1 węzłem, który zyskuje drzewo; następnie usunięcie dowolnego kolejnego węzła 1 spowoduje również uzyskanie drzewa, o ile wykres nie jest podzielony na partycje.

Na przykład, poprzez usunięcie A otrzymujemy drzewa:

0 
| 
0  0 
|  | 
C__B__0 
    | 
    D 

Możemy generować dodatkowych drzew przez usunięcie kolejnych węzłów. W tym celu musimy tylko sprawdzić, czy usuwając je nie podzielimy wykresu. Jeśli nie, możemy być pewni, że wykres pozostaje drzewem. Usunięcie D w tym przykładzie ilustruje ideę.

Te optymalizacje prawdopodobnie nie uczynią algorytmu lepszym niż wykładniczy w najgorszym przypadku, ale mogą sprawić, że będzie on praktyczny dla względnie małych danych wejściowych.