Théorie des graphes

  • Voir la page en français

    In brief

  • Code : N7EN14A

Objectives

To discover basic concepts and methods of graph theory from a family of practical problems. At the end of the lecture, the student must discover ten important problems and appropriate algorithms.

Description

·         Basic objects

·         Shortest path: Moore-Dijkstra and Ford algorithms.

·         Scheduling: PER analysis

·         Hamiltonian paths: Demoucron and Kaufman methods - Malgrange

·         Eulerian paths

·         Maximum flows: Ford-Fulkerson algorithm

·         Optimal assignments: Hungarian method

·         Properties relating to cycles, trees , Spanning trees with optimal weight: Kruskal's algorithm

·         Graph coloring, planar graphs: Euler's formula.

Bibliography

Graphs and hypergraphs - Author: Claude Berge - Publisher: Dunod, 1975

Graphs and Algorithms - Author: Michel Gondran and Michel Minoux - Editor: 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

Contact

The National Institute of Electrical engineering, Electronics, Computer science,Fluid mechanics & Telecommunications and Networks

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