US331B

Graphes, Couplages et Colorations


2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

Bases en optimisation et théorie des graphes

Objectifs pédagogiques

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

Connaître les résulats fondateurs des problématiques de couplage maximum et de coloration.

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.

Modalités de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003