MATH-360 / 5 crédits

Enseignant: Vérité Mathieu Jean-Paul

Langue: Anglais


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. Planarity

4. Methods from linear algebra

5. Forests and spanning trees

6. Eulerian and Hamiltonian graphs

7. Colourings

8. Extremal Graph Theory

Keywords

Graph, isomorphism, complement, complete, bipartite, product, graphic sequence, connected, path, circuit, cycle, block, planar, maximal planar, polyhedron, dual, tree, spanning, Eulerian, Hamiltonian, colouring, forbidden subgraph, extremal graph.

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

Moodle Link

Dans les plans d'études

  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel

Semaine de référence

Jeudi, 13h - 15h: Cours GCA330

Jeudi, 15h - 17h: Exercice, TP GCA330

Cours connexes

Résultats de graphsearch.epfl.ch.