Numero di alberi che possono essere formati eliminando nodi in un grafico

Question

0 
| 
0__1__0 
| | | 
1__1__0 
    | 
    1 

Diciamo che ho un grafico non orientato. Abbiamo queste condizioni:

1. È possibile eliminare solo i nodi etichettati come "1".

2. cancellazione di qualsiasi nodo non deve fare il grafico di una foresta

c'è permesso di eliminare più nodi, ma le condizioni devono essere soddisfatte.

Contare il numero di diversi alberi (senza radici) che è possibile eseguire con il processo sopra. Nota che non esiste una cosa come 'root' qui. Contiamo solo le diverse strutture.

Per quanto sopra, la risposta è 4 perché:

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 

Gradirei qualsiasi tipo di aiuto o suggerimenti.

(Nel caso in cui il grafico è già un albero, stiamo ancora permesso di eliminare i nodi per ottenere nuovi alberi, fatte salve le condizioni di cui sopra)

Answer 1

Come si è già sottolineato, una soluzione esponenziale semplice sarebbe quello di prendi tutti i sottoinsiemi dei nodi 1 e per ciascuno, controllando che la rimozione dei nodi ottenga un grafico ad albero. Due pensieri su come potare alcuni dei sottoinsiemi:

1. Creare i sottoinsiemi a 1 nodo in modo incrementale dal più piccolo al più grande. Se ne trovi uno che partiziona il grafico, non è necessario controllare alcuno dei suoi superset.

Permettetemi di indicare la 1-nodi nel tuo esempio A, B, C, D:

0 
| 
0__A__0 
| | | 
C__B__0 
    | 
    D 

Rimozione {A, B} partizioni del grafico. Pertanto, la rimozione evidente di {A, B, C} o {A, B, D} o {A, B, C, D} divide anche il grafico. Non è necessario controllare esplicitamente nessuno di questi.

(A meno che tutti i componenti del grafico partizionato tranne uno siano costituiti esclusivamente da 1 nodo.) La rimozione di tutti questi componenti a 1 nodo potrebbe anche ottenere una soluzione valida. Potrebbe essere necessario controllare questo caso speciale.)

2. Una volta trovato un sottoinsieme a 1 nodo che ottiene un albero; quindi rimuovendo ogni ulteriore nodo 1 otterrà anche un albero purché il grafico non sia partizionato.

Per esempio, rimuovendo A otteniamo un albero:

0 
| 
0  0 
|  | 
C__B__0 
    | 
    D 

possiamo generare ulteriori alberi, eliminando ulteriori nodi. Per questi abbiamo solo bisogno di controllare che rimuovendoli non partizioniamo il grafico. In caso contrario, possiamo essere sicuri che il grafico resti un albero. La rimozione di D in questo esempio illustra l'idea.

Queste ottimizzazioni probabilmente non renderanno l'algoritmo migliore di quello esponenziale nel caso peggiore, ma potrebbero renderlo pratico per input ragionevolmente piccoli.