Algebraic Combinatorics

A.Y. 2018/2019
Lesson for
6
Max ECTS
42
Overall hours
SSD
MAT/02
Language
Italian
Learning objectives
The aim of this course is to introduce Graph Theory and some applications
Achievements: knowledge of the main applications of Graph Theory.

Course structure and Syllabus

Active edition
Yes
Responsible
MAT/02 - ALGEBRA - University credits: 6
Lessons: 42 hours
Syllabus
11. Introduction
12. Definitions and examples - Equivalence -labelled graphs- Subgraphs
13. Eulerian graphs
14. Konigsberg Bridge Problem. The Chinise postman's problem
15. Hamiltonian graphs
16. The travelling salesperson problem. A shortest-path algorithm
17. Tournaments
18.Trees
Terminoly and chracterizations of trees-Spanning trees and minimal spanning trees
Network models. The max flow min cut theorem
18. Planar graphs
19. Definitions and Kuratowski's Theorem
20. Matrices and Graphs
21. Latin squares
22. Matching
23. Hall's marriage theorem- menger's theorem and its applications
24. Applications to group theory
25.
Lesson period
First semester
Lesson period
First semester
Assessment methods
Esame
Assessment result
voto verbalizzato in trentesimi