Aller au menu Aller au contenu
L'école d'ingénieur en systèmes avancés et réseaux

> Formation > Cycle Ingénieur > Filière EIS

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 cet article Facebook Twitter Linked In
  • 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 :

cf. l'emploi du temps 2021/2022

Informations complémentaires

Code de l'enseignement : 3AMMA351
Langue(s) d'enseignement : FR

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 cet article Facebook Twitter Linked In

mise à jour le 25 juin 2015

Université Grenoble Alpes