Portail nationalFormations hybrides

Graphes, Couplages et Colorations

Code UE : US331B

  • Cours
  • 2 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Public, conditions d’accès et prérequis

Bases en optimisation et théorie des graphes

Présence et réussite aux examens

Pour l'année universitaire 2022-2023 :

  • Nombre d'inscrits : 21
  • Taux de présence à l'évaluation : 100%
  • Taux de réussite parmi les présents : 100%

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 visées

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é d'évaluation

  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé