Esercizi di Matematica Discreta (04/02/09) 1)

Esercizi di Matematica Discreta (04/02/09)

1) Dato l'insieme A={1,2,3,4,5,6,7,8,9,10}, e i suoi sottoinsiemi B= {7,8,9,10}, C=

{1,2,3,7,8}, D={3,5,10}, calcolare il numero dei sottoinsiemi di A che hanno intersezione vuota con almeno uno dei sottoinsiemi B,C,D. (6 p.)

2) Dimostrare che per ogni numero naturale n il numero n

+4n è multiplo di 5. (4 p.) 3) Dati gli insiemi A = {1,2,3,4,5,6,7}, B = {7,8,9,10,11,12}, calcolare il numero delle funzioni f: A  B tali che l’immagine di ogni numero dispari sia pari; calcolare poi, tra queste funzioni, il numero di quelle iniettive (5 p.)

4) Si consideri il grafo semplice non orientato, in cui i vertici sono i numeri naturali x tali che 1x30 e in cui due vertici distinti x,y sono uniti da un arco se (rappresentati come punti su una retta orientata) la loro distanza è =3.

Quante componenti connesse ha il grafo ? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano (ciclico o non ciclico) ? (3 p.)

5) Sia dato l'insieme A={1,2,3,4,5,6,7,8,9,10,11,12} e il suo sottoinsieme

B={1,2,3,4,5,6}. Contare quanti sono i sottoinsiemi C di A tali che la cardinalità di

BC sia uguale a 3 (sugg. per costruire ognuno dei sottoinsiemi C, si deve scegliere

un sottoinsieme di B di cardinalità 3 e ...) (6 p.)