Théorie des graphes

  • See this page in english

    En bref

  • Code : N7EN14A

Objectifs

A partir de famille de problèmes pratiques, faire découvrir des concepts et des méthodes de base de la théorie des graphes. Au terme du cours, l'étudiant doit connaître une dizaine de problématiques importantes et des algorithmes appropriés.

Description

Objet de base

Parcours de longueur optimale : algorithmes de Moore-Dijkstra et de Ford.

Ordonnancement : analyse PER

Parcours hamiltoniens : méthodes de Demoucron et de Kaufman - Malgrange

Parcours eulériens

Flots maximaux : algorithme de Ford-Fulkerson

Affectations optimales : méthode hongroise

Propriétés relatives aux cycles, arbres et arborescences Arbres partiels de poids optimal : algorithme de Kruskal Graphes planaires : formule d'Euler.

Bibliographie

Graphes et hypergraphes - Auteur : Claude Berge - Editeur : Dunod , 1975
Graphes et Algorithmes - Auteur : Michel Gondran et Michel Minoux - Editeur : Eyrolles , 1980

Session 1 ou session unique - Contrôle des connaissances

ModalitéNatureCoefficientRemarques
CT (contrôle terminal) Oral/Ecrit100%Examen Théorie des Graphes

Session 2 - Contrôle des connaissances

ModalitéNatureCoefficientRemarques
CT (contrôle terminal) Oral/Ecrit100%Examen Théorie des Graphes

Contact(s)

DHAOU RIADH

Contactez l’ENSEEIHT

L’École Nationale Supérieure d'Électrotechnique, d'Électronique, d'Informatique, d'Hydraulique et des Télécommunications

2, rue Charles Camichel - BP 7122
31071 Toulouse Cedex 7, France

+33 (0)5 34 32 20 00

Certifications

  • Logo MENESR
  • Logo UTFTMP
  • Logo INP
  • Logo INPT
  • Logo Mines télécoms
  • Logo CTI
  • Logo CDEFI
  • Logo midisup