Provetta sulla Programmazione Combinatoria

Provetta sulla Programmazione Combinatoria

ESERCIZIO 1:

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

1.: Trovare l'albero ricoprente di peso minimo.
2.: Fornire un'argomentazione per l'ottimalità.
3.: Indicare quali archi siano contenuti in ogni soluzione ottimale.
4.: Indicare quali archi non siano contenuti in alcuna soluzione ottimale.
5.: Sfruttare le informazioni di cui ai punti 3. e 4. per rappresentare in modo compatto l'insieme delle soluzioni ottime o quantomeno fornire tutte le soluzioni ottime.

ESERCIZIO 2:

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

1.: Trovare un accoppiamento perfetto di peso minimo.
2.: Fornire un certificato di ottimalità.
3.: Dare tutti gli accoppiamenti perfetti di peso minimo argomentando come essi siano i soli.

ESERCIZIO 3:

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

ESERCIZIO 4:

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

1.: Dare un accoppiamento di cardinalità massima ed un certificato di ottimalità.
2.: Era possibile in questo caso fornire un certificato di ottimalità in termini di copertura per nodi?
3.: Si consideri l'algoritmo di Edmonds per trovare un accoppiamento di massima cardinalità. Fornire un grafo che costringa l'algoritmo a contrarre almeno un ``blossom'' e giustificare la risposta.
4.: Dare un grafo non bipartito dove la massima cardinalità di un accoppiamento pareggi la minima cardinalità di una copertura per nodi.

21 Maggio 1998