La rete di trasporto principale del West Montana è costituita da strade di 4 diverse categorie, che collegano tra loro 7 centri. In tabella sono indicati, per ogni categoria i di strade, la velocità media e la capacità di deflusso.
 

classe	velocità (km/ora)	capacità (auto/min.)
1	90	90
2	60	60
3	40	40
4	30	30

La rete è rappresentata dal grafo in Fig. 1, in cui ogni arco indica l’esistenza di un collegamento diretto tra due nodi. Ad ogni arco sono associate due informazioni: la lunghezza in km e, tra parentesi, la categoria della strada.

Si chiede:

(a) di determinare il tempo minimo necessario per andare dal nodo A (origine) al nodo G (destinazione), nell’ipotesi che il grafo non sia orientato (cioè che tutti gli archi siano percorribili in entrambi i sensi);

(b) di determinare il flusso massimo di automobili che possono spostarsi da A a G, nell’ipotesi che il grafo venga orientato come in Fig. 2 (le frecce indicano il senso di percorrenza degli archi; gli archi percorribili nei due sensi sono stati sdoppiati; l’informazione associata ad ogni arco è la capacità di deflusso).