Définition et vocabulaire
La dernière structure à connaître est un graphe. Il va nous aider à représenter des informations reliées entre elles (comme les arbres) mais sans lien de parenté.
Définition
Graphe
Un graphe est un ensemble de sommets (vertices) reliés entre eux via des arêtes (edges).
On peut associer une information aux sommets (et aux arêtes) du graphe. On parle alors de graphe étiqueté.
Orienté / Non orienté
Lorsque les sommets sont reliés dans un seul sens, on dit que le graphe est orienté, et les liens sont appelés arcs.
Dans un graphe non orienté, on dit que deux sommets sont adjacents s'ils sont reliés par une arête.
Exemple d'un graphe
Le graphe non orienté ci-contre possède 6 sommets.
La disposition des sommets n'a pas d'importance. On s'intéresse uniquement aux sommets et à leurs relations.
Vocabulaire
Voisinage
Si deux sommets sont reliés par une arête, alors on dit que l'un est voisin de l'autre. Donc tous les sommets adjacents entre eux sont voisins entre eux.
Le nombre de voisins d'un sommet est appelé degré.
Dans le cas d'un graphe orienté, on parle de :
- degré entrant pour compter les sommets qui arrivent à ce sommet
- degré sortant pour compter les sommets qui partent de ce sommet
Chemin
Un chemin dans un graphe est une suite de sommets possibles en suivant les arêtes ou les arcs du graphe.
Exemple : Il existe un chemin reliant 5 à 1 qui est 5 - 4 - 6 - 1
Un chemin est dit simple s'il ne passe pas deux fois par la même arête ou le même arc.
Cycle
Un cycle dans un graphe est un chemin simple qui commence et termine au même sommet.
Distance
La longueur d'un chemin est le nombre d'arêtes ou d'arc qui composent le chemin.
On définit la distance entre deux sommets comme étant la longueur du plus court chemin existant entre ces deux sommets.
Dans le cadre d'arêtes ou d'arcs étiquetés avec une valeur numérique, on parle de poids et on peut sommer ces poids pour connaître le coût d'un chemin.
Connexité
Un graphe non orienté est connexe si pour toute paire de sommets il existe un chemin reliant ces deux sommets.
Un graphe orienté est connexe si son graphe non orienté (obtenu en perdant le sens de tous ses arcs) est connexe.
Un graphe orienté est fortement conenxe si pour toute paire de sommets, il existe un chemin reliant ces deux sommets dans chaque sens.