Julien Sopena

Algorithmique avancée : Théorie des graphes

Université :

Université Paris Descartes - Paris V

Année :

3ème année de licence d'informatique

Le cours.

Cours 01 :

Théorie des graphes.. (1 par page / 8 par page).

Résumé :

Ce cours a pour but d'étudier une partie de la théorie des graphes. Ainsi, il abordera successivement : leurs propriétés, les algorithmes de parcours, la recherche des composantes fortement connexes, la caractérisation des cycles, le tri topologique, les graphes eulériens et hamiltoniens et pour finir les graphes planaires avec le théorème des quatre couleurs. Tout au long de celui ci, on insistera plus particulièrement sur la lecture de propriété formelle, sur les démonstrations et sur les notions de complexité.

TD 01 : Introduction

Contenus :

Cette première feuille de travaux dirigés est une transition avec les cours d'algorithmique des années précédentes ainsi qu'une introduction à la théorie des graphes. Dans un premier temps, au travers de l'étude de graphes donnés, elle met l'accent sur les difficultés de certaines propriétés. Puis dans un second exercice, elle fait la liaison entre les parcours d'arbres et les parcours de graphes. On profitera de cet exercice pour entraîner les étudiants aux calculs de complexité.

Ennoncé :

en ligne / pdf

TD 02 : Démonstration d'algorithme

Contenus :

Cette feuille de travaux dirigés, relativement courte (à lire...), a pour but de faire travailler les étudiants sur les démonstrations de propriétés. Elle prend pour cadre les graphes sans circuit et l'étude de leur diamètre.

Ennoncé :

en ligne / pdf

TD 03 : Composantes et représentation matricielle

Contenus :

Cette feuille de travaux dirigés, présente des algorithmes utilisant les parcours en profondeur vus dans la première séance. Ainsi on cherchera à calculer : composantes fortement connexes, graphe réduit et tri topologique. Pour ce dernier, on reviendra aussi sur la méthode matricielle permettant ainsi d'introduire les matrices d'adjacence et par la même occasion les matrices d'incidences.

Ennoncé :

en ligne / pdf

TD 04 : Graphes Eulériens

Contenus :

Dans cette dernière feuille de travaux dirigés, on reviendra sur les propriétés et théorèmes de caractérisation des graphes eulériens. Ces exercices laisseront une large place à la modélisation des problèmes.

Ennoncé :

en ligne / pdf

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License