in302-cours

IN302Graphes et algorithmesNotes de cours et exercicesMichel COUPRIELe 20 mars 2009L’unité Graphes et Algorithmes a son site web !www.esiee.fr/~info/a2si/TC-ESIEE/Ggraph/ggraph.htmlVous y trouverez le plan du cours, les sujets des TD et des TP, des lectures conseillées, desliens sur d’autres sites parlant de graphes et d’algorithmes...iGGTable des matières1 Notions de base 11.1 Première définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Représentation en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.1 Représentation d’un sous-ensemble . . . . . . . . . . . . . . . . . . . 31.2.2 Opérations sur un ensemble . . . . . . . . . . . . . . . . . . . . . . . 4~1.2.3 Représentation d’un graphe (E, ) . . . . . . . . . . . . . . . . . . . . 41.2.4 Représentation d’un graphe (E, ) . . . . . . . . . . . . . . . . . . . . 51.2.5 Évaluation de la complexité d’un algorithme . . . . . . . . . . . . . . 61.3 Graphes orientés et non-orientés . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.1 Le symétrique d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Graphe symétrique, graphe antisymétrique . . . . . . . . . . . . . . . 81.3.3 Fermeture symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.4 Graphe non-orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.5 Réflexivité, antiréflexivité . . . . . . . . . . . . . . . . . . . . . . . . 101.3.6 Graphe complet . . ...