Cours 2018-2019

Théorie des graphes [SMATB254]

  • 5 crédits
  • 30h+22.5h
  • 1er quadrimestre
Langue d'enseignement: Français

Acquis d'apprentissage

Développer l'aptitude mathématique dans le cadre de l'algorithmique liée à la théorie des graphes et dans la modélisation du comportement dynamique de systèmes discrets. Ce cours introduit à l'analyse de la complexité théorique des algorithmes . L'intérêt du cours réside dans l'énorme potentiel de modélisation constitué par les graphes.

Contenu

Graphes connexes, eulériens et bipartis Plus court chemin Arbres et connectivite Graphes hamiltoniens Mariages, couplages et couvertures Coloriages d'arêtes Cliques, ensembles indépendants et l'impossible désordre Coloriages de sommets Graphes planaires Flots et coupes P, N P et N P-complétude Grands et très grands graphes

Disciplines

Théorie des graphes
Mathématiques
Théorie de l'information

Pré-requis

Mathématiques pour l'économie et la gestion 1 [ECGEB150] et Algèbre linéaire [INFOB123]

Co-requis

Les unités d’enseignement d’une des propositions suivantes:

  1. Analyse mathématique [INFOB227]
  2. Algèbre et géométrie analytique [SMATB107] et Analyse réelle I [SMATB103]

Mode d'évaluation

Modalites d'interrogation aux examens :

- en 1ère session, l'examen est écrit, il comporte des questions de théorie et des exercices.

- en 2ème session, l'examen est identique à celui de la 1ère.

Sources, références et supports éventuels

Syllabus disponible sur Webcampus

Langue d'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté des sciences
Rue de Bruxelles, 61
5000 NAMUR

Cycle

Etudes de 1er cycle