Matematica Discreta 2
(elenco dei principali teoremi)

Domenico Luminati

Date: a.a. 2004/05

Questa è la lista dei principali teoremi studiati durante il corso ed il cui enunciato e la cui dimostrazione (a meno che non esplicitamente segnalato) potrà essere oggetto del tema d'esame.

Teoria degli insiemi

1. proprietà elementari delle funzioni totali e parziali (composizione di funzioni è una funzione, composizione di iniettive è iniettiva, composizione di suriettive è suriettiva, ecc.)
2. prima forma del principio di induzione
3. il teorema di ricorsione
4. lemma dei cassetti e definizione di cardinalità per gli insiemi finiti
5. ogni insieme infinito contiene un sottinsieme equipotente a $\mathbb{N}$.
6. caratterizzazione degli insiemi infiniti (sono equipotenti ad un sottinsieme proprio)
7. teorema di Cantor
8. il teorema di Cantor-Schroeder-Bernstein (solo enunciato)
9. i numeri razionali sono numerabili
10. i numeri reali non sono numerabili
11. $\mathbb{N}$ è bene ordinato da $\le$.
12. seconda forma del principio di induzione

Aritmetica

1. teorema di divisione euclidea
2. la relazione di divisibilità è un ordinamento parziale su $\mathbb{N}$
3. teorema di reappresentazione in base fissata dei numeri naturali
4. teorema di esistenza e unicità del MCD
5. algoritmo di Euclide per il calcolo del MCD
6. teorema di caratterizzazione dei numeri primi
7. teorema fondamentale dell'aritmetica (fattorizzazione unica)
8. teorema di esistenza di infiniti numeri primi
9. teorema di esistenza e unicità del mcm
10. proprietà della relazione di congruenza $\quad{\rm mod} n$
11. teorema cinese del resto
12. teorema di caratterizzazione degli invertibili $\quad{\rm mod} n$
13. piccolo teorema di Fermat

Teoria dei grafi

1. relazione fondamentale dei grafi finiti (la somma dei gradi è pari al doppio del numero dei lati)
2. teorema di equivalenza tra la congiungibilità con cammini e la congiungibilità con passeggiate
3. teorema dello score
4. legame tra le potenze della matrice di adiacenza ed il numero di passeggiate tra due punti
5. teorema di caratterizzazione dei grafi euleriani
6. primo teorema di caratterizzazione dei grafi 2-connessi (congiungibilità con cicli )
7. secondo teorema di caratterizzazione dei grafi 2-connessi (costruzione a partire da $K_3$)
8. teorema di caratterizzazione degli alberi
9. teorema di caratterizzazione degli alberi finiti mediante la formula di Eulero ( $\left\vert V\right\vert=\left\vert E\right\vert+1$)
10. teorema di esistenza dell'albero di copertura per i grafi finiti