Esisar rubrique Formation 2022

Graph Theory - 3AMMA351

  • Number of hours

    • Lectures 13.5
    • Projects -
    • Tutorials 12.0
    • Internship -
    • Laboratory works -
    • Written tests -

    ECTS

    ECTS 2.5

Goal(s)

The notion of graph is a useful tool in complex modelling. It may be needed in some cases, for example for modellign some optimization problems.

After following this course, the student should be able to:

  • use graphs as a modelling tool;
  • design and understand graph algorithms;
  • understand correctness proofs for simple graph algorithms.

Responsible(s)

Yann KIEFFER

Content(s)

Unoriented graphs:

  • chains, cycles;
  • binary relations; connexity;
  • trees;
  • minimum spanning trees.

Oriented graphs:

  • paths, circuits;
  • topological sorting;
  • accessibility;
  • shortest paths;
  • certificates.

Prerequisites

Basic algorithmic notions:

  • control structures;
  • Tracing an algorithm.

Test

E1: exam (1st session): 90 minutes written exam with documents and calculator
E2: exam (2nd session): 90 minutes written exam or 30 minutes oral exam
CC: homework assignment

Calendar

The course exists in the following branches:

see the course schedule for 2022-2023

Additional Information

Course ID : 3AMMA351
Course language(s): FR

The course is attached to the following structures:

You can find this course among all other courses.

Bibliography

« Théorie des graphes et applications », Jean-Claude Fournier, Hermès, 2006.