48
GEOMETRIA
REGGIO DI CALABRIA
Dati Generali
Periodo di attività
Syllabus
Obiettivi Formativi
Conoscenza delle nozioni di base della teoria dei Grafi: grafo semplice, ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Rappresentazione di grafi. Alberi e grafi planari. Matrice di adiacenza. Matrice di incidenza. Conoscenza degli strumenti e delle tecniche proprie della teoria dei Grafi: Copertura minimale di un grafo, k-colorazione, percorso minimo, albero di copertura minimale.
Risultati Attesi
Con riferimento ai Descrittori di Dublino lo studente dovrà conseguire i seguenti risultati di apprendimento:
Conoscenza e comprensione: a seguito del superamento dell’esame, lo studente conosce i principi fondamentali della teoria dei grafi.
Capacità di applicare conoscenze: a seguito del superamento dell’esame, lo studente è in grado di utilizzare gli strumenti della teoria dei grafi anche al fine di formalizzare e risolvere problemi legati alle discipline strutturali del corso di studio.
Autonomia di giudizio:
Per il superamento dell’esame lo studente deve essere in grado di riconoscere le tecniche più elementari della teoria dei grafi e riconoscere le situazioni e i problemi in cui tali tecniche possono essere applicate.
Abilità comunicative:
per il superamento dell’esame lo studente deve essere in grado di conoscere e illustrare con un linguaggio scientifico appropriato le motivazioni teoriche, che sono alla base della procedura di calcolo scelta per l’esecuzione di un esercizio, e il ragionamento logico alla base dei teoremi fondamentali della teoria dei grafi.
Capacità di apprendimento: a seguito del superamento dell’esame, lo studente è in grado di di approfondire in autonomia le conoscenze acquisite e di applicare le stesse alla conoscenza di nuovi argomenti, dove la teoria dei grafi viene applicata.
Prerequisiti
Conoscenze della matematica di base: insiemi numerici. Risoluzione di equazioni algebriche. Scomposizione dei polinomi algebrici. Concetto di matrice e rango di una matrice. Risoluzione dei sistemi lineari.
Metodi didattici
Tradizionali con lezione frontale ed esercitazioni
Verifica Apprendimento
Modalità di accreditamento e valutazione prova orale:
I possibili argomenti su cui verterà l'esame sono:
1. ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio.
2. Rappresentazione di grafi. Isomorfismo tra grafi. Alberi e grafi planari. Grafi diretti.
3. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza. Cammini e circuiti euleriani.
4. Grafi e colorazioni. Alberi di copertura minimali.
5. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero.
Nelle verifiche in itinere si valutano le capacità critiche raggiunte dallo Studente nell'inquadrare le tematiche oggetto del Corso ed il rigore metodologico delle risoluzioni proposte in risposta ai quesiti formulati. La prova orale consiste in un colloquio sugli argomenti delle verifiche in itinere e sugli argomenti teorici che fanno parte del programma del corso. Si valuta la capacità dello studente di comunicare le nozioni acquisite attraverso un linguaggio scientifico adeguato e la capacità di esposizione.
Il voto finale sarà attribuito secondo il seguente criterio di valutazione:
30 - 30 e lode: ottima conoscenza degli argomenti, ottima proprietà di linguaggio, completa ed originale capacità interpretativa, spiccata capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;
26 - 29: conoscenza completa degli argomenti, buona proprietà di linguaggio, completa ed efficace capacità interpretativa, in grado di applicare autonomamente le conoscenze per risolvere i problemi proposti;
24 - 25: conoscenza degli argomenti con un buon grado di apprendimento, discreta proprietà di linguaggio, corretta e sicura capacità interpretativa, capacità di applicare in modo corretto la maggior parte delle conoscenze per risolvere i problemi proposti;
21 - 23: conoscenza adeguata degli argomenti, ma mancata padronanza degli stessi, soddisfacente proprietà di linguaggio, corretta capacità interpretativa, limitata capacità di applicare autonomamente le conoscenze per risolvere i problemi proposti;
18 - 20: conoscenza di base degli argomenti principali e del linguaggio tecnico, capacità interpretativa sufficiente, capacità di applicare le conoscenze acquisite;
<18 Insufficiente: non possiede una conoscenza accettabile degli argomenti trattati durante il corso.
Testi
W. D. Wallis, A Beginner’s Guide to Graph Theory, Second edition, Birkhäuser, 2007.
Contenuti
Programma del Corso
1 cfu: Problema dei ponti di Königsberg. Definizioni e concetti fondamentali: ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Isomorfismi tra grafi.
1 cfu: Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti. Matrici e spazi vettoriali di grafi. Cammini e circuiti euleriani. Problema di cammino minimo.
1 cfu: Matrice di adiacenza. Matrice di incidenza. Grafi e colorazioni. Alberi. Alberi di copertura minimali.
1 cfu: Reti. Cammini nelle reti. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Algoritmi: di Kruskal e di Ford-Fulkerson:. Applicazioni della teoria dei grafi ai trasporti, alle reti elettriche, alle reti di calcolatori per la distribuzione e l’immagazzinamento di informazioni.
1 cfu: Flussi. Teoria di Ramsey. Teorema di Eulero.
1cfu: Applicazioni dei grafi in recenti articoli scientifici.
Risultati Attesi
Con riferimento ai Descrittori di Dublino lo studente dovrà conseguire i seguenti risultati di apprendimento:
Conoscenza e comprensione: a seguito del superamento dell’esame, lo studente conosce i principi fondamentali della teoria dei grafi.
Capacità di applicare conoscenza e comprensione: a seguito del superamento dell’esame, lo studente è in grado di utilizzare gli strumenti della teoria dei grafi anche al fine di formalizzare e risolvere problemi legati alle discipline strutturali del corso di studio.
Autonomia di giudizio:
Per il superamento dell’esame lo studente deve essere in grado di riconoscere le tecniche più elementari della teoria dei grafi e riconoscere le situazioni e i problemi in cui tali tecniche possono essere applicate.
Abilità comunicative:
per il superamento dell’esame lo studente deve essere in grado di conoscere e illustrare con un linguaggio scientifico appropriato le motivazioni teoriche, che sono alla base della procedura di calcolo scelta per l’esecuzione di un esercizio, e il ragionamento logico alla base dei teoremi fondamentali della teoria dei grafi.
Capacità di apprendimento: a seguito del superamento dell’esame, lo studente è in grado di di approfondire in autonomia le conoscenze acquisite e di applicare le stesse alla conoscenza di nuovi argomenti, dove la teoria dei grafi viene applicata.
Altre informazioni
Ricevimento sia in studio che in aula. Possibilità anche di supporto per lo svolgimento di esercizi o eventuali spiegazioni anche tramite email o collegamento online.
Codice teams del corso xeupp8f. Il materiale didattico fornito slide delle lezioni ed esercizi proposti sarà di supporto allo studio.