Les réseaux complexes d’interaction sont au cœur de nombreux processus actuels tant dans le domaine technologique que dans le domaine sociétal. Il se basent sur une représentation à base de graphes qui sont eux-mêmes des outils conceptuels de modélisation offrant de riches capacités de calcul. Le développement des réseaux de communications et de télécommunications (téléphone, internet), la distribution énergétique et les réseaux de transport (routier, ferré et aérien) ont conduit à des phénomènes de propagation virale ou sociale via ces supports de réseaux et de graphes qui les contraignent ou les favorisent. L’objet de ce cours est de donner une base solide mathématique et algorithmique sur les graphes, sur leurs propriétés et leurs représentations afin de mieux maîtriser leurs propriétés et leurs impacts dans leurs domaines d’applications.

Les supports de cours pour les étudiants sont aujourd’hui sur la plateforme Moodle / Eureka de l’Université Le Havre Normandie.

Enseignant

  • Cyrille Bertelle, LITIS, Université Le Havre Normandie ;

Contenu

  • Chapitre 1 : Concepts fondamentaux (introduction, historique, définitions, représentations et visualisation des graphes, isomorphismes)
  • Chapitre 2 : Cheminement et connexité
  • Chapitre 3 : Arbres et arborescence
  • Chapitre 4 : Algorithmes de parcours des arbres et des graphes
  • Chapitre 5 : Graphes planaires
  • Chapitre 6 : Graphes eulériens et graphes hamiltoniens
  • Chapitre 7 : Recherche du plus court chemin
  • Chapitre 8 : Flots dans les réseaux

Bibliographie générale principale

  • Gondran M., Minoux M. (2009) Graphes et algorithmes (4e édition), Lavoisier.
  • Diestel R. (2005) Graph Theory, Springer.
  • Cabane R. (2000) Théorie des graphes, Techniques de l’ingénieur.
  • van Steen M. (2010) Graph Theory and Complex Networks, publication à compte d’auteur.
  • Larramendy Valverde I., Marie-Jeanne A. (2018) Introduction à la théorie des graphes, Ellipses
  • Newman M. (2018) Networks (2de Edition), Oxford University Press
  • Saché A. (1974) La théorie des graphes, Que-sais-je ?
  • Berge C. (1957) Théorie des graphes et ses applications, Dunod

Travaux de recherche développés sur le sujet