Portail nationalFormations hybrides

Graphes Avancés

Code UE : US331R

  • Cours
  • 2 crédits

Responsable(s)

Safia KEDAD SIDHOUM

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

Cours de base en graphes

Objectifs pédagogiques

Les graphes planaires constituent une classe de graphes étudiée d'une part pour leur cadre applicatif, conception de circuits électroniques notamment, et pour leur aspects plus théoriques liés notamment à la topologie. Il en est de même pour les problèmes hamiltoniens avec les probématiques de tournées de véhicules. Les graphes parfaits ont des propriétés structurelles très fortes, leur étude permet d'acquérir des compétences essentielles pour tout chercheur en théorie des graphes. La compréhension de ces problématiques est un atout pour tout chercheur qu'il soit au sein du centre recherche et développement d'une entreprise ou d'un établissement universitaire.

Compétences visées

Connaître les résulats fondateurs des problématiques de cycles hamiltoniens, des graphes planaires et des graphes parfaits.

Contenu

  • Définition des graphes planaires et exemples. Formule d'Euler. Notion de mineur et Théorème de Kuratowski-Wagner.
  • Coloration des graphes planaires. Définition de graphes bergiens, de graphes parfaits et exemples.
  • Autour du théorème fort des graphes parfaits.
  • Définitions de cycles et chaînes hamiltoniennes. Exemples. Résultats de complexité dans le cas général et des cas particuliers (par exemple le cas planaire). Conditions nécessaires et suffisantes d'existence.
  • Aspects polyédraux du problème du cycle hamiltonien. Méthodes de résolutions. Liens avec les problèmes de tournée et/ou autres applications.

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é