Donatella Iacono

Matematica Discreta 2023/2024 (M-Z)

Corso di Laurea in Informatica e Tecnologia per la Produzione del Software, Corso B, M-Z

Inizio lezioni 26 Settembre 2023. Da lunedi 4 Dicembre, lezione in Aula 2, palazzo delle Aule: Lunedi 8:30-11:00, Martedi 8:30-11:00, Giovedi 8:30-10:10.

Ricevimento

Per i prossimi orari di Ricevimento studenti consultare la pagina home.

Esami:

La prenotazione agli appelli È OBBLIGATORIA mediante il sistema ESSE3 nei tempi stabiliti. NON si accettano prenotazioni via mail, netantomeno prenotazioni dopo i termini stabiliti. Portare obbligatoriamente un documento di validità, una penna e se serve una calcolatrice (non si può usare quella del cellulare). La durata della prova è 2 ore. È sconsigliata vivamente la partecipazione all' esame a chi non ha studiato (NON si viene a vedere come è ne tantomeno a tentarlo). Gli studenti che hanno superato la prova e vogliono accettare il voto, devono farlo entro i termini stabiliti su Esse3. Chi non accetta il voto può ripetere la prova in uno qualsiasi degli appelli successivi, perdendo ovviamente la prova precedente (questo vale per chi non accetta il voto per proprio volere, per errore, per dimenticanza, perché non sa usare Esse3, etc. ).

Pagina web degli Esami

Leggere attentamente e comprendere prima di presentarsi agli esami le Regole e faq.

Programma

Testi consigliati

Per la preparazione al corso va bene un qualsiasi libro che ricopra gli argomenti trattati. Alcuni libri che contengono tali argomenti sono:

G.M. Piacentini Cattaneo:"Matematica Discreta", ed. ZANICHELLI

M.G. Bianchi, A. Gillio: "Introduzione alla Matematica Discreta", ed. McGRAW-HILL

K. H. Rosen, "Discrete Mathematics and Its Applications", McGraw-Hill Editore, Settima Edizione (2012) (in Inglese).

Appunti, a cura di D.Iacono .

Note ed Esercizi svolti di Logica e Insiemi a cura di D.Iacono e V.Nardozza.

È stato attivato un canale su telegram https://t.me/MD23MZ, per facilitare e velocizzare la comunicazione di avvisi. Tutte le notizie verranno comunque pubblicate sulla pagina web del docente.

Esercizi

Esercizi di recupero su prodotti e potenze.(su prodotti, potenze, frazioni)
Esercizi 2 Ottobre 2023.(alcuni visti a lezione, su insiemi e logica)
Esercizi 3 Ottobre 2023.(alcuni visti a lezione, su logica e funzioni)
Esercizi 6 Ottobre 2023.(alcuni visti a lezione, su logica e funzioni)
Esercizi 9 Ottobre 2023.(alcuni visti a lezione, su funzioni) [Tolto Esercizio 3=Esercizio 1]
Esercizi 10 Ottobre 2023.(alcuni visti a lezione, su funzioni)
Esercizi 13 Ottobre 2023.(alcuni visti a lezione, su funzioni e principio di induzione)
Esercizi 17 Ottobre 2023.(alcuni visti a lezione, su principio di induzione)
Esercizi 19 Ottobre 2023.(alcuni visti a lezione, su principio di induzione e combinatoria)
Esercizi 23 Ottobre 2023.(alcuni visti a lezione, su combinatoria)
Esercizi 24 Ottobre 2023.(alcuni visti a lezione, su combinatoria)
Esercizi 26 Ottobre 2023.(alcuni visti a lezione, su relazioni di ordine)
Esercizi 30 Ottobre 2023.(alcuni visti a lezione, su relazioni di equivalenza [Nei primi 5 esercizi le relazioni sono quelle del 26 Ottobre])
Esercizi 31 Ottobre 2023.(alcuni visti a lezione, su relazioni di equivalenza)
Esercizi 6 Novembre 2023.(alcuni visti a lezione, su divisione)
Esercizi 8 Novembre 2023.(alcuni visti a lezione, su equazioni diofantee)
Esercizi 9 Novembre 2023.(alcuni visti a lezione, su congruenze)

Esercizi di riepilogo sulla prima parte del corso (In alcune tracce c'e' un esercizio sui sistemi di congruenze lineari che non va svolto, impareremo a svolgerlo dopo la pausa esoneri) Per simulare una prova basta scegliere una traccia, svolgerla in 2 ore usando solo penna e calcolatrice.

Esercizi 20 Novembre 2023.(alcuni visti a lezione, su congruenze, congruenze lineari, sistemi di congruenze lineari)
Esercizi 21 Novembre 2023.(alcuni visti a lezione, su struttre algebriche)
Esercizi 23 Novembre 2023.(alcuni visti a lezione, su struttre algebriche, alcuni esercizi sono gli stessi del foglio del 21 Novembre, con l'aggisunta della proprieta' commutativa e degli elementi invertibili)
Esercizi 27 Novembre 2023.(alcuni visti a lezione, su gruppo simmetrico)
Esercizi 28 Novembre 2023.(alcuni visti a lezione, su gruppo simmetrico)
Esercizi 1 Dicembre 2023.(alcuni visti a lezione, su vari argomenti)
Esercizi 14 Dicembre 2023.(su matrici)
Esercizi 27 Dicembre 2023.(su grafi)

Esercizi di riepilogo sulla seconda parte. Per simulare una prova di autovalutazione basta scegliere una traccia, svolgerla in 2 ore usando solo penna e calcolatrice. ATTENZIONE: Per i soli iscritti all' Anno Accademico 2023/2024 gli esercizi sui gruppi ciclici e gli esercizi sugli anelli (divisori invertibili) non fanno parte del programma di esame (quindi saltare esercizi sui gruppi ciclici e sugli anelli). Per tutti, dall'Anno Accademico 2020/2021 i numeri complessi non fanno più parte del Programma del Corso (quindi saltare l'esercizio sui numeri complessi). Dall'Anno Accademico 2017/2018 i reticoli non fanno più parte del Programma del Corso (quindi saltare l'esercizio sui reticoli).

Raccolta Prove passate

Esami passati. ATTENZIONE: Per i soli iscritti all' Anno Accademico 2023/2024 gli esercizi sui gruppi ciclici e gli esercizi sugli anelli (divisori invertibili) non fanno parte del programma di esame (quindi saltare esercizi sui gruppi ciclici e sugli anelli). Per tutti, dall'Anno Accademico 2020/2021 i numeri complessi non fanno più parte del Programma del Corso (quindi saltare l'esercizio sui numeri complessi). Dall'Anno Accademico 2017/2018 i reticoli non fanno più parte del Programma del Corso (quindi saltare l'esercizio sui reticoli). Nel tempo il corso è cambiato molto poco, ma qualche cambiamento c'è stato, quindi le tracce più recenti sono più simili ad una prova d'esame. ( All'appello del 12 Gennaio 2016, uno studente mi ha fatto giustamente notare che nel titolo manca una i....dal 2011: tutta colpa del copia e incolla! Anche se perseverare è diabolico.... lasciamo questo errore come segno di riconoscimento.)

Diario delle Lezioni

Inizio lezioni 26 Settembre 2023 ore 11:30 Aula Magna, piano terrra, Dipartimento di Informatica.

26.09.2023 (2h) : Presentazione del corso, orario lezioni, libri di testo, programma, esami, regole di base. Teoria elementare degli INSIEMI. Simbolo di appartenenza. Tre descrizioni per un insieme: elenco elementi, proprietà caratterizzante, Diagrammi di Venn. Inclusione. Esempi.
28.09.2023 (+3=5h) Ripasso appartenenza inclusione. iIlusione propria, uguaglianza. Esempi. Introduzione al linguaggio e simbolismo matematico: Quantificatori Ogni ed Esiste. Esempi. Unione, Intersezione. Proprietà Esempi. Operazione di somma e prodotto negli insiemi numerici: Commutatività, associatività, esistenza 0 e 1. Definizione di complementare e leggi di De Morgan (con dimostrazione) ed esempi. Insieme Differenza ed esempi. Prodotto cartesiano, Insieme delle Parti. Esempi ed Esercizi.
02.10.2023 (+3=8h) LOGICA: Definizione di proposizione, negazione, congiunzione, disgiunzione, implicazione. Tavole di Verità. Esempi ed Esercizi. Esercizi di logica: Tabelle di verità, proposizioni logiche, vere, false e negazioni. Doppia implicazione. Tavole di Verità. Esempi ed Esercizi. Equivalenza di proposizioni. Esempi ed Esercizi. Esercizi di logica: Tabelle di verità con tre proposizioni. Equivalenza di proposizioni. Significato Teorema. Esercizi su legge di De Morgan.
03.10.2023 (+2=10h) FUNZIONI: Definizione di funzione, insieme di partenza e insieme di arrivo. Esempi. Funzioni uguali. Immagine di una funzione e di un sottoinsieme. Controimmagine di un sottoinsieme. Esempi ed Esercizi su immagini e controimmagine. Funzione identità. Funzioni costanti. Esempi. Proprietà di immagine e controimmagine rispetto unione e intersezione. Esercizi: Proposizioni logiche, vere, false e negazioni.
05.10.2023 (+3=13h) Esercizi su proposizioni logiche, vere, false e negazioni. Tabelle di verità con tre proposizioni. Esercizi su funzioni: immagine dell'intersezione e intersezione delle immagini; controimmagine dell'unione è l'unione delle controimmagini. FUNZIONI: Grafico di una funzione. Esempi. Funzioni iniettive, definizione ed esempi. Funzioni suriettive, definizione ed esempi.
09.10.2023 (+3=16h) Esercizi su proposizioni logiche, vere, false e negazioni. Tabelle di verità con tre proposizioni. Funzioni biettive, definizione ed esempi. Esercizi su funzioni, iniettive, suriettive, biettive. Composizione di funzione e proprietà. Esempi ed esercizi. Esercizio: dimostrazione che la composizioni di funzioni iniettive è iniettiva. Esercizo su funzioni, iniettive, suriettive, biettive, composizioni.
10.10.2023 (+2h=18h): Esercizi su funzioni, iniettive, suriettive, biettive, composizioni. Esercizio: dimostrazione che la composizioni di funzioni suriettive è suriettiva. Funzione inversa di funzioni biettive. Proprietà: inversa della composizione di funzione, funzione inversa della funzione identità, funzione inversa della funzione inversa (senza dim). Determinazione della funzione inversa. Esempi ed Esercizi. Esercizi su funzioni: iniettive, suriettive, biettive, inversa, composizione
12.10.2023 (+3h=21h): Ripasso regole esame. Esercizi su funzioni, iniettive, suriettive, biettive, composizioni. CARDINALITÀ: Cardinalità di un insieme. Insiemi Equipotenti. Insiemi finiti. Esempi. Cardinalità minore o uguale. Proprietà di insiemi finiti. Insiemi infiniti, difinizioni equivalenti. Esempi. PRINCIPIO di INDUZIONE: Principio di induzione e formulazioni equivalenti. Esempi e controesempi ed esercizi sul principio di induzione.
16.10.2023 (+3h=24h): Esercizi su funzioni, iniettive, suriettive, biettive, composizioni. Esercizi su principio di induzione. Teorema: Cardinalità dell'insieme delle parti di un insieme finito (dim.1 usando il principio di induzione). SUCCESSIONI. Definizioni ed esempi. Successioni ricorsive ed esempi: numeri fattoriali, progressione aritmetica, progressione geometrica. Formula chiusa di successioni ricorsive. Esempi ed Esercizi.
17.10.2023 (+2h=26h): Esercizi su formula chiusa di successioni ricorsive, numeri fattoriali. Esempi ed Esercizi. Esempi di successioni ricorsive: Numeri di Fibonacci: definizione ricorsiva come modellazione della popolazione di conigli, formula ricorsiva e formula chiusa (senza dim.). Torri di Hanoi: definizione come gioco, formula ricorsiva e formula chiusa (con dimostrazione). Enunciato PRINCIPIO di INDUZIONE generalizzato. Simbolo di sommatoria e proprietà. Esercizio su principio di induzione con simbolo di sommatoria.
19.10.2023 (+3h=29h): Esercizi su formula chiusa di successioni ricorsive. Esercizi vari su principio di induzione con simbolo di sommatoria. Cardinalità dell'unione di insiemi finiti. Caso generale di insiemi disgiunti. Cardinalità dell'unione di insiemi finiti: Principio di inclusione-esclusione caso con intersezioni non vuote per due e tre insiemi (con dimostrazione). Cardinalita' del prodotto di insiemi finiti. Esempi. Introduzione a COMBINATORIA: Scegliere k elementi in un insieme con n elementi. Descrizione dei 4 casi: scelta di k elementi senza ripetizione (k minore o uguale ad n) ordine importante/ordine non importante; scelta di k elementi con ripetizione ordine importante/ ordine non importante. Caso 1) =SENZA ripetizioni. Caso 1) a) =SENZA ripetizioni ordine importante: Disposizioni semplici di n oggetti di classe k (k minore o uguale ad n). Definizione, calcolo di D(n,k), esempi ed esercizi. D(n,k) calcola il numero di applicazioni iniettive da un insieme di cardinalità k ad uno di cardinalità n(con dim.). D(n,n)=n! come numero di ordinamenti di n oggetti (permutazioni). Esercizi ed Esempi.
23.10.2023 (+3h=32h): Esercizio su principio di induzione con simbolo di sommatoria. Ripasso caso 1): Scegliere k elementi in un insieme con n elementi senza ripetizione: ordine importante D(n,k). D(n,k) calcola il numero di applicazioni iniettive da un insieme di cardinalità k ad uno di cardinalità n. Esempio D(n,n) calcola il numero di applicazioni biettive tra insiemi di cardinalità n. Esempio. Caso 1) b) =SENZA ripetizioni ordine non importante: Combinazioni semplici di n oggetti di classe k (k minore o uguale ad n). Definizione e calcolo del coefficiente binomiale. Sottoinsiemi di cardinalità k in un insieme di cardinalità n. Esempi. Proprieta'. Triangolo di Tartaglia e legame con i coefficienti binomiali. Formula del binomio di Newton (senza dim.). Seconda dimostrazione della cardinalita' dell'insieme delle parti di un insieme finito, usando la formula di Newton (con dim.). Esercizi ed Esempi. Caso 2) = CON ripetizioni. Caso 2) a) =con ripetizioni ordine importante: Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Esempi ed Esercizi.
24.10.2023 (+2h=34h): Ripasso Caso 2) a)= CON ripetizioni. Caso 2) a) =con ripetizioni ordine importante: Definizioni di disposizioni con ripetizioni di n oggetti di classe k e calcolo esplicito. Esercizio. Numero di funzioni tra due insiemi finiti. Esempi. Caso 2) b) =con ripetizioni ordine non importante: Combinazioni con ripetizioni di n oggetti di classe k. Calcolo (senza dim). Esempi ed Esercizi. Esercizi vari su Combinatoria: formula coefficiente binomiale, esercizi su disposizioni e combinazioni. Esercizi su principio di induzione con simbolo di sommatoria.
26.10.2023 (+3h=37h): Esercizi su Combinatoria. RELAZIONI: Definizioni di relazione su un insieme. Esempi. Relazione vuota, totale, identità. Relazione di ordine parziale: Riflessiva, Antisimmetrica, Transitiva. Esempi. Insiemi parzialmente ordinati e insiemi totalmente ordinati. Esempi.
30.10.2023 (+3h=40h): Relazioni di equivalenza: Riflessiva, Simmetrica, Transitiva. Esempi. Definizione di classe di equivalenza. Esempi ed Esercizi su relazioni di ordine e di equivalenza. Esempio Importante: a-b multiplo di n. Teorema sulle proprieta' delle classi di equivalenza (con dimostrazione). Definizione di PARTIZIONE di un insieme. Teorema: le cassi di equivalenza definiscono una partizione e viceversa (senza dimostrazione). Esercizi su su relazioni di ordine e di equivalenza e classi.
31.10.2023 (+2h=42h): Ripasso definizione di classe di equivalenza. Definizione di insieme quoziente. Esempi. Esercizi su relazioni di ordine e di equivalenza, classi di equivalenza. NUMERI INTERI. Definizione di divisore e multiplo. Proprietà ed esempi. Teorema della combinazione lineare: divisibilità di ogni combinazione lineare (con dimostrazione). Esercizio su relazione di equivalenza con divisione.
06.11.2023 (+3h=45h): Ripasso definizione di divisore e multiplo. Teorema della divisione in Z: esistenza ed unicità del quoziente e resto (senza dimostrazione). Esempi di divisioni con resto in tutti i casi. Definizione di un massimo comun divisore e definizione di MCD. Proprietà di MCD. Esempi. Definizione di un minimo comune multiplo e di mcm. Teorema: esistenza del MCD e algoritmo di Euclide per la sua determinazione e Identità di Bezout (con dimostrazione). Esempi ed Esercizi. Esercizio su induzione con divisione.
07.11.2023 (+2h=47h): Ripasso definizione del MCD e Identità di Bezout. EQUAZIONI DIOFANTEE: Definizione ed Esempi. Teorema di esistenza della soluzione (con dim.). Teorema che descrive tutte e sole le soluzioni di una equazione diofantea (visto solo che sono soluzioni). (Il nome è dovuto a Diofanto, per i più curiosi). Esempi ed Esercizi. Esercizi su equazioni diofantee. NUMERI PRIMI. Definizione di numeri primi. Definizioni equivalenti (senza dimostrazione) e proprietà.
09.11.2023 (+3h=50h): Esercizio su equazioni diofantee. Esercizio su relazione di equivalenza con divisione. Teorema Fondamentale dell'aritmetica: esiste unica fattorizzazione in potenze di primi distinti (dimostrato solo l'esistenza della fattorizzazione). Esempi. Applicazione della fattorizzazione per trovare divisori di un numero: scrittura esplicita e calcolo di quanti sono i divisori. Applicazione della fattorizzazione per il calcolo del MCD. Teorema esistenza infiniti numeri primi (con dimostrazione). Crivello di Eratostene per trovare numeri primi e metodo di fattorizzazione. CONGRUENZE modulo n >1. Ripasso della definizione della relazione di congruenza: relazione di equivalenza. Descrizione relazione, classi di equivalenza. Esempi.
PAUSA ESONERI: 13-17 NOVEMBRE (no lezioni)
20.11.2023 (+6h=56h): CONGRUENZE modulo n >1. Ripasso della definizione della relazione di congruenza: relazione di equivalenza. Descrizione relazione, classi resto, descrizione quoziente. Esempi. Descrizione di alcune proprietà: somma, moltiplicazione, divisione dei coefficienti, riduzione del modulo. Esempi vari. Ripasso criteri di divisibilità per 2, 5, 3 e 9. Piccolo teorema di Fermat (senza dim.). [ Teorema di Fermat (enunciato). Per i piu' curiosi: un po' di storia del teorema e un link un po' meno matematico ] Definizione della funzione di Eulero. Teorema di Eulero Fermat (senza dimostrazione). Applicazione al calcolo di potenze modulo n. Esercizi su potenze modulo n. CONGRUENZE LINEARI: Definizione ed Esempi. Teorema di esistenza della soluzione (con dimostrazione). Teorema che descrive tutte e sole le soluzioni di una congruenza lineare (usando le equazioni diofantee), descrizione delle soluzioni non congruenti modulo n. Proprietà. Esempi ed Esercizi. Proprietà di risoluzione (divisione, resto, tentativi). Esempi ed Esercizi su congruenze lineari. SISTEMI DI CONGRUENZE LINEARI: definizione ed esempi. Teorema riduzione dei coefficiente dell'incognita ad 1, nel caso di esistenza di soluzione per ogni congruenza (con dimostrazione). Teorema Cinese dei Resti: esistenza ed unicità della soluzione modulo N (dimostrazione solo dell'esistenza della soluzione). Esempi ed Esercizi sui sistemi di congruenze. Per i più curiosi: Il sistema RSA: applicazione delle congruenze lineari alla crittografia.
21.11.2023 (+2h=58h): Esercizi su congruenza, sistemi di congruenze. STRUTTURE ALGEBRICHE: Definizione di struttura algebrica, operazione. Esempi. Operazione associativa: esempi e esercizi. Elemento neutro: esempi ed esercizi. MONOIDI: definizione.
23.11.2023 (+3h=61h): Ripasso definizione monoide. Esempio monoide delle parole. Definizione di operazione commutativa ed esempi. Esempi ed esercizi su strutture algebriche associativa, commutativa elemento neutro. Definizione di elementi invertibili. Teorema: nelle strutture algebriche associative (monoidi) se l'inverso esiste è unico (con dim.) Esempi ed Esercizi su elementi invertibili. GRUPPI: definizione, esempi, gruppi abeliani e non abeliani. Esempi. Relazioni di equivalenza compatibili con strutture algebriche. Teorema della struttura algebrica indotta sull'insieme quoziente (senza dimostrazione). Esempio fondamentale 1: relazione di congruenza modulo n su Z compatibile con la somma : (Z_n,+). Gruppo abeliano (Z_n, +) ed esempi numerici. Esempio fondamentale 2: relazione di congruenza modulo n su Z compatibile con il prodotto: (Z_n, .). Monoide commutativo (Z_n, .). Esempio numerico.
27.11.2023 (+3h=64h): Ripasso definizione gruppo. Ordine di un gruppo: definizione ed esempi. Teorema: elementi invertibili in (Z_n, .) (con dim.). Teorema su gruppo abeliano: (Zp*,.) con p primo è un gruppo abeliano (con dimostrazione). SOTTOGRUPPI: definizioni. Esempi banali. Sottogruppo ciclico generato da un elemento: insieme delle potenze di un elemento. Definizione di gruppo ciclico. Ordine di un elemento. Esempi. Proprietà delle potenze di un elemento n realazione al suo ordine (senza dim.). Esempio. GRUPPO SIMMETRICO o GRUPPO di PERMUTAZIONI. Definizione di gruppo simmetrico. Notazione degli elementi, degli inversi e della composizione. Esempi. Definizione di Ciclo. Esempi. Definizione di trasposizione o scambio. Ogni ciclo corrisponde ad una permutazione. Teorema: Ogni permutazione può scriversi come ciclo o prodotto di cicli disgiunti (senza dim.). Esempi.
28.11.2023 (+2h=66h): GRUPPO SIMMETRICO o GRUPPO di PERMUTAZIONI. Teorema: ordine di una permutazione (senza dim.). Esempi. Teorema: Ogni ciclo può essere scritto come prodotto di trasposizioni (con dim. formula) Esempi. Conseguenza: ogni permutazionepuò essere scritta come prodotto di trasposizioni. Permutazioni pari e dispari. Esempi. Esercizi su gruppo di permutazione: ordine, prodotti di cicli, inversa, pari e dispari, sottogruppo generato ordine degli elementi e descrizione. Esercizi su strutture algebriche: associativa, commutativa, elemento neutro, inverso di un elemento, elementi invertibili.
01.12.2023 Esercizi su: gruppo simmetrico, strutture algebriche, sistemi di congruenze, congruenze, equazioni diofantee, relazioni di ordine e di equivalenza, principio di induzione, combinatoria.
L'ultima parte del corso è mutuato con il corso di Matematica Discreta, Informatica, Canale M-Z, Professoressa Sara Azzali. Programma svolto: Ripasso strutture algebriche e gruppi. Esercizi. Esercizi su sistemi di congruenze e strutture algebriche. Gruppi ciclici ed esempi. Ripasso gruppo simmetrico. Definizione di matrice. Esempi. MATRICI: Insieme delle matrici m x n a coefficienti in un campo. Matrice trasposta di una matrice data. Matrici quadrate. Operazioni fra matrici: somma fra matrici; prodotto per scalari; il prodotto "righe per colonne" e loro proprietà. Le matrici quadrate a coefficienti in campo K formano un anello [senza dimostrazione]. Invertibilità di una matrice quadrata rispetto al prodotto righe per colonne. Il determinante: definizione ricorsiva tramite lo sviluppo di Laplace. Esempi ed esercizi. Formula per calcolare l'inversa di una matrice invertibile [senza dimostrazione]. GRAFI: Grafi. Nozione di grafo semplice ed esempi. Rappresentazione di un grafo. Isomorfismo fra due grafi. Grado o valenza di un vertice. Il teorema delle strette di mano [con dimostrazione]. Corollario: ogni grafo finito ha un numero pari di vertici dispari. Esempi. Grafo completo. Esempi. Nozione di cammino su di un grafo e di circuito. Grafi connessi e sconnessi. Cammini e circuiti euleriani. Enunciato del teorema di Eulero sulla caratterizzazione dei cammini e circuiti euleriani. Alcune classi di grafi. Grafi bipartiti. Esempi: i grafi K_{n, m}. Teorema: un grafo è bipartito se e solo se non ammette circuiti di lunghezza dispari [senza dimostrazione]. Grafi planari. Nozione di sottografo di un grafo dato e di espansione di un grafo dato. Teorema di Kuratowski che caratterizza la planarità di un grafo [senza dimostrazione]. ALBERI. Teorema di caratterizzazione degli alberi [senza dimostrazione]. Ogni albero è un grafo bipartito (con dimostrazione). Teorema sull'esistenza di alberi per un assegnato insieme di vertici e valenze. Esempi.

DONATELLA IACONO