Esame 1617
Tradotto da
ScribdTranslationsEsame 1617
Tradotto da
ScribdTranslationsUniversità Hassiba Benbouali di Chlef Durata: 1h30
Facoltà delle scienze
Dipartimento di informatica
Esame TG L2- 2017
Esercizio 1. (5 pt)
Mostrare che ogni albero è un grafo bipartito.
Sia T=(V,E) un albero, mostra che |V|=|E|+1.
Esercizio2. (5 pts)
Una compagnia di sviluppo software deve lavorare su tre progetti P1, P2 e P3 nel
4 mesi prossimi. P1 può iniziare solo dopo il primo mese e deve concludersi prima
la fine del terzo mese. P2 e P3 possono iniziare il primo mese e devono finire,
rispettivamente, prima della fine del quarto e del secondo mese.
I progetti richiedono, rispettivamente un volume di, 8, 10 e 12 ingegneri/mese. Ogni mese 8
gli ingegneri sono disponibili. A causa della struttura interna della compagnia, non più di 6
ingegneri possono lavorare, contemporaneamente, sullo stesso progetto.
1. Descrivere come questo problema si riduce a un problema di massimo flusso.
2. Determinare se è possibile completare i tre progetti entro le scadenze richieste.
Esercizio3. (5 pts)
Sia il grafo G qui sotto che rappresenta il piano di uno zoo. Il vertice A rappresenta l'accesso e i
Altri picchi sono i diversi siti animali. Un'arista rappresenta un sentiero (un cammino)
ponderato per la distanza (in metri) tra i due settori. Per pulire i vialetti, una spazzatrice
l'automobile è utilizzata.
1. È possibile che questo spazzamento non percorra ogni viale solo una volta e nient'altro? Se sì,
descrivere il percorso corrispondente.
2. I servizi di sicurezza situati nel settore A devono intervenire nel settore H. Utilizzando
L'algoritmo di Dijkstra, determinare il percorso più breve per arrivarci e dare la sua lunghezza.
AB AC AD AE BC BD BE CD CH DE DF DG EF FH GH
50 300 150 150 200 150 200 100 250 100 100 200 150 250 150
B
A
C
G
E
H
F
Esercizio 4. (5 pt)
L'università di Chlef avvia un progetto che richiede la realizzazione delle attività individuate da
lettereAàIet le cui caratteristiche sono le seguenti:
Compito Precedenza Durata
A - 4 giorni
B - 2 giorni
C A 2 giorni
D B ¼ giorni
E F 3 giorni
F - 1,5 giorni
G C 2,5 giorni
H E 10 giorni
Io G, H 1,5 giorni
Disegnare la rete PERT corrispondente
Determina una durata totale minima di ristrutturazione e il cammino critico in questo grafo.