Graphs and Applications - Catch up course - 4PMIGAP1

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.

None but requires a good mathematical skill.

1 written exam (2 h).

• • MCC en présentiel **
    N1=E1 (examen écrit)
    N2=E2 (examen écrit)

MCC en distanciel
N1 = DM
N2 = DM

The course exists in the following branches:

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

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