I. Définitions
Dans un réseau social, les sommets peuvent représenter les utilisateurs et les arêtes les relations entre ces utilisateurs.
Un graphe dont les arêtes n'ont pas de sens est appelé graphe non orienté.
Graphe n°1
Graphe n°2
II. Voisins, chemins et distances
Dans un graphe orienté, le sommet b est adjacent du sommet a s'il existe un arc allant de a vers b.
III. Représentations des graphes en machine
Les graphes peuvent être représentés en machine de deux façons différentes :
- par matrice d'adjacence ;
- par liste d'adjacence.
A. Matrice d'adjacence
Le graphe n°1 peut être représenté par la matrice d'adjacence suivante :
| Luke | Leia | Han | Yoda | Chewbacca | Obi-Wan |
|---|
| Luke | | X | X | X | | X |
| Leia | X | | X | | | X |
| Han | X | X | | | X | |
| Yoda | X | | | | | X |
| Chewbacca | | | X | | | |
| Obi-Wan | X | X | | X | | |
B. Liste d'adjacence
Le graphe n°2 peut être représenté par la liste d'adjacence suivante :
Qui-Gon : Obi-Wan, Yoda
Obi-Wan : Anakin, Yoda
Anakin : Obi-Wan, Padme, Palpatine
Padme : Anakin
Yoda : Qui-Gon
Palpatine : Dark Maul
Dark Maul : aucun sommet
IV. Excentricité, diamètre, centre et rayon
V. Représentation sagittale d'un graphe
Une matrice d'adjacence permet également de reconstruire la représentation d'un graphe.
Retour en haut ↑