IN101 - cours 13 - 11 de19 ecembre 2009

IN101 - cours 13 - 11 de19 ecembre 2009

-

Documents
79 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 ...

Sujets

Informations

Publié par
Nombre de visites sur la page 25
Langue Français
Signaler un problème

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