1.46 Esercizio. Si dimostri che, dato un grafo orientato aciclico e assegnato un nodo particolare s, esiste sempre un albero tale che l’unico cammino da s a i sull’albero `e un cammino massimo da s a i nel grafo, per ogni i. Si faccia anche vedere come la propriet`a non sia in generale verificata in assenza di aciclicit`a.
Soluzione. La dimostrazione `e del tutto analoga a quelle dell’esercizio 1.42, notando che in un grafo aciclico non pu`o ovviamente avvenire che un arco sia percorso da due cammini in senso opposto.
1
![[1] Si consideri il polinomio booleano (nelle quattro variabili a, c, e, s ) dato da P (a, c, e, s](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)