FANDOM


Il candidato analizzi il problema del flusso massimo attraverso i seguenti punti:

  1. Fornire la terminologia e le principali definizioni riguardanti i grafi;
  2. Illustrare il problema del flusso massimo su grafo orientato;
  3. Proporre un algoritmo risolutivo;
  4. Adattare l’algoritmo al caso di sorgenti/terminali multipli e al caso di capacità sui vertici.




Si dia la definizione di problema di Programmazione Lineare, discutendone le proprietà fondamentali e si descriva un algoritmo risolutivo per questa classe di problemi.




Si parli della programmazione matematica in generale, soffermandosi poi sulla programmazione lineare. In particolare, si dia la caratterizzazione della regione ammissibile e se ne discutano le proprietà fondamentali, presentando le relazioni con le soluzioni ottime. Si descriva la difficoltà del problema e la complessità computazionale di eventuali algoritmi risolutivi.




Si definiscano le caratteristiche e proprietà fondamentali dei grafi; successivamente si affronti il problema di determinare il flusso massimo tra una coppia di vertici su un grafo pesato sugli archi e orientato. Per tale problema si presentino i risultati teorici fondamentali e un algoritmo risolutivo.