Vai al contenuto principale
Oggetto:
Oggetto:

Algoritmi per l'algebra (DM 270) - a.a. 2011/12

Oggetto:

Anno accademico 2011/2012

Codice dell'attività didattica
MFN1418
Docente
Prof. Marco Burzio (Titolare del corso)
Corso di studi
Laurea in Matematica
Anno
3° anno
Periodo didattico
Primo semestre
Tipologia
D.M. 270 - TAF D
Crediti/Valenza
6
SSD dell'attività didattica
MAT/02 - algebra
Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

La teoria dei grafi, pur essendo una branca della matematica pura, ha numerose applicazioni nei più disparati settori della scienza e della tecnologia (ottimizzazione dei trasporti e delle risorse, architettura dei circuiti stampati, ecc.). Il corso si propone di fornire agli studenti le conoscenze di base della teoria dei grafi e di renderli in grado di studiare e risolvere le problematiche collegate anche utilizzando gli algoritmi introdotti durante il corso.

Oggetto:

Risultati dell'apprendimento attesi

L'allievo dovrà ottenere padronanza con gli argomenti, le tecniche e gli algoritmi introdotti durante il corso. In particolare dovrà dimostrare di saper risolvere, utilizzando le tecniche proprie della teoria dei grafi, vari problemi di tipo combinatorio che nascono tanto in ambito teorico quanto nelle applicazioni. Dovrà dimostrare di saper maneggiare concetti quali la traversabilità, la planarità, le diverse colorazioni ed etichettatura dei grafi.

Oggetto:

Programma

 

Grafi e sottografi: grafi, sottografi, grafi speciali, operazioni sui grafi, successioni dei gradi.
Grafi connessi e sconnessi: cammini e cicli, complemento di un grafo e grafi autocomplementari, vertici separanti e ponti, grafi euleriani, grafi hamiltoniani, blocchi. Matrici e alberi: grafi e matrici, alberi, il numero degli alberi non identici, alberi ricoprenti e teorema degli alberi e delle matrici.
Grafi planari e non planari: la formula di Eulero, condizioni algebriche necessarie planarità, grafi planari e poliedri, omeomorfismo, caratterizzazione dei grafi planari.
Colorazioni sui grafi: il numero cromatico, l'algoritmo k-colorabile, il teorema dei quattro colori, il polinomio cromatico, colorazioni sui lati.
Digrafi e networks: digrafi e tornei, networks e cammini critici, flussi e tagli. 

Graphs and subgraphs. Special graphs. Operations on graphs. Degree sequences. Connected and disconnected graphs. Paths and cycles. Complementary graph. Autocomplementary graphs. Cut vertices and bridges. Eulerian graphs. Hamiltonian graphs Blocks. Matrices. Trees. The number of nonidentical trees. Spanning trees.  Matrices and trees theorem. Planar and nonplanar graphs. Euler formula. Algebraic conditions to planarity. Planar graphs and polyhedra. Homeomorphism. Characterization of planar graphs. Colouring on graphs. Chromatic number. The k-colorable algorithm. The four color theorem. The chromatic polynomial. Colouring on edges.

 

Testi consigliati e bibliografia

Oggetto:

M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt. S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley. Dispense del Corso disponibili in rete.



Oggetto:

Note

ALGORITMI PER L'ALGEBRA, MFN1418 (DM270), 6 CFU, MAT/02, TAF D Libero, Ambito: a scelta dello studente 

Modalità di verifica/esame: Prova orale preceduta, nello stesso giorno, da una breve prova scritta.

Oggetto:
Ultimo aggiornamento: 17/12/2014 09:46

Location: https://www.matematica.unito.it/robots.html
Non cliccare qui!