Théorie des Graphes

Ce cours de Théorie du Graphe (disponible aussi sur https://sites.google.com/a/esi.dz/informatiqueblida/theorie-du-graphe/annee-universitaire-2019-2020) est destiné aux étudiants de deuxième année Informatique (L2).

L'objectif de ce cours est de :

  • Savoir modéliser certains problèmes afin de les résoudre à l’aide des techniques et des algorithmes simples. 
  • Comprendre les notions de graphes orientés et non orientés.
  • Maîtriser les algorithmes de recherche des composantes connexes (Tarjan), des plus courts chemins (Bellman et Dijkstra), des arbres couvrants minimaux (Kruskal et Prim), des flots maximaux (Ford-Fulkerson), de coloration des sommets (Welch-Powell et Dsatur), etc.