IN101 - cours 13 - 11 de19 ecembre 2009

Matthieu Finiasz

Informations

• Publié par: Iddo
• Nombre de lectures: 25
• Langue: Français

Extrait

IN 101 - Cours 13
16 d´ecembre 2011
pr´esent´e par
Matthieu FiniaszUn probl`eme concret
Fonctionnemnt d’un GPS
1Un probl`eme concret
Fonctionnemnt 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 concret
Fonctionnemnt d’un GPS
■ On cr´ee ainsi un graphe orient´e pond´er´e,
■ le GPS cherche un plus court chemin dedans
optimiser un poids sur un de A `a B.
_
3Les graphesMotivations
Les graphes mod´elisent :
■ r´eseaux de communication (routes, t´el´ecoms, m´etro...),
■ circuits ´electriques,
■ tˆaches et d´ependances/ant´eriorit´e...
15
4
38
7
2
6
4D´efinitions
Un 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).
15
4
3Sommets8
7
2
Arcs
6
5D´efinitions
Un 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.
15
4
38
7
2
Chemin de
longueur 4
6
6D´efinitions
Un 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.
15
4
38
7
2
Cycle de
longueur 3
6
7D´efinitions
Mˆemes d´efinitions pour un graphe non-orient´e (undirected graph) :
les arcs s’appellent des arˆetes (edges).
Un arbre (g´en´eral) est un graphe non-orient´e, sans cycle, connexe
et dont on fixe un sommet comme racine.
15 Cycle de
longueur 5
4
3Sommets8Arêtes
7
2
Chemin de
longueur 3
6
8