Graphes, Couplages et Colorations
Mis à jour le
Responsable(s) : Mme Safia KEDAD SIDHOUM
- Cours
Envie d'en savoir plus sur cette formation ?
Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :
Afficher le centre adapté à mes besoins
Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :
-
Durée : 22 heures
-
Package
-
2 crédits
Présentation
Public, conditions d'accès et prérequis
Prérequis
Bases en optimisation et théorie des graphes
Objectifs
L'existence de couplages parfaits et les problèmes de coloration ont des intérêts théoriques et applicatifs. L'objectif est de fournir les principaux résultats de nature structurelle ou algorithmique concernant ces problèmes.
Compétences et débouchés
Compétences
Connaître les résulats fondateurs des problématiques de couplage maximum et de coloration.
Informations pratiques
Contact
-
Département : Recherche opérationnelle
-
Tel : 01 40 27 22 67
-
Email : secretariat.ro@cnam.fr
-
Adresse : 2D4P20, 33-1-10, 2 rue Conté - 75003 Paris
Programme
Contenu
-
Rappel sur les couplages maximum et définition d'un couplage parfait. Cas des graphes bipartis. Cas général : théorème de Tutte.
-
Cas des graphes cubiques et théorème de Petersen. Aspects polyédraux et algorithmiques. Généralisation aux 2-facteurs.
-
Coloration des sommets d'un graphe. Exemples et applications. Borne supérieure pour le nombre chromatique et thérorème de Brooks.
-
Théorème de Gallay-Roy. Coloration listée. Utilisation de noyaux pour l'obtention de bornes pour le nombre chromatique listé.
-
Coloration des arêtes. Exemples d'applications. Théorème de König pour les graphes bipartis, théorème de Vizing. Autres exemples de problèmes de coloration.