Problema algoritmi su grafi
Ho bisogno del vostro aiuto visto che non riesco a risolvere il seguente esercizio:
Il testo dice:
Progetta un algoritmo che sia in grado di rimuovere tutti i cicli di un grafo orientato G=(V,E) in tempo O(m+n) ,dove m è il numero di archi ed n è il numero di vertici del grafo. Rimuovere un ciclo significa rimuovere un arco del ciclo . Se ci sono l cicli in G il tuo algoritmo dovrebbe rimuovere solo O(l) archi.
Qualcuno di voi ha qualche idea su come devo procedere???
Vi prego illustratemi i passi per la risoluzione dell'esercizio in modo corretto.
Il testo dice:
Progetta un algoritmo che sia in grado di rimuovere tutti i cicli di un grafo orientato G=(V,E) in tempo O(m+n) ,dove m è il numero di archi ed n è il numero di vertici del grafo. Rimuovere un ciclo significa rimuovere un arco del ciclo . Se ci sono l cicli in G il tuo algoritmo dovrebbe rimuovere solo O(l) archi.
Qualcuno di voi ha qualche idea su come devo procedere???
Vi prego illustratemi i passi per la risoluzione dell'esercizio in modo corretto.
Risposte
Ecco come pensavo di procedere:
allora in pratica sto usando un algoritmo sulla falsa riga dell'ordinamento topologico.
Ricordiamo che l'algoritmo topologico mantiene i gradi entranti dei vertici e li aggiorna man mano che si vanno a cancellare gli archi , e quando il grado entrante di un vertice va a zero , viene messo quel vertice in una lista. Se alla fine il grafo G sulla quale abbiamo effettuato le relative cancellazioni , è diventato vuoto ,allora il grafo è aciclico , altrimenti non lo è e contiene un ciclo.
Io sono proprio partito da questa considerazione ed ho riformulato l'algoritmo come segue:
Allora ho un grafo G=(V,E) con n vertici e m archi. Per evitare di distruggere il grafo G in ingresso , l'algoritmo lavora con una copia G' di G. Inizio analogamente all'ord.topologico , verificando se c'è un vertice u senza archi entranti in G' ,il tutto tramite un ciclo while , così se esiste lo cancello da G' ,visto che non potrà indurre un ciclo poichè non ha archi entranti,
stessa cosa finchè però la condizione non è falsa, in quanto non ho alcun vertice senza alcun arco entrante.
Quindi non saprei come procedere...secondo me ho sbagliato ad usare questo algoritmo, secondo voi come dovrei fare???
vi prego aiutatemi
allora in pratica sto usando un algoritmo sulla falsa riga dell'ordinamento topologico.
Ricordiamo che l'algoritmo topologico mantiene i gradi entranti dei vertici e li aggiorna man mano che si vanno a cancellare gli archi , e quando il grado entrante di un vertice va a zero , viene messo quel vertice in una lista. Se alla fine il grafo G sulla quale abbiamo effettuato le relative cancellazioni , è diventato vuoto ,allora il grafo è aciclico , altrimenti non lo è e contiene un ciclo.
Io sono proprio partito da questa considerazione ed ho riformulato l'algoritmo come segue:
Allora ho un grafo G=(V,E) con n vertici e m archi. Per evitare di distruggere il grafo G in ingresso , l'algoritmo lavora con una copia G' di G. Inizio analogamente all'ord.topologico , verificando se c'è un vertice u senza archi entranti in G' ,il tutto tramite un ciclo while , così se esiste lo cancello da G' ,visto che non potrà indurre un ciclo poichè non ha archi entranti,
stessa cosa finchè però la condizione non è falsa, in quanto non ho alcun vertice senza alcun arco entrante.
Quindi non saprei come procedere...secondo me ho sbagliato ad usare questo algoritmo, secondo voi come dovrei fare???
vi prego aiutatemi
Ora invece stavo pensando che la soluzione sarebbe una visita DFS , ma non so come applicarla....
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo