Ticker

6/recent/ticker-posts

Header Ads Widget

partie 1 Cours Théorie des graphe





Introduction
Les graphes modélisent de nombreuses situations concrètes où interviennent des objets en
interaction.
• Les interconnexions routières, ferroviaires ou aériennes entre différentes
agglomérations,
• Les liens entre les composants d'un circuit électronique,
• Le plan d'une ville et de ses rues en sens unique, ...
Les graphes permettent de manipuler plus facilement des objets et leurs relations avec une
représentation graphique naturelle. L'ensemble des techniques et outils mathématiques mis au
point en Théorie des Graphes permettent de démontrer facilement des propriétés, d'en déduire
des méthodes de résolution, des algorithmes, ...
• Quel est le plus court chemin (en distance ou en temps) pour se rendre d'une ville à une
autre?
• Comment minimiser la longueur totale des connexions d'un circuit?
• Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville?

Objectifs : Appréhender les algorithmes des graphes utilisés dans les réseaux informatiques,
dans les problèmes de calcul de coût minimal, dans la recherche du meilleur chemin et dans les
méthodes d’ordonnancement (Gestion des projets,...)

Un graphe permet de décrire un ensemble d'objets et leurs relations, c'est à dire les liens entre
les objets.
• Les objets sont appelés les nœuds, ou encore les sommets du graphe.
• Un lien entre deux objets est appelé une arête
Graphes non orientés
Définition
Un graphe G est un couple (V,E) où
− V est un ensemble (fini) d'objets. Les éléments de V sont appelés les sommets du graphe
(Vertices en anglais).
− E est sous-ensemble de VxV. Les éléments de E sont appelés les arêtes du graphe (Edges
en anglais).
Une arête e du graphe est une paire e=(x,y) de sommets qui peut être notée simplement xy.
On dit que les sommets x et y sont les extrémités de l’arête e, que e est incidente en x et en y,
et que y est un successeur ou voisin de x (et vice versa).
On appelle ordre d’un graphe le nombre de sommets n de ce graphe.
La disposition des sommets et la longueur ou la forme (rectiligne ou incurvée) des arêtes n’a
aucune importance. Seule l’incidence des différentes arêtes et sommets compte.