| |
|
Les graphes sont une manière intuitive de représenter une relation binaire transitive entre des éléments d'un ensemble, une relation binaire transitive étant :
Définition (Graphe) Un Graphe est un couple (S,A), S étant un ensemble et A une partie de S×S. Les éléments de S sont appelés les sommets et ceux de A les arêtes.
Exemple : le réseau routier est un graphe dont les sommets sont les villes et les arêtes les routes qui mènent directement d'une ville à une autre sans passer par une ville intermédiaire.
La théorie des graphes étudie les propriétés de ces objets. Parmis les problèmes classiques figurent :
| Table of contents |
|
2 Algorithmes importants de la théorie des graphes |
Exemple : Si on reprend le réseau routier, une valuation possible est la longueur de la route.
Définitions
Graphe connexe
Graphe orienté
On parle de graphe orienté lorsque la relation symbolisée par A n'est pas symétrique, c'est-à-dire lorsque l'on n'a pas l'implication <<a∈S est en relation avec b∈S implique b est en relation avec a∈S>> (équivaut à <<(a,b)∈A implique (b,a)∈A>>). En d'autres termes, sur la représentation graphique, les arêtes ont une flèche.Valuation d'un graphe
Une valuation d'un graphe est une fonction qui, à chaque arête, associe un nombre réel.Algorithmes importants de la théorie des graphes