Université Lyon 1
Arqus
Accueil  >>  Graphes et Applications
  • Unité d'enseignement : Graphes et Applications
Nombre de crédits de l'UE : 2
Code APOGEE : PL7053AP
    Responsabilité de l'UE :
BONNEVAY STEPHANE
 stephane.bonnevayuniv-lyon1.fr
04.81.92.99.28
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
Durée de projet en autonomie (PRJ)
3 h
Activité tuteurée personnelle (étudiant)
15 h
Activité tuteurée encadrée (enseignant)
3 h
Heures de Tutorat étudiant
0 h

* Ces horaires sont donnés à titre indicatif.

    Pré-requis :
Elève Ingénieur de Polytech Lyon, Spécialité Informatique, Année 4
    Compétences attestées (transversales, spécifiques) :

A l’issue de ce cours, les étudiants :

  • maîtriserons les algorithmes fondamentaux de la théorie des graphes, leur complexité ainsi que leur implémentation
  • serons capable de modéliser un problème sous forme d’un graphe, puis d’utiliser, d’adapter ou de créer un algorithme pour résoudre ce problème sur ce graphe
    Programme de l'UE / Thématiques abordées :
L’objectif est de vous présenter les concepts et les algorithmes fondamentaux de théorie des graphes, ainsi que les problématiques qui y sont associées.

Le plan du cours ets le suivant :
  1. Introduction
  2. Généralités sur les graphes
  3. Représentation d’un graphe en machine
  4. Parcours dans les graphes
  5. Arbre recouvrant
  6. Plus court chemin dans un graphe
  7. Coloration d’un graphe
  8. Graphes planaires
  9. Flots et réseaux de ransports
  10. Analyse des réseaux d’interactions
    Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 13/02/2024
SELECT MEN_ID, `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`, `PAR_ID` FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='21495' ORDER BY `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`