- français
- English
Fiches de cours
Graph theory
MATH-360
Enseignant(s) :
Maffucci Riccardo WalterLangue:
English
Summary
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer science and in practice.Content
1. Graphic sequences
2. Connectivity
3. Eulerian and Hamiltonian graphs
4. Forests and spanning trees
5. Planarity
6. Colourings
7. Extremal Graph Theory
Keywords
Graphs, isomorphism, complements, complete, bipartite, products, graphic sequences, connected, paths, circuits, cycles, Eulerian, Hamiltonian, trees, spanning trees, planar, maximal planar, polyhedra, colourings, forbidden graphs, extremal graphs.
Learning Prerequisites
Recommended courses
Mandatory for IN/SC: Analyse III, Physique générale I, Physique générale II, Probability and statistics
Learning Outcomes
By the end of the course, the student must be able to:- Illustrate simple examples of graphs satisfying certain properties
- State definitions and results of graph theory
- Verify hypotheses of theorems for applications
- Implement algorithms of graph theory
- Prove theorems and other properties
- Justify the main arguments rigorously
- Apply relevant results to solve problems.
Assessment methods
WRITTEN EXAM
Dans le cas de l'art. 3 al. 5 du Règlement de section, l'enseignant décide de la forme de l'examen qu'il communique aux étudiants concernés.
Resources
Bibliography
- Diestel : Graph Theory (Springer)
- Bollobas : Modern Graph Theory (Springer)
- Harris, Hirst, Mossinghoff : Combinatorics and Graph Theory (Springer)
- Harary : Graph Theory (Addison-Wesley).
Ressources en bibliothèque
Dans les plans d'études
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
5 - Matière examinée
Graph theory - Cours
2 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
5 - Matière examinée
Graph theory - Cours
2 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
5 - Matière examinée
Graph theory - Cours
2 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
Semaine de référence
Lu | Ma | Me | Je | Ve | |
---|---|---|---|---|---|
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | MAA330 | ||||
14-15 | |||||
15-16 | MAA330 | ||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
Cours
Exercice, TP
Projet, autre
légende
- Semestre d'automne
- Session d'hiver
- Semestre de printemps
- Session d'été
- Cours en français
- Cours en anglais
- Cours en allemand