[Algoritmi] Determinare albero di copertura.
Salve a tutti, sono bloccato in un esercizio sui grafi.
tale per cui sia
La mia idea iniziale è quella di richiamare una procedura che, dato un nodo sorgente, crea un spanning tree e richiama tale procedura per ogni nodo di G, per avere ogni possibile albero. Poi confronta se uno di questi alberi rispetta il fatto che i vertici di U siano tutti foglie. Però non penso sia la procedura più efficiente e mi sembra anche piuttosto costosa in termini di complessità
Qualcuno mi può dare una mano? Grazie mille.
tale per cui sia
Sia G = (V, E) un grafo non orientato e connesso. Sia U ⊆ V un sottoinsieme non vuoto di V . Si consideri il problema di
determinare, se esiste, un albero T di copertura di G in cui tutti i nodi di V \ U siano foglie.
a. Scrivere lo pseudo-codice di un algoritmo efficiente che, dati G e U restituisca T, se esiste, e false altrimenti. Determinare la complessità e dimostrare la correttezza della procedura proposta;
b. Come si può modificare l’algoritmo descritto al punto precedente nel caso in cui G sia pesato e T, oltre a rispettare le
specifiche precedenti, debba essere di peso minimo. Come varia la complessità computazionale
La mia idea iniziale è quella di richiamare una procedura che, dato un nodo sorgente, crea un spanning tree e richiama tale procedura per ogni nodo di G, per avere ogni possibile albero. Poi confronta se uno di questi alberi rispetta il fatto che i vertici di U siano tutti foglie. Però non penso sia la procedura più efficiente e mi sembra anche piuttosto costosa in termini di complessità
Qualcuno mi può dare una mano? Grazie mille.
Risposte
Non ci ho pensato piú di tanto, ma mi è venuta in mente l'idea seguente che può forse esserti utile..
Puoi partire da una foresta di alberi composti dai soli nodi di \(V-U\). Ad ogni iterazione scegli un elemento di \(U\) che unisca due di questi alberi. Devi cioè trovare un elemento di \(U\) che sia connesso ad almeno un nodo di entrambi gli alberi (nota che questo nodo potrebbe fare parte di uno dei due alberi).
Puoi partire da una foresta di alberi composti dai soli nodi di \(V-U\). Ad ogni iterazione scegli un elemento di \(U\) che unisca due di questi alberi. Devi cioè trovare un elemento di \(U\) che sia connesso ad almeno un nodo di entrambi gli alberi (nota che questo nodo potrebbe fare parte di uno dei due alberi).
Ok, ho capito l'idea ma non saprei metterla in pratica. Ad ogni modo mi hai fatto venire un'idea.
Utilizzo la visita BFS a cui aggiungo un controllo: se il nodo della lista di adiacenza che sto scorrendo fa parte dell'insieme U/V (cioè deve essere una foglia), allora lo coloro di grigio, aggiungo distanza e predecessore ma non lo metto nella coda. In questo modo tale nodo non sarà collegato ad altri nodi (eccetto il predecessore) perché non scorro la sua lista di adiacenza. Inoltre risulterà uno spanning tree perché non sarà mai collegato a più di un nodo (creando un ciclo) poiché alla prima visita verrà colorato di grigio e quindi non sarà più preso in considerazione nelle liste di adiacenza seguenti.
Non so se mi sono spiegato; provato sulla carta però mi sembra funzioni.
Utilizzo la visita BFS a cui aggiungo un controllo: se il nodo della lista di adiacenza che sto scorrendo fa parte dell'insieme U/V (cioè deve essere una foglia), allora lo coloro di grigio, aggiungo distanza e predecessore ma non lo metto nella coda. In questo modo tale nodo non sarà collegato ad altri nodi (eccetto il predecessore) perché non scorro la sua lista di adiacenza. Inoltre risulterà uno spanning tree perché non sarà mai collegato a più di un nodo (creando un ciclo) poiché alla prima visita verrà colorato di grigio e quindi non sarà più preso in considerazione nelle liste di adiacenza seguenti.
Non so se mi sono spiegato; provato sulla carta però mi sembra funzioni.
Credo possa funzionare.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo