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
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érequisNotions é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.
Informations complémentaires Code de l'enseignement : 3AMMA351
Langue(s) d'enseignement : 
Le cours est rattaché aux structures d'enseignement suivantes :
Vous pouvez retrouver ce cours dans la liste de tous les cours.
Bibliographie « 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
mise à jour le 25 juin 2015