Aller au menu Aller au contenu
Academics
Academics
Academics

> Study at Esisar > Engineering degree in Embedded Systems

Graph Theory - 3AMMA351

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Number of hours

    • Lectures : 13.5
    • Tutorials : 12.0
    • Laboratory works : -
    • Projects : -
    • Internship : -
    • Written tests : -
    ECTS : 2.5
  • Officials : Yann KIEFFER

Goals

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.

Content

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.

Tests

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 2021-2022

Additional Information

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

The course is attached to the following structures:

  • Team Mathematics for engineers

You can find this course among all other courses.

Bibliography

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

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

Date of update June 25, 2015

Université Grenoble Alpes