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

> Formation > 1er Cycle

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 Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Volumes horaires

    • CM : 13.5
    • TD : 12.0
    Crédits ECTS : 2.5

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.
Contact Yann KIEFFER

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
E2: Examen de session 2
CC: Contrôle continu: Devoir à la maison



Informations complémentaires

Cursus ingénieur->Filière IR->Semestre 2
Cursus ingénieur->Filière EIS->Semestre 2

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 Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 25 juin 2015

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes