Un graphe est un ensemble de liens qui relient des éléments entre eux.
Les liens sont représentés par des lignes appelées arêtes ou par des arcs.
Les éléments sont représentés par des points qu'on appelle sommets. Les éléments peuvent être des lieux, des personnes, des tâches, etc.
Dans la représentation graphique d'un graphe:
- Les sommets sont généralement identifiés par une lettre minuscule, une lettre majuscule, un nombre ou un mot.
- Les arêtes sont généralement nommées à l'aide des lettres désignant ses extrémités dans n'importe quel ordre.
Voici un exemple de graphe qui traduit une situation bien précise. Les sommets représentent des îles et les arêtes représentent des ponts.
Un graphe complet est un graphe dont chaque sommet est relié directement à tous les autres sommets.
Un graphe est connexe quand tout sommet peut être relié à tout autre sommet par une arête ou une suite d’arêtes. Le graphe connexe est un graphe en un seul morceau.
L'ordre d'un graphe correspond au nombre de sommets contenus dans un graphe.
Le nombre de fois qu’un sommet est touché par une arête est le degré de ce sommet .
Si plus d’une arête relient deux sommets, ces arêtes sont dites parallèles .
Une boucle est une arête qui lie un sommet à lui-même. Celle-ci compte pour une arête, mais pour 2 degrés.
Le degré du sommet C = 4
Le degré du sommet B = 2
Le degré du sommet A = 2
Le degré du sommet E = 2
Le degré du sommet D = 2
Le nombre d’arêtes du graphe est 6.
La somme des degrés de tous les sommets d'un graphe est toujours le double du nombre d'arêtes du graphe. Dans l'exemple précédent, il y a 6 arêtes et la somme des degrés de tous ses sommets est 12.
Les graphes sont une façon utile de représenter certaines situations. À l'aide de ces graphes, il est possible d'optimiser ou de résoudre des situations qui, à première vue, peuvent nous apparaitre très complexes. Voici quelques méthodes d'optimisation à l'aide des graphes.