Algebraic Combinatorics
A.Y. 2023/2024
Learning objectives
The course aims to give an introduction of graph theory and its applications.
Expected learning outcomes
Knowledge of the basic notions of graph theory and of some applications.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
Course syllabus
Definitions and examples of graphs, isomorphisms of graphs, subgraphs, graph invariants.
Eulerian graphs. The Konigsberg Bridges problem. The Chinese postman's problem
Hamiltonian graphs. The travelling salesperson problem.
Tournaments. Trees: elementary properties, enumeration of trees.
Planar graphs and colouring of graphs.
Networks and flows.
Matching. Hall's marriage theorem, Menger's theorem and their applications.
Latin squares in relation with algebraic structures.
Combinatorial circuits.
Eulerian graphs. The Konigsberg Bridges problem. The Chinese postman's problem
Hamiltonian graphs. The travelling salesperson problem.
Tournaments. Trees: elementary properties, enumeration of trees.
Planar graphs and colouring of graphs.
Networks and flows.
Matching. Hall's marriage theorem, Menger's theorem and their applications.
Latin squares in relation with algebraic structures.
Combinatorial circuits.
Prerequisites for admission
Basic knowledge of set theory and group theory.
Teaching methods
Traditional lectures.
Teaching Resources
F. Harary, "Graph theory", 1969
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
Assessment methods and Criteria
Some exercises will be assigned and published on the course webpage on the Ariel portal. Solving these exercises is a necessary condition to have access to the oral exam. In the oral exam, the student will be required to illustrate results presented during the course and will be required to solve problems regarding their applications in order to evaluate her/his knowledge and comprehension of the arguments covered as well as the capacity to apply them.
Educational website(s)
Professor(s)
Reception:
by appointment via e-mail
office 1014, Via Saldini 50