Alcuni Problemi Combinatorici su Grafi

Alcuni Problemi Combinatorici su Grafi

Di ciascuno dei seguenti grafi dire se è planare (e motivare), bipartito (e motivare).

Nei due seguenti grafi trovare un albero ricoprente ed un accoppiamento perfetto di peso minimo.

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

I seguenti grafi contengono un accoppiamento perfetto? (motivare) Posso colorarne gli archi in tre colori? (motivare)

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

Posso disegnare i seguenti grafi senza staccare la penna dal foglio? (motivare) E con la condizione aggiuntiva di ritornare al nodo di partenza? (motivare)

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

Dare condizioni necessarie e sufficienti affinchè sia possibile tracciare un grafo senza staccare la penna dal foglio e ritornando al nodo di partenza.

5 Maggio 1998