Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Graphs and Applications - Upgrade - 4MMGAMN

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Number of hours

    • Lectures : 9.0
    • Tutorials : 9.0
    ECTS : 1.5

Goals

1° To get the students acquainted with graphs, which are an essential tool in combinatorial optimization, with many applications to various problems in networks, and which will appear in other courses.
2° The focus will be on modelizing problems and on the existence of general results and techniques.

Contact Wojciech BIENIA

Content

Graph search, components, trees, paths, flows and connectivity, min-cut (routing, fault-resistance), arc-disjoint paths (traffic assignment); Compatibility and conflicts: matching (client-resource assignment), coloring (frequency assignment), domination (location of concentrators); Miscellaneous: Eulerian cycles, Hamiltonian cycles (vehicle routing), broadcasting and gossiping, etc. Principles of operations research. Some other fundamental ideas of graph theory, some results and methods of combinatorial optimization like spanning tree, optimal path, scheduling, heuristic algorithms are exhibit by formulation and computation exercises.



Prerequisites

None but requires a good mathematical skill.

Tests

1 written exam (2 h).



N1=E1
N2=E2

Additional Information

Curriculum->Embedded Systems & Connect. Devices->Semester 7

Bibliography

W. BIENIA : "Introduction à la recherche opérationnelle et optimisation combinatoire", polycopié 2007
V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983
G. FINKE at al : “Recherche Opérationnelle et réseaux” traité IGAT, HERMES, 2002
M. SAKAROVITCH : "Optimisation combinatoire vol.I et II", Hermann, 1984
N.H. XUONG : "Mathématiques discrètes et informatique", Masson, 1992.
I. Charon, A. Germa, O. Hudry, Méthodes d’Optimisation Combinatoire, Collection Pédagogique de Télécommunication, Masson, Paris, 1996
M. Gondran, M. Minoux, Graphes et Algorithmes (2ème ed. revue et augmentée). Eyrolles, Paris, 1985.
J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. North-Holland, 1981.
A. Gibbons, Algorithmic Graph Theory.Cambridge University Press, 1988

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

Date of update January 15, 2017

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes