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 2021-2022 :
- Nombre d'inscrits : 17
- Taux de présence à l'évaluation : 100%
- Taux de réussite à l'évaluation : 88%
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
Rechercher une formation
RECHERCHE MULTI-CRITERES
Plus de critères de recherche sont proposés:
-
Vous pouvez sélectionner des formations grâce à un mot ou à une expression (chaîne de caractères) présent dans l’intitulé de la formation, sa description ou ses index (discipline ou métier).
Des mots-clés sont suggérés à partir du 3e caractère saisi, mais vous pouvez aussi rechercher librement. - Les différents items sélectionnés sont croisés.
ex: "Comptabilité" et "Diplôme" - Les résultats comprennent des formations du Cnam Liban (UE, diplômes, certificats, stages) et des formations proposées à distance par d'autres centres du Cnam.
- Les codes des formations du Liban se terminent par le suffixe LIB.
- Dans tous les cas, veillez à ne pas insérer d'espace ni de ponctuation supplémentaire.
Plus de critères de recherche sont proposés:
- Type de diplôme
- Niveau d'entrée
- Modalité de l'enseignement
- Programmation semestrielle
Chargement du résultat...
Intitulé de la formation |
Type |
Modalité(s) |
Lieu(x) |
|
---|---|---|---|---|
Intitulé de la formation
Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
|
Lieu(x)
Package
|
Lieu(x)
Paris
|
||
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
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é
Code UE : US331B
- Cours
- 2 crédits
Responsable(s)
Safia KEDAD SIDHOUM