Théorie des graphes

Contenus

Objectif du Cours

Ce cours vise à présenter les concepts de base, les sujets et les résultats de la théorie moderne des graphes avec un objectif de techniques applicables notamment aux sciences sociales.

Contenu du Cours

Concepts théoriques de base des graphes : chemins et cycles, connectivité, arbres, sous-graphes couvrant, graphes bipartis, cycles hamiltoniens et d'Euler.
Algorithmes pour le chemin le plus court et les arbres couvrants.
Théorie de l'appariement.
Graphiques planaires.
Coloration.
Flux dans les réseaux, théorème de max-flow min-cut.
Graphiques aléatoires d'Erdös-Rényi.
Lemme de régularité de Szemerédi.
Graphiques infinis.
Applications en informatique et aux sciences sociales.

Acquis d'Apprentissage du Cours

A la fin de cours, l'étudiant doit être capable de :

1)connaître quelques classes importantes de problèmes de théorie des graphes ;
2) de formuler et de prouver des théorèmes centraux sur les arbres, l'appariement, la connectivité, la coloration et les graphes planaires ;
3)de décrire et d'appliquer quelques algorithmes de base pour les graphiques ;
4) d'utiliser la théorie des graphes comme outil de modélisation.

Ressources

Graph theory, Diestel, Reinhard., 4th ed.: Heidelberg: Springer, 2010.
Graph Theory with Applications, Bondy.and Murty, North-Holland, 1979
Graph Based Natural Language Processing and Information Retrieval / Rada Mihalcea, Dragomir Radev, Cambridge University Press, 2011.
Discrete Mathematics, An Open Introduction, Oscar Levin, at
http://discretetext.oscarlevin.com/
Proof Techniques in Graph Theory, Harary, F. , Academic Press, New York, 1969.
New Directions in the Theory of Graphs, Harary, F., Academic Press, New York, 1973.

Intitulés des Sujets

Système d'évalution

Evalution de la Compétence

Tableau de la Charge de Travail