Courses/THEG

From LRDE

Titre

Théorie des Graphes

Sigle

THEG

Enseignant

Alexandre Duret-Lutz, Jim Newton

Période

S2, Ing1

Public

Tronc-commun

Contrôle

Partiel

Durée

12h

Optionnel

non

Module

Informatique Fondamentale

Prérequis

ALGO

Objectifs

L'objectif du cours est triple. Il s'agit d'une part d'introduire le vocabulaire de la théorie des graphes et d'illustrer sont vaste champ d'applications. D'autre part ce cours prolonge le cours d'algorithmique en étudiant la complexité de chaque algorithme présenté (dont certains utilisant de la programmation dynamique). Enfin ce cours relie les graphes à la théorie des groupes (abordée brièvement en classes préparatoires).

Plan
  • Histoire de la théorie des graphes et applications diverses (Ponts de Königsberg, calcul de résistance dans un circuit, démonstration de la formule des alcanes, formule de Cayley)
  • Vocabulaire (graphe orienté, non-orienté, arbre, cycle, composantes, rayon, diamètre, clique, nombre chromatique, ...)
  • Représentation et codage des graphes (listes et matrices d'ajacence)
  • Calculs de plus courts chemins (Dijkstra, Bellman-Ford, Floyd-Warshall,...).
  • Lien avec la théorie des groupes (Plus court chemin = calcul d'une puissance de matrice)
  • Graphes planaires (Formule d'Euler, Théorème de Kuratowsky, Théorème des 4 couleurs)
  • Graphes cordaux (Triangulation, LexBFS, Coloration gloutonne, graphes d'intersection, application à l'allocation de registres).
Documentation
  • Introduction a l'algorithmique. Thomas H. Cormen. Edition Dunod
  • Introduction to algorithms. Cormen, Leiserson, Rivest and Stein.
Support
Journaux