B104 – Théorie des graphes et combinatoire

Posted by admin  at juin 7th, 2012

Objectifs :

• Fournir les concepts de base concernant les graphes.
• Souligner l’apport des graphes en informatique en tant qu’outil de modélisation.
• Présenter certains algorithmes fondamentaux.
• Initier aux difficultés de la combinatoire

Contenu :

• Graphes, graphes simples, graphes orientés, bipartis, eulériens et hamiltoniens, planaires.
• Cheminement et connexité. Fermeture transitive. Graphes sans circuit. Arbres et arborescences.
• Parcours de graphes. Arbres de poids minimum. Ordonnancement. Chemins extrémaux. Flot maximum et problèmes d’affectation.