Esercitazione, Ricerca operativa

Name: Esercitazione, Ricerca operativa
Rating: 4.0 (3 reviews)
Author: Simo'93

Revisionato il 09/09/2026

di Simo'93

Publisher

Vota 4,0/5 (3)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Esercizi svolti passo-passo sul minimo albero ricoprente per l'esame di Ricerca operativa del professor Giordani. Sono stati svolti con l'algoritmo di Prim e di Kruskal. Per ogni soluzione …

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. Giordani Stefano

Università Università degli Studi di Roma Tor Vergata

A.A. 2014-2015

36 pagine

3 download

Esercitazione

Scarica

Estratto del documento

Prim

i ∈ V ∅ 1° 2° 3° 4° 5° 1 * 2 5; 1 * 3 7; 1 5; 5 * 4 6; 1 5; 3 * 5 4; 2 * 6 7; 5 6; 3 *

costo totale = 32

Prim

C_EV

Iterazioni

1^o

2^o

3^o

4^o

5^o

5; 1

7; 1

5; 5

6; 1

5; 3

4; 2

7; 5

6; 3

Costo totale = 32

1/36

Kruskal

(1, 2) = 5
(1, 3) = 7
(1, 4) = 6
(2, 5) = 4
(3, 4) = 5
(3, 5) = 5
(3, 6) = 6
(4, 6) = 8
(5, 6) = 7

Ordinamento iniziale e costi non decrescenti:

✓ (2, 5) = 4
✓ (1, 2) = 5
✓ (3, 4) = 5
✓ (3, 5) = 5
✗ (1, 4) = 6
✓ (3, 6) = 6
✗ (1, 3) = 7
✗ (5, 6) = 7
✗ (4, 6) = 8

Componenti non banali

(i, j)

(2, 5) {2, 5}
(1, 2) {1, 2, 5}
(3, 4) {1, 2, 5}, {3, 4}
(3, 5) {1, 2, 3, 4, 5}
ciclo! (1, 4) {4, 2, 3, 4, 5}
(3, 6) {1, 2, 3, 4, 5, 6}
ciclo! (1, 3)
ciclo! (5, 6)
ciclo! (4, 6)

Costo totale & minimo albero ricoprente = 32

Condizioni di ottimalita' cicli:

C₃₃ ≥ C₄₂, C₂₅, C₃₅
7 ≥ 5, 4, 5 ✓

C₄₃ ≥ C₂₁, C₂₅, C₃₅, C₃₁
6 ≥ 5, 4, 5, 5

C₄₁ ≥ C₇, C₃₁, C₃₆
8 ≥ 7, 5, 6 ✓

C₅₆ ≥ C₃₅, C₃₆
7 ≥ 5, 6 ✓

L'albero ricopertura e' ottimo.

Condizioni di ottimalita' sui tagli:

C_1,2 ≤ C₄₃, C₄₁
5 ≤ 7, 6 ✓

C_4,3 ≤ C₄₁, C_4,6
5 ≤ 6, 8 ✓

C₆₃ ≤ C_4,6, C₆₅
6 ≤ 8, 7 ✓

C₂₅ ≤ C_4,1, C_4,4
4 ≤ 7, 6

C₃₅ ≤ C_4,1, C₄₃, C₅₆
5 ≤ 6, 7, 7 ✓

L'albero "tagli" e' ottimo.

3/36

Prim

Iterazioni

A: *
B: 4; A *
C: 3; D *
D: 2; A *
E: 6; A *

Costo: 15

Kruskel

(A, B) = 4
(A, D) = 2
(A, E) = 6
(B, C) = 5
(B, D) = 5
(C, D) = 3
(C, E) = 7

✓ (A, D) = 2
✓ (C, D) = 3
✓ (A, B) = 4
✗ (B, C) = 5
✗ (B, D) = 5
✓ (A, E) = 6
✗ (C, E) = 7

Componenti Connesse Non Banali

(A, D) {A, D}
(C, D) {A, C, D}
(A, B) {A, B, C, D}
(A, E) {A, B, C, D, E}

Costo: 15

5/36

condizioni ottimali c.c.i.

[ C_BD ≤ C_BA ; C_AD

5 7 ; 4 ; 2

[ C_BC ≤ C_AB ; C_AD ; C_BD

5 7 ; 4 ; 2 ; 3

[ C_CE ≤ C_AB ; C_AD ; C_AE

7 7 ; 3 ; 2 ; 6

condizioni ottimali tagli.

[ C_DC ≤ C_CE ; C_BC

3 ≤ 7; 5

[ C_AE ≤ C_CE

6 ≤ 7

[ C_BA ≤ C_BD ; C_BC

4 ≤ 5 ; 5

[ C_AD ≤ C_CE ; C_BD ; C_CB

2 ≤ 7 ; 5 ; 5

L'albero risultante è di costo minimo.

6/36

Prim

i e V 0 1°

Anteprima

Vedrai una selezione di 9 pagine su 36