IN101 - cours 13 - 17 de19 ecembre 2010

IN 101 - Cours 1316 d´ecembre 2011pr´esent´e parMatthieu FiniaszUn probl`eme concretFonctionnemnt d’un GPS1Un probl`eme concretFonctionnemnt d’un GPS■ On repr´esente chaque intersection par un nœud,■ les nœuds sont reli´es par des branches qui ont :un sens_des poids (distance, temps, vitesse...)_2Un probl`eme concretFonctionnemnt d’un GPS■ On cr´ee ainsi un graphe orient´e pond´er´e,■ le GPS cherche un plus court chemin dedansoptimiser un poids sur un de A `a B._3Les graphesMotivationsLes graphes mod´elisent :■ r´eseaux de communication (routes, t´el´ecoms, m´etro...),■ circuits ´electriques,■ tˆaches et d´ependances/ant´eriorit´e...154387264D´efinitionsUn graphe orient´e G (directed graph) est un couple (S,A) ou` :S est un ensemble de sommets (vertex/vertices),A est un sous ensemble de S×S (les arcs).1543Sommets872Arcs65D´efinitionsUn graphe orient´e G (directed graph) est un couple (S,A) ou` :S est un ensemble de sommets (vertex/vertices),A est un sous ensemble de S×S (les arcs).Une suite d’arcs est un chemin.1543872Chemin delongueur 466D´efinitionsUn graphe orient´e G (directed graph) est un couple (S,A) ou` :S est un ensemble de sommets (vertex/vertices),A est un sous ensemble de S×S (les arcs).Une suite d’arcs est un chemin.≪ ≫Un chemin qui boucle est un cycle.1543872Cycle delongueur 367D´efinitionsMˆemes d´efinitions pour un graphe non-orient´e (undirected graph) :les arcs s’appellent des ...