Scribd
Carica
4 visualizzazioni2 pagine

Esame

Il documento è un esame di Ricerca Operativa per la Scuola Superiore di Informatica, con esercizi che richiedono l'applicazione di vari algoritmi sui grafi, come BFS, DFS, Prim e Dijkstra. Gli studenti devono calcolare densità, somma dei gradi, costruire alberi di copertura minima e analizzare proprietà dei grafi come la semi-eulerianità e la presenza di cicli. Inoltre, si richiede di eseguire operazioni su matrici di adiacenza e di applicare algoritmi di colorazione e di Bellman-Ford.

Tradotto da

ScribdTranslations
Copyright
© All Rights Reserved
Per noi i diritti sui contenuti sono una cosa seria. Se sospetti che questo contenuto sia tuo, rivendicalo qui.
Formati disponibili
Scarica in formato PDF, TXT o leggi online su Scribd
4 visualizzazioni2 pagine

Esame

Il documento è un esame di Ricerca Operativa per la Scuola Superiore di Informatica, con esercizi che richiedono l'applicazione di vari algoritmi sui grafi, come BFS, DFS, Prim e Dijkstra. Gli studenti devono calcolare densità, somma dei gradi, costruire alberi di copertura minima e analizzare proprietà dei grafi come la semi-eulerianità e la presenza di cicli. Inoltre, si richiede di eseguire operazioni su matrici di adiacenza e di applicare algoritmi di colorazione e di Bellman-Ford.

Tradotto da

ScribdTranslations
Copyright
© All Rights Reserved
Per noi i diritti sui contenuti sono una cosa seria. Se sospetti che questo contenuto sia tuo, rivendicalo qui.
Formati disponibili
Scarica in formato PDF, TXT o leggi online su Scribd

Scuola Superiore di Informatica ‫ﻱﻝﺍﻝ ﻡﻝﻉﻝﻝ ﻳﺎﻝﻉﺍﻝ ﺩﺭﺳﺔﻡﺍﻝ‬

Sidi Bel Abbes ‫ﺱﺍﺏﻉﻝﺏﻱﺩﻱﺱ‬

Modulo: Ricerca Operativa


Durata: 02 h 00

ESAME 01
21/11/2018

Esercizio 01 : (4,5 pt)


NB: Per questo esercizio, rispettare l'ordine crescente dei vertici quando si tratta di fare una scelta.

Dato il grafo G rappresentato qui accanto:


1 – Applicare l'algoritmo di ricerca in ampiezza BFS (1 pt)
2– Applicare l'algoritmo di ricerca in profondità DFS(1pt)
3 – Qual è la densità di questo grafo? (0,5 pt) E qual è la
somma dei suoi gradi? (0,5 pt)
4 –Disegnare S il sottografo di G generato dai vertici:
5,7,8,6,9, 11,10(0,5 pts) et P un grafo parziale di G che garantisce un
grado 2 per ogni vertice. (0,5 pt)
5- Questo grafo è semi-euleriano? Giustifica la tua risposta.
risposta(0,5 pt).

Esercizio 02 : (05 pts)


Dato il grafo G non orientato pesato seguente:
1 - Prendendo come punto di partenza il vertice 0,
Applicare l'algoritmo di Prim per costruire l'albero
coprendo minimo(2pt). Dare il peso di questo albero(0,5pt).
2- Dare il codice di Prüfer dell'ACPM ritrovato a
domanda precedente(1 pt).
3– Se i lati di questo grafo esprimono una relazione
d'incompatibilità, proporre una colorazione del grafo in
utilizzando l'algoritmo Welsh e Powell (1,5 pt).

Esercizio 03 : (3,5 pts)


1 - Disegna il grafo G che ammette come matrice di adiacenza
la matrice M :(0,25 pt)

2- a -Calcola (prodotto non booleano) M² , M3, poi M+M² .(1,5 pt)


b - Cosa significa la presenza di 0 nella posizione (i,j) nella matrice M3(0,25 pt)
c - Que signifie la présence de 0 à la position (i,j) dans la matrice M+M²(0,25 pt)
3 - Quanti percorsi ci sono di lunghezza 2 che portano da 1 a 2? Da 2 a 4? (0,5 pt)
4 - Quanti ci sono percorsi di lunghezza ≤ 2 che portano da 1 a 2? Da 2 a 4? (0,5 pt)
5 - Come rilevare la presenza di un ciclo attraverso la chiusura transitiva? (0,25 pt)

NB: la chiarezza e la leggibilità delle risposte sono valutate su 01 pt.


Scuola Superiore di Informatica ‫ﻱﻝﺍﻝ ﻡﻝﻉﻝﻝ ﻳﺎﻝﻉﺍﻝ ﺩﺭﺳﺔﻡﺍﻝ‬
Sidi Bel Abbes ‫ﺱﺍﺏﻉﻝﺏﻱﺩﻱﺱ‬

Modulo: Ricerca Operazionale


Durata: 02 h 00

Esercizio 04: (6 pt)


Dato il grafo orientato e pesato seguente:

1. Utilizzare l'algoritmo di Dijkstra per calcolare i più


corti percorsi provenienti da a.(2,5 pts). Elenca tutti questi
percorsi così come le distanze corrispondenti.(0,5 pt)
2. La lunghezza dell'arco ge è in effetti -8. Usa questa volta
l'algoritmo di Bellman-Ford per trovare i più
corti sentieri provenienti da a. Si tratteranno gli archi secondo
l'ordine alfabetico.(2,5 pts)
3. Una seconda modifica avviene, la lunghezza dell'arco
fh est maintenant de 1 (la longueur de ge est toujours -8). Peut on relancer l’algorithme de Bellman-
Ford. Giustifica la tua risposta. (0,5 pts)

NB: la chiarezza e la leggibilità delle risposte sono valutate su 01 pt.

Potrebbero piacerti anche