- Oggetto:
- Oggetto:
Teoria dei Grafi
- Oggetto:
Anno accademico 2006/2007
- Codice dell'attività didattica
- M8541
- Docenti
- Prof. Alessandro Andretta (Titolare del corso)
Prof. Marco Burzio (Titolare del corso) - Corso di studi
- Laurea in Matematica
- Anno
- 3° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- A scelta dello studente
- Crediti/Valenza
- 5
- Oggetto:
Sommario insegnamento
- 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 autoomplementari, 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 tagliTesti 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 disponibili presso il Centro Stampa e in rete - Oggetto:
