IN101 - cours 13 - 17 de19 ecembre 2010

Un probl`eme concretFonctionnemnt d’un GPSIN 101 - Cours 1316 d´ecembre 2011pr´esent´eparMatthieu FiniaszUn probl`eme concret Un probl`eme concretFonctionnemnt d’un GPS Fonctionnemnt d’un GPS On repr´esente chaque intersection par un nœud, On cr´ee ainsi un graphe orient´epond´er´e, les nœuds sont reli´es par des branches qui ont : le GPS cherche un plus court chemin dedansun sens optimiserunpoidssurunchemindeA`aB. des poids (distance, temps, vitesse...)MotivationsLes graphes mod´elisent : r´eseaux de communication (routes, t´el´ecoms, m´etro...), circuits ´electriques, tˆaches et d´ependances/ant´eriorit´e...Les graphes15438726D´ efinitions D´ efinitionsUn graphe orient´e G (directed graph) est un couple (S,A)ou:` Un graphe orient´e G (directed graph) est un couple (S,A)ou:`S est un ensemble de sommets (vertex/vertices), S est un ensemble de sommets (vertex/vertices),A est un sous ensemble de S ×S (les arcs). A est un sous ensemble de S ×S (les arcs).Une suite d’arcs est un chemin.1 15 54 43 3Sommets8 87 72 2Chemin deArcslongueur 46 6D´ efinitions D´ efinitionsUn graphe orient´e G (directed graph) est un couple (S,A)ou:` Mˆemes d´efinitions pour un graphe non-orient´e (undirected graph):S est un ensemble de sommets (vertex/vertices), les arcs s’appellent des arˆetes (edges).A est un sous ensemble de S ×S (les arcs).Un arbre (g´en´eral) est un graphe non-orient´e, sans cycle, connexeUne suite d’arcs est un chemin ...