Cours sur la Théorie des Graphes

Didier Maquin (©) 2002-2012

Encore un clic et vous pourrez expérimenter mon
Cours interactif sur la Théorie des Graphes

Note à l'attention des étudiants ENSEM 2A : créez votre login avec votre nom précédé de ENS (par exemple ENSMAQUIN)
Note à l'attention des étudiants ENSGSI 1A : créez votre login avec votre nom précédé de GSI (par exemple GSIMAQUIN)
Pour tous : utilisez votre vrai nom lors de l'enregistrement.

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.

Jusqu'à la version 4 de Scilab, la bibliothèque Metanet était incluse dans le logiciel de base. Depuis, la version 5 et la mise en place de ATOMS, le gestionnaire de modules externes, Metanet doit maintenant être chargé préalablement dans Scilab. Actuellement, ce module n'est pas opérationnel dans Scilab 5. De trop nombreux bugs rendent ce module inutilisable. Si vous souhaitez utiliser la bibliothèque Metanet, chargez une ancienne version de Scilab (par exemple Scilab 4.1.2 Windows ou Scilab 4.1.2 Mac Intel).

Téléchargements relatifs à l'enseignement (ENSEM)

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 des Sciences pour la Conception, l'Optimisation et la Production de Grenoble (GSCOP) (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.
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 !

Didier Maquin Didier.Maquin@univ-lorraine.fr