Esercizi in preparazione alla provetta sulla Programmazione Combinatoria

Esercizi in preparazione alla provetta sulla Programmazione Combinatoria

ESERCIZIO 1:

$\begin{figure}% \begin{center} \leavevmode \psfig{figure=trees.eps, height=4 true cm}\par\end{center}\end{figure}$

Trovare l'albero ricoprente di peso minimo.
Fornire un argomentazione per l'ottimalità
Trovare tutti gli alberi ricoprenti di peso minimo.
Indicare quali archi siano contenuti in ogni soluzione ottima, ossia quali archi non possano essere rimossi senza peggiorare la qualità della soluzione ottima.

ESERCIZIO 2:

$\begin{figure}% \begin{center} \leavevmode \psfig{figure=stu.eps, height=4 true cm}\par\end{center}\end{figure}$

Il grafo in figura è planare? Perchè?
É bipartito? Perché?
Trovare un cammino che vada da s a t utilizzando ogni arco precisamente una volta. Esiste un tale cammino anche da s a u? Perché?
Trovare l'albero ricoprente di peso minimo.
Trovare tutti gli alberi ricoprenti di peso minimo.

ESERCIZIO 3:

Con riferimento ai tre grafi delle figure precedenti.

Trovare tra gli accoppiamenti di cardinalità massima quello di peso minimo.
Fornire un'argomentazione per l'ottimalità
Trovare tutte le soluzioni ottime.
Indicare quali archi siano necessariamente contenuti in ogni soluzione ottima.

ESERCIZIO 4:

Nel seguente digrafo trovare l'alborescenza dei cammini minimi da s a tutti gli altri nodi. Trovare quindi i cammini minimi da t a tutti gli altri nodi. Trovare infine il cammino di costo minimo da u a t.

$\begin{figure}% \begin{center} \leavevmode \psfig{figure=distanze.eps, height=7 true cm}\par\end{center}\end{figure}$

20 Maggio 1998