Ottimizzazione su rete - Esercizi

Esercizio n. 1

Con riferimento al grafo in figura si risponda alle seguenti domande:

1. Qual è la densità del grafo?
2. Il grafo è pieno?
3. Il grafo è completo?
4. È fortemente connesso?

Esercizio n. 2

Per il grafo dell’esercizio 1:

1. Si scriva la matrice di incidenza arco-percorso per la coppia ordinata di vertici 1-6, assumendo che ciascun arco abbia un costo pari al numero del suo vertice destinazione.
2. Si calcoli il percorso minimo.

Esercizio n. 3

Per il grafo dell’esercizio 1 si costruisca l’albero di visita in larghezza e l’albero di visita in profondità, indicando l’indice di successione della visita.

Esercizio n. 4

Si consideri la rete in figura, sulla quale sono riportati il costo di spostamento su ciascun arco, il flusso generato o attratto da ciascun nodo e in tratto doppio l’albero di una soluzione basica ammissibile iniziale.

1. Si scriva il modello di flusso single-commodity senza vincoli di capacità e la tabella del simplesso associata al caso in figura, senza riportare le variabili artificiali.
2. Quali condizioni devono essere rispettate affinché la soluzione di un modello di flusso single-commodity sia intera anche se non si impone esplicitamente il vincolo di interezza delle variabili?
3. Si determini la soluzione ottima del problema utilizzando l’algoritmo del simplesso su rete assumendo come iniziale la soluzione evidenziata in figura.