Les graphes
En informatique et en mathématiques, un graphe est une structure de données qui modélise un ensemble d'éléments appelés sommets (ou nœuds) reliés par des arêtes (ou liens). Un graphe peut être utilisé pour représenter des relations entre des objets.
Utilisation
Les graphes sont largement utilisés pour modéliser et résoudre des problèmes dans de nombreux domaines :
- Réseaux sociaux : Les sommets représentent les utilisateurs, et les arêtes représentent les connexions entre eux ;
- Routage et navigation : Les sommets représentent des lieux (villes, intersections), et les arêtes représentent les routes ;
- Réseaux informatiques : Les sommets modélisent des appareils (ordinateurs, serveurs), et les arêtes représentent les connexions physiques ou logiques ;
- Biologie : Les graphes servent à représenter des interactions protéiques ou génomiques ;
- Planification : Les graphes sont utilisés pour organiser des tâches avec des dépendances (diagrammes de Gantt) ;
- Recherche sur le Web : Les pages web sont modélisées comme des sommets, et les liens hypertexte comme des arêtes ;
- ...
Types de graphe
Il existe 2 graphes différents : les graphes orientés, et les graphes non orientés.
Graphes non orientés
Abrégé en GNO, les graphes non orientés disposent d'arêtes reliant les sommets entre eux par un trait. Il n'y a aucune orientation, les sommets sont reliés entre eux dans les 2 sens.
Graphes orientés
Abrégé en GO, les graphes orientés disposent d'arcs reliant les sommets entre eux par une flèche. Il n'y a un sens suivant la flèche, le sommet A peut aller vers le sommet B, mais le sommet B ne peut pas aller vers le sommet A.
Propriétés
Un chemin (ou une chaîne) est une séquence de sommets, allant d'un sommet de départ pour aller à un sommet de destination, en passant par différentes arêtes (ou arcs) du graphe.
D'après le GNO plus haut, pour aller du sommet C au sommet E, il existe la chaîne C - A - B - E.
Un cycle est un chemin (ou une chaîne) dont le sommet de départ est également le sommet d'arrivée.
On les repère très souvent par une forme "circulaire" d'arêtes entre les sommets.
D'après le GNO plus haut, il y a un cycle avec les sommets B - E - D.
Le degré d'un sommet correspond au nombre de liens d'un sommet.
Dans un GNO, on note d(Sommet) = x le degré d'un sommet.
D'après le GNO plus haut, d(A) = 2, d(C) = 1...
Dans un GO, on note d+(Sommet) = x le degré entrant d'un sommet, et d-(Sommet) = x le degré sortant d'un sommet.
On notera d(Sommet) = d+(Sommet) + d-(Sommet).
D'après le GO plus haut, d+(A) = 1, d-(A) = 2, d(A) = 3...
Matrices d'adjacence
Une matrice est un tableau contenant des entiers, représenté par cette notation :
En Théorie des Graphes, cette notation peut être utilisée pour représenter simplement un graphe. On utilise une matrice carrée (autant de colonne que de rangée) correspondant aux sommets.
L'objectif est de noter 1 dans la case où un sommet A est en lien avec un sommet B, 0 dans le cas contraire.
Cette technique s'applique aussi bien aux GO qu'aux GNO.
Avec le GO présenté au début du cours, on aurait la matrice suivante :
On lit : A a une arête vers B et C, B a une arête vers A et E ...
Dans un GNO, la matrice d'adjacence est symétrique !
Listes d'adjacence
Une liste d'adjacence est la seconde méthode de représentation des graphes.
Cette méthode consiste à associer pour chaque sommet du graphe une liste des sommets vers qui il peut aller.
Dans un GNO, on associe, pour chaque sommet, la liste de ses voisins.
Avec le GNO du cours :
- A : B, C
- B : A, D, E
- C : A
- D : B, E
- E : B, D
Dans un GO, il y a 2 listes : la liste des prédécesseurs (les arcs entrants) et la liste des successeurs (les arcs sortants).
Avec le GO du cours :
- Prédécesseurs :
- A : C
- B : A, D
- C : A
- D : E
- E : B
- Successeurs :
- A : B, C
- B : E
- C : A
- D : B
- E : D