PDA

Visualizza versione completa : Aiuto Grafi


ciccio2077
22-05-2001, 23.56.03
Salve a tutti!Vorrei sottoporvi un tema molto interessante, e cioè l'implementazione di Grafi.Se possibile, sarei felice se qualcuno potesse darmi un aiuto con i seguenti quesiti:

1. Descrivere un algoritmo che preso in Input un grafo diretto, pesato e connesso G trova un albero di copertura di G di Peso Massimo. Discutere la correttezza dell’algoritmo proposto.
2. Modificare l’algoritmo di Dijkstra in modo tale che, per ogni nodo u, calcola il cammino minimo (rispetto alla somma dei pesi degli archi) da s ad u con il minor numero di archi.
3. Descrivere un algoritmo che preso in input un grafo diretto e pesato G (senza cicli di peso negativo) e un albero di copertura T di G radicato in un nodo s, determina se T è o meno un albero dei cammini minimi con sorgente s per G. L’algoritmo deve avere complessità O(n+m) dove n è il numero di nodi ed m il numero degli archi di G.
4. Descrivere in pseudo-codice un algoritmo efficiente che dato un grafo diretto G trova un insieme di nodi che induce un sottografo completo massimale di G. Un sottografo completo è massimale se non è contenuto in nessun altro sottografo completo.
5. Come è noto l’algoritmo di Dijkstra, dato un grafo diretto G con pesi positivi e un nodo s, calcola i cammini minimi(cioè, di peso minimo) da s a tutti gli altri nodi di G. In generale, tra s e un altro nodo ci può essere più di un cammino minimo. Modificare l’algoritmo di Dijkstra per calcolare i cammini minimi con il minor numero di archi, Cioè, per ogni nodo u l’algoritmo modificato deve determinare il cammino minimo da s ad u che tra tutti i cammini minimi da s ad u è quello con il minor numero di archi.
6. Si deve calcolare il minimo albero di copertura per grafi con pesi appartenenti all’insieme{1,2,………k}, dove k è un intero fissato. Descrivere una implementazione dell’algoritmo di Prim che sfruttando la particolarità di questi grafi calcola il minimo albero di copertura in O(k*n + m), dove n è il numero dei nodi ed m è il numero degli archi.
7. Descrivere in pseudo-codice un algoritmo efficiente che dato un grafo non diretto G trova un accoppiamento massimale di G. Un accoppiamento è un qualsiasi insieme di archi disgiunti(cioè, due archi dell’accoppiamento non possono avere nodi in comune). Un accoppiamento si dice massimale se non è contenuto in nessun’altro accoppiamento.
8. Modificare l’algoritmo di Knuth Morris e Pratt in modo tale che date due stringhe T ed S trova la lunghezza del più lungo prefisso di S che occorre in T.
9. Modificare l’algoritmo di Prim per trovare dato un grafo non diretto con pesi positivi, un albero di copertura il cui prodotto dei pesi degli archi è massimo.



Grazie e ciao!!

quipo.it
23-05-2001, 10.38.15
Ehm... Cormen, Leiserson, Rivest, "Introduzione agli algoritmi"? :D :D

verloc
25-05-2001, 20.40.11
Hey?Mica sei un collega?Io l'algoritmo di D. l'ho studiato

a Tecnica ed Economia dei Trasporti.Anzi no, a Sistemi di Esercizio dei Trasporti.Se mi dai qualche sito dove trattano
questo tipo di algoritmi,potrebbe essere interessante ripolverare certe cose(non mi ricordo un cacchio dell'esame).Grazie