Lezione 13.1: le condizioni di ottimalità del flusso di costo minimo
Completion requirements
La necessaria teoria sul problema di flusso di costo minimo. Pseudoflussi, sbilanciamenti, cammini aumentanti e loro effetto sugli sbilanciamenti (nullo nel caso di cicli) e sul costo. Teorema di decomposizione degli pseudoflussi (enunciato) e cosa vuol dire: "gli pseudoflussi sono semplici". Condizioni di ottimalità: un flusso è ottimo se e solo se non esistono cicli aumentanti di costo negativo, la freccia banale e quella no. Come determinare se esistono cicli aumentanti di costo negativo: il grafo residuo ed il problema del cammino minimo. Esempio di condizioni di ottimalità: le etichette che soddisfano le condizioni di Bellman sono un certificato di ottimalità del flusso.