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 ...
Lesgraphesmoedlisent erseaux de communication (routes,
circuitselectriques,
at^ches
et
edpendances/anetrioriet...
telcoms,
metro...),
Motivations
4
Un
SAG
grapheorienet(MSceIeeM NcFpO est un ensemble desommets est un sous ensemble de
S)
est un couple (evcee/vxceSIed), (lesarcs).
S
(
S
,
A)
Denitions
o`u
:5
Un
Une
SAG
grapheorienet(MSceIeeM NcFpO est un ensemble desommets est un sous ensemble de
suite
d’arcs
est
un
S
chemin.
)
est un couple eceSIed, (vece/vx) (lesarcs).
S
(
S
,
A)
Denitions
o`u
:6
Un
SAG)
grapheorienet(MSceIeeM NcFpOest un couple ( est un ensemble desommets(evce/xevceSIed), est un sous ensemble deS(lesarcs).
Unesuited’arcsestunchemin.
Uncheminqui
boucle
S
est uncycle
.
S
,
A)
Denitions
o`u
:7
e^Mmesedfinitionspourunon-npaehtneroeirg les arcs s’appellent desaer^tes(eMNed).
Unarbre(egenral)estungraphenon-orienet,sans et dont on fixe un sommet comme racine.
enitions D
(gnMSceIeeM NcFpO
cycle,
connexe
):8
Repersentationenmachined'ungraphe
Onnepeutpasutiliserunestructuresimilaire`acelled’unarbre un sommet n’a pas unpere`unique _arbregeneral,eledafricemoemnupoimibss onveutpourvoiracecderdirectement`aunsommetdonen.
Il
y
aplusieursrepersentations,adapetesa`deirentsalgorithmes matrice d’adjacence _plus baese sur les sommets, listes de successeurs _plus baese sur les arcs.