Sto facendo la mia ricerca e mi sono bloccato con una domanda:
Sto avendo uno spanning tree minimo (algoritmo prim), ora viene eliminato un nodo nel mio albero, mi chiedo se c'è un modo in cui posso riorganizzare il mio albero in modo che l'ottimalità mantenga ancora?
Sto cercando alcuni suggerimenti qui e apprezzerò il tuo aiuto.
Grazie!
Nota: tutti i pesi dei bordi sono 1 (grafico unitario)
Se tutti i pesi degli spigoli sono 1, qualsiasi albero spanning è un albero spanning minimo. Quindi possiamo dimenticare il fatto che vogliamo un albero di spanning minimo e concentrarsi solo su spanning tree.
Questo significa che usare l'algoritmo di prim per costruire l'albero originale è uno spreco. L'algoritmo di Prim richiede di aggiungere il minimo peso ad ogni passaggio. Ma dal momento che tutti i pesi sono gli stessi, non importa quale bordo si aggiunge finché il bordo non causa un ciclo.
Se rimuoviamo un nodo, ci sono due possibilità. Se il nodo era una foglia sull'albero, il nuovo albero continuerà a coprire l'intero grafico. In tal caso abbiamo finito. Altrimenti finiamo con due alberi. Potrebbe essere che il grafico sia ora disconnesso in cui non esiste alcun albero spanning. Supponendo che il grafico sia connesso, allora aggiungendo qualsiasi spigolo alla struttura ad albero che collega due alberi funzionerà.
Se rimuovi un vertice dal tuo grafico (che è un MST) potresti non essere necessariamente lasciato con un albero:
Se il vertice che rimuovi è un taglio vertice il tuo grafico verrà disconnesso e non più un albero.
Se la rimozione di un vertice lascia collegato il tuo grafico, poiché hai dichiarato che tutti i pesi dei bordi sono uguali, rimarrà un MST. Qualsiasi albero spanning di un grafico con lo stesso peso del bordo è uno spanning tree minimo.
Leggi altre domande sui tag algorithms