Cours d'algorithmique dans les graphes -- L3 (2019--2020)

Documents du cours



Exemples de graphes pour le projet

Remarques sur le projet à rendre. Le deadline est le 31 janvier. En plus du code, il faudra remettre un petit mode d'emploi pour permettre de tester facilement les programmes. Si il y a des choix d'implémentation spéciaux, signalez les ! Je testerai les programmes sur des graphes décrits selon le format prévu (donc comme ceux donnés ci-dessous): assurez vous que cela fonctionne.
NB: bug corrigé !

La plupart de ces graphes proviennent du site snap.stanford.edu/ . Ils ont été mis au format demandé pour le projet et parfois complété avec des valuations, restreints à une composante connexe, etc.
Pour les graphes importants, il faut afficher des données quantitatives (nombre de composantes connexes ou fortement connexes, nombre de composantes bi-connexes, distance d'un PCC entre deux sommets fixés, etc. plutôt que la liste des CC ou CFC, ou le tableau complet des distances des PCC !) Il faudra aussi utiliser ces grpahes pour distinguer les performances des différents algorithmes...

Graphes non-orientés:

Graphes orientés:

Graphes non-orientés valués:

Graphes orientés valués:

Réseaux de transport pour les flots:

Des (petits) graphes orientés valués (dans N), avec un noeud "e" et un noeud "s"...

Email: francois.laroussinie[at]univ-paris-diderot.fr