Cours sur la Théorie des Graphes

Didier Maquin (©) 2003

Lors des travaux dirigés, nous utiliserons le logiciel Scilab. Scilab a été développé avec une philosophie très proche de celle de Matlab ; la différence essentielle est que Matlab est un logiciel commercial relativement onéreux alors que Scilab est d'utilisation gratuite. Le choix de Scilab est essentiellement lié à l'existence de la boîte à outils METANET permettant la manipulation des graphes. Vous pouvez aisément obtenir une description et un manuel d'utilisation de cette boîte à outils sur le site de l'INRIA Rocquencourt (en ligne, fichier HTML ou sous la forme d'un fichier téléchargeable au format PDF)

Téléchargements relatifs à l'enseignement

• Transparents utilisés en cours, partie 1, partie 2 et partie 3, sous la forme de fichiers au format PDF (à visualiser éventuellement ; n'essayez pas d'imprimer ces documents, il font plus de 400 pages et cela ne servirait à rien ! Pour la visualisation, il est préférable de télécharger le document (clic droit sur le lien, "enregistrer la cible sous...") pour le visualiser ensuite avec Acrobat Reader, la visualisation par l'intermédiaire des "plug-in" des navigateurs est médiocre)

• Le cours en format Postscript ou PDF

• Enoncé du TD numéro 1 en format Postscript ou PDF

• Enoncé du TD numéro 2 en format Postscript ou PDF

• Enoncé du TD numéro 3 en format Postscript ou PDF

Sites WEB intéressants (essentiellement en français !)

• Interview de Claude Berge, le père de la théorie moderne des graphes, décédé en juin 2002.

• Un excellent cours avec des applets java, vraiment très esthétique, par Christophe Rapine du Laboratoire de Gestion Industrielle et Conception Logistique (GILCO) de Grenoble (le meilleur que j'ai trouvé !).

• Un autre cours en ligne, par Didier Müller, Lycée Cantonal de Porrentruy en Suisse : intéressant !

• Un polycopié de cours par Pierre Lopez du Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS) de Toulouse.

• Le cours de Jean-Pierre Segado qui enseigne à l'Ecole Centrale d'Electronique.

• Quelques définitions à propos des graphes.

• Des exercices, des exercices, des exercices ... et des corrigés à l'EPFL !

• Une implémentation de l'algorithme de Dijkstra par un étudiant de l'Ecole Centrale de Paris.

• Différentes applets Java très bien faites par Kenji Ikeda.

• La théorie des graphes va parfois se nicher là où on ne l'attend pas comme dans cette conférence présentée au Musée des Arts d'Afrique et d'Océanie sur La logique de la longue ligne Vanuatu concernant le tracé de dessins sur le sable des îles... cela fait rêver !