Ricerca di uno spanning tree che riduca al minimo la somma delle profondità dei nodi

Question

Ho un grafico collegato non orientato con i bordi non pesati. Come posso costruire uno spanning tree (la soluzione potrebbe non essere unica) in modo tale che la somma delle profondità di tutti i nodi sia ridotta al minimo? Ovviamente, questo non sta trovando l'albero di copertura minimo, poiché il "peso" dei bordi varia in realtà in base alla profondità del bambino.

Penso che, data una radice designata, l'albero con la somma minima di profondità possa essere formato collegando avidamente tutto ciò che è possibile collegare come bambini, a ciascun nodo in un ordine di ampiezza. Pertanto, troverò l'albero con profondità totale minima applicando la stessa procedura N volte, designando ciascuno dei nodi N come root e scegliendo il minimo tra i N candidati. È un algoritmo valido? Per favore, fai notare se è sbagliato o se esiste qualcosa di più efficiente.

Answer 1

È un algoritmo valido?

Sì, l'algoritmo è corretto.

Dato un nodo R che è da considerarsi la radice dell'albero attraversa, la profondità di un nodo N nel albero ricoprente è almeno la lunghezza del percorso più breve da R al N nel grafico, quindi la somma delle profondità è almeno la somma delle lunghezze dei percorsi più brevi (da R).

L'albero costruito dall'algoritmo collega ogni nodo di R con uno dei percorsi più brevi, in modo che la somma delle profondità è la somma delle distanze, che abbiamo visto sopra è un limite inferiore.

Come piccola ottimizzazione, se il numero di nodi è almeno 3, nessun nodo con grado 1 deve essere considerato come la radice dell'albero. (Per un albero radicato in un nodo R con grado 1, considerare lo stesso grafico, visualizzato come un albero radicato al livello R. La profondità di R aumenta di 1, la profondità di tutti gli altri nodi diminuisce di 1, quindi la somma di profondità diminuisce di number_of_nodes - 2.)