COMBINATORIA

Claudia Malvenuto Scheda di esercizi n. 1

1. Disegnare tutti i grafi aventi per insieme dei vertici {1, 2, 3}. Quante e quali sono le classi di isomorfismo su questi grafi?

2. Quante e quali sono le classi di isomorfismo di grafi su 5 vertici?

3. Scrivere un isomorfismo esplicito tra i due seguenti grafi:

5 4 1 3 2  5 4 1 3 2

4. Scrivere un isomorfismo esplicito tra i due seguenti grafi:

9  8 10  7 6 4  3 5  2 1  5 6  1  2 3 4 9  8 7 10

5. Dimostrare che i grafi che seguono non sono isomorfi:

9  8 10  7 6 4  3 5  2 1  9  8 10  7 6 4  3 5  2 1

6. Scrivere tutti gli automorfismi di un 4-ciclo.

7. Dimostrare che in ogni grafo il numero di vertici di grado dispari è pari.

8. Nel corso di una festa alcune persone si stringono la mano. Dimostrare che, in qualunque modo ciò avvenga, ci saranno almeno due persone che avranno stretto lo stesso numero di mani.

9. È vero che il complementare di un grafo non connesso è connesso? È vero che il complementare di un grafo connesso è non connesso?

10. Dimostrare che in un grafo connesso esiste un cammino euleriano da x a y se e solo se x e y sono i soli vertici di grado dispari.

11. Si mostri che in un grafo euleriano, comunque presi un vertice x e un arco e a esso incidente, è possibile trovare un circuito euleriano x, e, x_{1}, e_{1}, …, x (che parte dal vertice x ed esce da x passando per e).

12. Mostrare che l’insieme degli archi di un circuito può essere partizionato in cicli.