Introduction à la théorie des graphes - 3AMMA351

Volumes horaires
- CM 13.5
- Projet -
- TD 12.0
- Stage -
- TP -
- DS -
Crédits ECTS
Crédits ECTS 2.5

Objectif(s)

La notion de graphe permet de modéliser de nombreuses situations complexes. Elle est essentielle pour la formulation de certaines situations, en particulier pour les problèmes d'optimisation.

A l'issue de ce cours, l'étudiant doit être capable de:

mobiliser les graphes comme outil de modélisation;
concevoir et comprendre des algorithmes sur les graphes;
comprendre des preuves de correction sur des algorithmes simples.

Responsable(s)

Yann KIEFFER

Contenu(s)

Graphes non-orientés:

chaines, cycles;
relations binaires; connexite;
arbres;
arbres couvrants de poids minimum.

Graphes orientés:

chemins, circuits;
tris topologiques;
accessibilité;
plus courts chemins;
certificats.

Prérequis

Notions élémentaires d'algorithmique:

structures de contrôle;
déroulement d'un algorithme.
Notions élémentaires de preuve mathématique:
preuve par récurrence;
preuve par l'absurde.

Notions mathématiques de base:

ensembles, produits cartésiens;
applications, injections, surjections, bijections.

Contrôle des connaissances

E1: Examen de session 1: Épreuve écrite de 1h30, documents autorisés, calculatrice autorisée
E2: Examen de session 2: épreuve écrite d'1h30, ou orale de 30 min, suivant le nombre de candidats à l'épreuve, documents autorisés, calculatrice autorisée
CC: Contrôle continu: devoir à la maison

En cas d'impossibilité d'épreuve dans les locaux de l'école:
E1: Examen de session 1: épreuve orale de 5 min en visioconférence avec partage de documents, avec comme support le rendu d'un devoir à la maison dont le sujet est transmis 14 jours auparavant.
E2: Examen de session 2: épreuve orale de 30 min en visioconférence.

Calendrier

Le cours est programmé dans ces filières :