Graphes et algorithme: cours avancé.

Johanne Cohen

(Page en cours de construction)

Cours

• Introduction aux graphes : Cours .pdf
• le couplage d'un graphe : Cours .pdf
  • Terminologie sur les graphes
    • Définition
    • Un chemin augmentant/alternant
  • L’algorithme calculant un couplage maximum
    • Graphe contracté et chemin augmentant
    • Algorithme calculant un chemin augmentant de M
    • L’algorithme d’Edmonds (1965)
  • Couplage dans les graphes bipartis
    • Théorème de Hall
    • Méthode hongroise
• l'approximation et arbre de steiner : Cours .pdf
  • Définition du problème
  • Complexité (preuve de la NP-complétude)
  • Algorithme d'approximation

Enoncé des exercices :

• td sur les graphes planaires : le td .pdf, et les corrigés .pdf
  • Relation d'Euler,
  • Algorithme de coloration,
  • Ensemble indépendant.

Category: teaching