Introduction à la théorie des graphes - 3AMMA351

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail

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

Objectifs

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.

Contenu

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ôles 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 :