in302-cours

IN302Graphes et algorithmesNotes de cours et exercicesMichelCouprieLe 11 janvier 2010L’unit´e Graphes et Algorithmes a son site web!http://www.esiee.fr/~coupriem/IN302/Vous y trouverez le plan du cours, les sujets des TD et des TP, des lectures conseill´ees,des liens sur d’autres sites parlant de graphes et d’algorithmes ...iTable des mati`eres1 Notions de base 11.1 Premi`ere d´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Repr´esentation en m´emoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.1 Repr´esentation d’un sous-ensemble . . . . . . . . . . . . . . . . . . 31.2.2 Op´erations sur un ensemble . . . . . . . . . . . . . . . . . . . . . . 4~1.2.3 Repr´esentation d’un graphe (E,Γ) . . . . . . . . . . . . . . . . . . 41.2.4 Repr´esentation d’un graphe (E,Γ) . . . . . . . . . . . . . . . . . . 5´1.2.5 Evaluation de la complexit´e d’un algorithme . . . . . . . . . . . . . 61.3 Graphes orient´es et non-orient´es . . . . . . . . . . . . . . . . . . . . . . . . 71.3.1 Le sym´etrique d’un graphe . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Graphe sym´etrique, graphe antisym´etrique . . . . . . . . . . . . . . 81.3.3 Fermeture sym´etrique . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.4 Graphe non-orient´e . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.5 R´eflexivit´e, antir´eflexivit´e . . . . . . . . . . . . . . . . . . . . . . . 101.3.6 Graphe complet . . . . . . . . . . . . . ...