Esercitazione, Ricerca operativa

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

Revisionato il 21/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

Prima: iterazioni

i	E	V	0	1^o	2^o
1	*
2	5; 1	*
3	7; 1		5; 5	*
4	6; 1			5; 3	*
5		4; 2	*
6		7; 5	6; 3		*

Costo totale = 321/36

Prima: iterazioni

i	E	V	0
1	*
2	5; 1	*
3	7; 1	5; 5	*
4	6; 1	5; 3	*
5	4; 2	*
6	7; 5	6; 3	*

Costo totale = 321/36

Kruskal

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

Ordinamento in ordine di 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

(i,j) componenti non banali

(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)
(3,6) {1,2,3,4,5,6}
Ciclo! (1,3)
Ciclo! (5,6)
Ciclo! (4,6)

Costo totale minimo dell'albero ricoperto = 322/36

Condizioni ottimalità del ciclo

c₁₃ >= c₁₂, c₂₅, c₃₅

7 > 5, 4, 5

c₁₄ >= c₁₁, c₂₅, c₃₅, c₃₄

6 > 5, 4, 5, 5

c_4,6 >= c₃₄, c₃₆

8 > 5, 6

c₅₆ >= c₃₅, c₃₆

7 > 5, 6

L'albero ricercato è ottimo.

Condizioni ottimalità sui tagli

c_1,2 < c₁₃, c₁₄

5 < 7, 6

c_4,3 < c₁₄, c_4,6

5 < 6, 8

c_6,3 < c₄₆, c₆₅

6 < 8, 7

c₂₅ < c₁₃, c₁₄

4 < 7, 6

c₃₅ < c₁₄, c₁₃, c₅₆

5 < 6, 7, 7

L'albero ricercato è ottimo.

3/36

Prim: iterazioni

i	c	v
A	*
B	4; A	*
C	3; D	*
D	2; A	*
E	6; A	*

Costo: 15

Kruskal

(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

(i,j) componenti connesse non banali

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

Costo: 15

5/36

Condizioni ottimalità cicli

c_BD > c_BA ; c_AD

5 > 4 ; 2

c_BC > c_BA ; c_AD ; c_DC

5 > 4 ; 2 ; 3

c_CE > c_CD ; c_DA ; c_AE

7 > 3 ; 2 ; 6

L'albero ricoperto è di costo minimo.

Condizioni ottimalità 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 ricoperto è di costo minimo.

6/36

Prima: iterazioni

i e V A B C D E F

Costo: 5

7/36

Kruskal

(A,B) = 1
(A,E) = 1
(A,F) = 1
(B,C) = 1
(B,F) = 3
(C,D) = 1
(C,F) = 4
(D,E) = 1
(D,F) = 5
(E,F) = 6

(A,B) = 1
(A,E) = 1
(A,F) = 1
(B,C) = 1
(C,D) = 1
(D,E) = 1
(B,F) = 3
(C,F) = 4
(D,F) = 5
(E,F) = 6

8/36

(i,j) componenti connesse non banali

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

Costo: 5

9/36

Condizioni ott

Anteprima

Vedrai una selezione di 9 pagine su 36