Vous êtes ici :

UFR de mathématique et d'informatique

Information importante

La page que vous consultez correspond à l'offre de formation 2023-2024.

Trouvez votre formation pour l'année universitaire 2024-2025

Graphes

  • Cours (CM) 20h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 14h
  • Travaux pratiques (TP) -
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

Cette UE présente les propriétés mathématiques fondamentales des graphes, et analyse les principaux algorithmes sur ceux-ci. Programme :
Graphes orientés et non-orientés : adjacence, degrés, voisinages ; chaînes, chemins, cycles et circuits ; composantes (fortement) connexes ; graphes eulériens ; arbres et arborescences. Algorithmes sur les graphes : parcours en largeur et en profondeur, tri topologique, composantes fortement connexes ; arbres couvrants minimum ; recherche de plus courts chemins ; réseaux de transports et recherche de flots maximaux. Couplages dans les graphes bipartis, applications.

Compétences à acquérir

À l'issue de cette UE une étudiante devrait savoir :
- les propriétés fondamentales des graphes et des arbres ;
- exprimer des problèmes dans le langage des graphes ;
- pratiquer les algorithmes sur les graphes.

Bibliographie, lectures recommandées

Références :
C. Berge : Graphes, 2e édition, Dunod, 1973.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein : Introduction to Algorithms, PHI Learning, 2010. Traduction française : Algorithmique. Dunod, 2010.

Pré-requis obligatoires

À l'entrée de cette UE, une étudiante devrait :
- connaître les rudiments de mathématiques discrètes (cf. PSC en S4) ;
- pratiquer la programmation impérative, choisir les structures de données appropriées et connaître l'algorithmique de base (cf. SDA1 en S3 et SDA2 en S4).

Contact

UFR de mathématique et d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact


Cursus master ingénierie (CMI)

Partenaires

Logo du CNRS
Logo Établissement associé de l'Université de Strasbourg
Logo du réseau Epicur
Logo de EUCOR, Le Campus européen
Logo de l'Inserm Grand Est
Logo de l'Inria

Labels

Logo du label Bienvenue en France
Logo du programme HRS4R
Logo du programme France 2030
Logo de Service Public+

Réseaux

Logo de France Universités
Logo de la Ligue européenne des universités de recherche (LERU)
Logo du réseau Udice
Logo de l'Université franco-allemande