Retour aux Reseaux sociaux
Degre de separation : les calculs
Apprendre a calculer les distances et chemins dans un graphe social
40 min
Difficulte:
+70 XP
La distance entre deux sommets
Clique sur deux noeuds pour voir la distance
Clique sur un noeud, puis sur un autre pour calculer la distance
Definition
La distance entre deux sommets A et B dans un graphe est le nombre minimum d'aretes a parcourir pour aller de A a B.
Notation
- On note d(A, B) la distance entre A et B
- Si A et B sont directement connectes : d(A, B) = 1
- Si A = B : d(A, A) = 0
- Si A et B ne sont pas connectes : d(A, B) = infini
Exemple visuel
Considerons ce graphe (reseau d'amis) :
Alice ―――― Bob ―――― Charlie
| |
| |
Diana ―――― Eve ―――― Frank
Calculons quelques distances :
| De | A | Distance | Chemin |
|---|---|---|---|
| Alice | Bob | 1 | Alice → Bob |
| Alice | Charlie | 2 | Alice → Bob → Charlie |
| Alice | Frank | 3 | Alice → Diana → Eve → Frank |
| Diana | Charlie | 3 | Diana → Alice → Bob → Charlie |
Methode de calcul
Pour trouver la distance : 1. Lister tous les chemins possibles entre les deux sommets 2. Compter le nombre d'aretes de chaque chemin 3. Prendre le minimum
Exemple : Distance entre Diana et Charlie
Chemins possibles : - Diana → Alice → Bob → Charlie : 3 aretes - Diana → Eve → Frank → Charlie : 3 aretes
La distance d(Diana, Charlie) = 3
Erreurs courantes a eviter
- Oublier que la distance compte les aretes, pas les sommets
- Ne pas considerer tous les chemins possibles
- Confondre distance et degre d'un sommet
