Ricerca operativa - Modulo 1 (Teoria dei grafi e reti di flusso)

Teoria dei grafi e reti di flusso

Appunti del primo modulo di Ricerca Operativa, tenuto dal Prof. Stefano Giordani

TGRF // Scritto da Andrea Albanese

2022/23

Ingegneria gestionale 2

Indice

• Capitolo 1 – Introduzione ....................................... 7
• 3.4 - Notazione Big-O: ........................................................ 30
• Criteri e osservazioni per la notazione Big-O ...................... 30
• 1.1 - Cos’è una rete: ............................................................. 7
• 3.5 - Notazioni Big- e Big-: ............................................ 31
• 1.2 - Problemi, modelli e decisioni: ................................... 7
• Notazione Big-: ................................................................. 31
• Problemi decisionali: .............................................................. 7
• Notazione Big-: ................................................................. 31
• 1.3 - Ricerca operativa, definizione e storia: .................. 7
• 3.6 - Complessità di un algoritmo: ................................. 31
• 1.4 - Il metodo delle cinque fasi: ...................................... 8
• 3.7 Classificazione degli algoritmi: ............................... 32
• 1.5 - Approccio modellistico e relative fasi: ................... 8
• 3.8 Algoritmi di ricerca: ................................................... 32
• Fasi dell’approccio modellistico: ............................................ 8
• Algoritmi di ricerca lineare (o sequenziale): ........................ 32
• Costruzione del modello matematico: ................................... 8
• Algoritmo di ricerca binaria: ................................................. 32
• Vantaggi e svantaggi dell’approccio modellistico: ................. 8
• 3.9 Algoritmi di ordinamento: ....................................... 33
• 1.6 - Problema di ottimizzazione (o di programmazione matematica PM): ..................................................................... 8
• Capitolo 4 – Rappresentazioni di reti .................... 35
• Tipologie di problemi di ottimizzazione: ................................ 9
• 4.1 Introduzione: ............................................................... 35
• Espressione esplicita del problema di ottimizzazione: .......... 9
• Formulazione di un problema di ottimizzazione:................... 9
• 4.2 Matrice di incidenza: .................................................. 35
• Classificazione dei problemi di ottimizzazione (PM): ............. 9
• Vertici-spigoli: ...................................................................... 35
• Esempi: ................................................................................ 10
• Nodi-archi: ........................................................................... 35
• 1.7. - Modelli, istanze e algoritmi: .................................. 10
• 4.3 Matrice di adiacenza: ................................................. 36
• Vertici-vertici: ...................................................................... 36
• 1.8 - Storia della teoria dei grafi ed Eulero: ................ 11
• Nodi-nodi: ............................................................................ 36
• Osservazione sul problema dei ponti di Könisberg: ............. 11
• 4.4 Liste degli archi: .......................................................... 37
• Capitolo 2 – Notazioni e definizioni ...................... 13
• Pregi: .................................................................................... 37
• Difetti: .................................................................................. 37
• 2.1 - Grafi e reti: ................................................................. 13
• Massimo numero possibile di archi/spigoli: ........................ 14
• 4.5 Liste di adiacenza: ........................................................ 37
• Definizioni per un digrafo: ................................................... 14
• 4.6 Forward and reverse star representation: .......... 38
• Definizioni per un grafo (non orientato): ............................. 15
• Lemma di Handshaking: ....................................................... 15
• Forward star: ....................................................................... 38
• Reverse star: ........................................................................ 38
• Grafi/digrafi completi: ......................................................... 15
• Passaggio dal digrafo al grafo sottostante: .......................... 16
• 4.7 Comparazione: ............................................................. 39
• 2.2 - Sottografi: ................................................................. 16
• Capitolo 5 – Algoritmi di ricerca ........................... 41
• 2.3 - Fattorizzazione: ........................................................ 17
• 5.1 Introduzione: ............................................................... 41
• 2.4 - Percorsi, sentieri, cammini, circuiti e cicli: ........... 17
• 5.2 Raggiungibilità: ........................................................... 41
• Numero di cammini in un grafo: .......................................... 17
• Scrittura e analisi dell’algoritmo per determinare i nodi raggiungibili da s: ................................................................. 41
• 2.5 - Connessione: .............................................................. 18
• 2.6 - Tagli: ............................................................................ 19
• 5.3 Ricerca in ampiezza e in profondità: ........................ 42
• Ricerca in ampiezza: ............................................................ 42
• 2.7 - Alberi e foreste: ......................................................... 19
• Ricerca in profondità: .......................................................... 43
• Alberi e arborescenze radicati/e: ......................................... 20
• Alberi ricoprenti: .................................................................. 21
• 5.2.1 Raggiungibilità: ........................................................ 43
• Foreste: ................................................................................ 22
• 5.4 Ricerca in ordine inverso: ......................................... 43
• 2.8 - Clique, insiemi stabili e insiemi dominanti: ........... 22
• 5.5 Ordinamento topologico: ........................................ 44
• Clique: .................................................................................. 22
• Lemma 5.1: .......................................................................... 44
• Insiemi stabili: ...................................................................... 23
• Lemma 5.2: .......................................................................... 45
• Insiemi dominanti: ............................................................... 23
• Algoritmo formale di ordinamento topologico: ................... 45
• 2.9 - Grafo complemento: ................................................ 24
• Osservazioni sulla numerazione topologica: ....................... 45
• 2.10 - Insieme ricoprente: ................................................. 25
• Capitolo 6 – Proprietà principali ........................... 47
• 2.11 - Abbinamenti: ............................................................ 26
• 6.1 Isomorfismo: ............................................................... 47
• Condizioni necessarie affinché due grafi e siano ′ adiacenti: ............................................................................. 47
• 2.12 - Colorazione: ............................................................ 27
• 2.13 - Grafi bipartiti: .......................................................... 27
• 6.2 Connessione: ................................................................ 49
• 2.14 - Circuiti e sentieri euleriani: ................................... 28
• Lemma 6.1: .......................................................................... 49
• Lemma 6.2: .......................................................................... 50
• 2.15 - Cicli e cammini hamiltoniani: ................................ 28
• Teorema 6.3: ........................................................................ 50
• Capitolo 3 – Algoritmi e complessità .................... 29
• Lemma 6.4: .......................................................................... 50
• Teorema 6.5: ........................................................................ 51
• 3.1 - Introduzione: ............................................................. 29
• Teorema 6.6: ........................................................................ 51
• Proprietà degli algoritmi: ..................................................... 29
• Teorema di connessione: ..................................................... 51
• 3.2 - Efficienza degli algoritmi: ....................................... 29
• 6.3 Aciclicità: ...................................................................... 51
• Lemma 6.7: .......................................................................... 51
• 3.3 - Dimensione dell’istanza: .......................................... 29
• Teorema 6.8: ........................................................................ 52
• 3
• Teorema di aciclicità: ........................................................... 52
• 8.1 Flusso, distribuzione e divergenza: ......................... 77
• 6.4 Alberi: ............................................................................ 52
• 8.2 Conservazione del flusso: ......................................... 77
• Teorema 6.9: ........................................................................ 52
• 8.3 Circolazione: ................................................................ 77
• Proprietà di un albero: ......................................................... 53
• Teorema 6.10: ...................................................................... 53
• 8.4 Rete di flusso: .............................................................. 78
• Ulteriori proprietà che seguono dal teorema 6.10: ............. 53
• 8.5 Flusso ammissibile: ..................................................... 78
• Corollario 6.11: .................................................................... 53
• Teorema 6.12: ...................................................................... 53
• 8.6 Problema di flusso a costo minimo: ....................... 79
• Formulazione: ...................................................................... 79
• 6.5 Grafi euleriani: ............................................................ 53
• Teorema 6.13: ...................................................................... 53
• 8.7 Problema del percorso minimo: ............................... 80
• Algoritmo di Hierholzer: ...................................................... 55
• Formulazione: ...................................................................... 80
• Algoritmo di Fleury: ............................................................. 55
• 8.8 Problema del cammino minimo: ............................... 81
• 6.6 Grafi hamiltoniani: ..................................................... 55
• Formulazione: ...................................................................... 81
• Teorema 6.14: ...................................................................... 55
• Teorema 6.15: ...................................................................... 56
• 8.9 Problema del flusso massimo: ................................. 82
• Teorema 6.16: ...................................................................... 56
• Formulazione: ...................................................................... 83
• 6.7 Grafi bipartiti: ............................................................. 56
• 8.10 Problema dell’abbinamento massimo: ................. 84
• Teorema 6.17: ...................................................................... 56
• 8.11 Problema dell’assegnamento: ............................... 84
• Metodo alternativo per riconoscere un grafo bipartito: ..... 57
• Formulazione: ...................................................................... 85
• Teorema 6.18: ...................................................................... 57
• Corollario 6.19: .................................................................... 58
• 8.12 Problema di trasporto: ........................................... 86
• Formulazione: ...................................................................... 86
• 6.8 Colorazione di grafi non-bipartiti: ......................... 58
• Teorema 6.20: ...................................................................... 58
• Capitolo 9 – Percorsi e cammini minimi ................ 89
• Teorema 6.21: ...................................................................... 58
• Teorema 6.22: ...................................................................... 58
• 9.1 Generalità: ................................................................... 89
• Teorema 9.1: ........................................................................ 89
• Appendice A – Matematica discreta ...................... 61
• Teorema 9.2: ........................................................................ 89
• Regola della somma: ....................................................... 61
• 9.2 Albero dei cammini minimi: ....................................... 90
• Proprietà 9.3: ....................................................................... 90
• Regola del prodotto: ....................................................... 61
• Proprietà 6.4: ....................................................................... 91
• Principio di inclusione/esclusione: ................................ 62
• Teorema 9.5: ........................................................................ 91
• Principio della piccionaia (o principio dei cassetti): ......... 62
• 9.3 Algoritmo generico di etichettatura: .................... 92
• Principio base: ...................................................................... 62
• Condizioni di ottimalità di Bellman: ..................................... 92
• Generalizzazione del principio: ............................................ 62
• Teorema 9.6: ........................................................................ 92
• Algoritmo generico di etichettatura di Ford (1956): ............ 92
• Disposizioni: ....................................................................... 63
• Teorema 9.7: ........................................................................ 93
• Disposizioni semplici: ........................................................... 63
• Disposizioni con ripetizione: ................................................ 64
• 9.4 Tipologie di algoritmi di etichettatura: ................. 94
• Algoritmi label-setting (assegnazione di etichetta): ............ 94
• Permutazioni: .................................................................... 64
• Algoritmi label-correcting (correzione di etichetta): ........... 94
• Permutazioni semplici: ......................................................... 64
• Permutazioni con ripetizione: .............................................. 65
• 9.5 Algoritmo dei cammini minimi per reti acicliche: . 94
• Teorema 9.8: ........................................................................ 95
• Combinazioni: .................................................................... 65
• Combinazioni semplici: ........................................................ 65
• 9.6 Algoritmi per reti con costi non-negativi: ............ 96
• Proprietà delle combinazioni semplici: ................................ 65
• Algoritmo di Dijkstra: ........................................................... 96
• Conseguenza del teorema binomiale: ................................. 67
• Teorema 9.9: ........................................................................ 97
• Capitolo 7 – Minimo albero ricoprente ................. 69
• 9.7 Algoritmi per reti con cicli non-negativi: .............. 98
• Algoritmo di Bellman-Ford: ................................................. 98
• 7.1 Introduzione: ............................................................... 69
• 9.8 Reti con cicli di costo negativo: ............................... 99
• Problema del minimo albero ricoprente: ............................ 69
• Applicazioni del problema: .................................................. 69
• 9.9 Algoritmi dei cammini minimi tra tutti i nodi: ...... 99
• 7.2 Formulazione del problema: .................................... 69
• 9.10 Cammino minimo con singola origine e destinazione: ................................................................... 100
• 7.3 Condizioni di ottimalità (1): ...................................... 71
• Algoritmo di Dijkstra a due liste: ....................................... 100
• Condizioni di ottimalità sui tagli: ......................................... 71
• Teorema 7.14: ...................................................................... 71
• Capitolo 10 – Massimo flusso ............................. 101
• Proprietà 7.5: ....................................................................... 72
• 10.1 Generalità: ............................................................... 101
• 7.4 Algoritmo di Prim: ...................................................... 72
• Problema del massimo flusso: ........................................... 101
• Algoritmo di Prim-Dijkstra: .................................................. 72
• 10.2 Rete residua: ............................................................. 101
• 7.5 Condizioni di ottimalità (2): ...................................... 73
• Condizioni di ottimalità sui cammini: ................................... 73
• 10.3 Taglio s-t: .................................................................. 102
• Teorema 7.6: ........................................................................ 73
• Capacità del taglio separatore: .......................................... 102
• Conseguenze teorema 7.6: .................................................. 73
• Taglio minimo: ................................................................... 103
• Flusso netto attraverso il taglio ............................... 103 − :
• 7.6 Algoritmo di Kruskal: ................................................ 74
• Proprietà 10.1: ................................................................... 103
• Capitolo 8 – Problemi di flusso su rete .................. 77
• Proprietà 10.2: ................................................................... 104
• 4
• Capacità residua del taglio separatore: ............................. 104
• Teorema 10.6: .................................................................... 109
• Corollario 10.3: .................................................................. 104
• 10.6 Reti con archi di capacità minima e massima: .... 109
• Proprietà 10.4: ................................................................... 105
• Teorema 10.7: .................................................................... 109
• 10.4 Cammini aumentanti: .......................................