TEORIA DEI GRAFI

Origini: problema dei ponti di Königsberg. Definizioni e concetti fondamentali: definizioni, ciclo, multigrafo, grafo completo, grafo bipartito, cammini, circuiti, connettività, componenti, punto di taglio. Rappresentazione di grafi. Alberi e grafi planari. Grafi diretti. Matrici e spazi vettoriali di grafi. Cammini e circuiti euleriani. Problema di cammino minimo. Matrice di adiacenza. Matrice di incidenza. Matching. Grafi e colorazioni. Alberi con radice. Alberi di copertura minimali. Reti. Cammini nelle reti. Circuito Hamiltoniano. Grafo euleriano. Grafo Hamiltoniano. Flussi. Teorema di Eulero. Algoritmi: di Dijkstra, di Kruskal e di Prim. Applicazioni della teoria dei grafi ai trasporti, alle reti elettriche, alle reti di calcolatori per la distribuzione e l’immagazzinamento di informazioni.

Definizioni di base di algebra commutativa: definizione di anello commutativo, di campo, ideale di un anello, operazione tra ideali. Anello dei polinomi in n-indeterminate a coefficienti su campo. Ordinamenti monomiali. Ordinamento delle variabili. Introduzione dell’algebra computazionale mediante l’uso delle basi di Groebner per lo studio della K-colorazione, della copertura minimale di un grafo e del calcolo dei cicli di un grafo. Utilizzo delle basi di Grobner sia dal punto vista teorico che pratico. Uso dei software di algebra computazionale CoCoA o Macaulay 2 per lo svolgimento di esercizi.

Ultimo aggiornamento: 08-10-2023

• W. D. Wallis, A Beginner’s Guide to Graph Theory, Second edition, Birkhäuser, 2007.
•  W.W. Adams, P. Loustaunau, An Introduction to Groebner Bases, American Mathematical Society, 2012
• Tutorial software CoCoA (Capani - G. Niesi - L. Robbiano, A system for doing computations in commutative algebra, Available via anonymous ftp from: cocoa.dima.unige.it.)

Ultimo aggiornamento: 08-10-2023

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. Capacità di comprendere e utilizzare strumenti matematici adeguati per la risoluzione di problemi di connessione tramite l'utilizzo dei grafi. Capacità di comunicare le conoscenze acquisite attraverso un linguaggio tecnico-scientifico adeguato.

Conoscenze relative agli aspetti metodologico-operativi della Teoria dei grafi, ai fini dell’interpretazione e descrizione di applicazioni nell’ambito dell’Ingegneria, ad esempio applicazioni nell'ambito delle reti elettriche, problemi di flusso e dei trasporti.

Conoscenza delle nozioni di base dell’algebra computazionale. Capacità di risolvere mediante tecniche di natura computazionale i problemi di colorazione di un grafo, il problema del minimal vertex cover, calcolo dei cicli di un grafo.

Ultimo aggiornamento: 08-10-2023

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.

Ultimo aggiornamento: 08-10-2023

Metodo tradizionale. Lezione alla lavagna e svolgimento di esercizi anche con l’utilizzo dei software CoCoA o Macaulay2.

Ultimo aggiornamento: 08-10-2023

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.

Ultimo aggiornamento: 28-11-2023

Modalità di accreditamento e valutazione:

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. 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. Algoritmo di Dijkstra.

Modalità di apprendimento:

Svolgimento di esercizi tramite l’utilizzo dell’algebra computazionale e di software di calcolo simbolico.

Possibili quesiti:

1)    Basi di Groebner, Ordinamenti monomiali

2)    Colorazione di un grafo

3)    Copertura minimale di un grafo

4)    Calcolo dei cicli in un grafo

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.

Ultimo aggiornamento: 08-10-2023

Eliminare le disparità di genere nell'istruzione e assicurarsi che tutti gli studenti, compresi i più vulnerabili quali le persone con disabilità, acquisiscano le conoscenze e le competenze necessarie, fornire ambienti di apprendimento sicuri, non violenti, inclusivi ed efficaci per tutti

Ultimo aggiornamento: 28-11-2023