Mesurer un graphe
Un graphe se lit, mais il se mesure aussi. Qui est au centre du réseau ? Le réseau est-il étendu ou resserré ? Est-il très connecté ou très clairsemé ? Ces mesures ont des noms précis, et ce sont celles qu'utilisent les réseaux sociaux pour te connaître.
Dans toute cette page, on travaille sur le graphe G2 de la séance précédente :
Ces définitions sont à lire, pas à apprendre par cœur
Chaque mesure ci-dessous est définie précisément. Ton travail n'est pas de retenir les mots, mais d'appliquer la définition au graphe qu'on te donne. C'est exactement ce qui sera évalué : lire une définition, et s'en servir.
La matrice des distances
Pour mesurer un graphe, il faut d'abord connaître toutes les distances entre ses sommets. On les range dans un tableau : la matrice des distances.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 3 | 1 | 2 |
| B | 0 | 1 | 2 | 2 | 2 | |
| C | 0 | 1 | 2 | 1 | ||
| D | 0 | 2 | 1 | |||
| E | 0 | 1 | ||||
| F | 0 |
Deux remarques d'économie :
- La diagonale ne contient que des 0 : la distance d'un sommet à lui-même est nulle.
- Il est inutile de remplir sous la diagonale : la distance de B à D est la même que celle de D à B (l'arête n'a pas de sens). Le tableau est symétrique.
L'excentricité d'un sommet
Définition
L'excentricité d'un sommet est la plus grande distance entre ce sommet et tous les autres sommets du graphe.
Autrement dit : « depuis ce sommet, à quelle distance se trouve le sommet le plus éloigné ? »
Pour A, on lit sa ligne dans la matrice : les distances sont 1 (B), 2 (C), 3 (D), 1 (E), 2 (F). La plus grande est 3, donc l'excentricité de A vaut 3.
Une excentricité faible signifie que le sommet est proche de tout le monde : il est bien placé dans le réseau.
Exercice - Excentricités
Complète le tableau des excentricités de G2, en t'appuyant sur la matrice des distances.
| Sommet | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Excentricité | 3 |
Correction
| Sommet | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Excentricité | 3 | 2 | 2 | 3 | 2 | 2 |
Pour chaque sommet, on prend la plus grande des distances vers les autres. Attention à bien lire la matrice en ligne et en colonne (elle n'est remplie qu'au-dessus de la diagonale) : pour B, les distances sont 1 (A), 1 (C), 2 (D), 2 (E), 2 (F), donc son excentricité est 2.
Le centre, le rayon, le diamètre
Ces trois mesures découlent directement des excentricités.
Définitions
Le centre d'un graphe est l'ensemble des sommets d'excentricité minimale.
Le rayon d'un graphe est l'excentricité minimale (celle du centre).
Le diamètre d'un graphe est l'excentricité maximale.
Le diamètre répond à une question très concrète : quelle est la plus grande distance qui sépare deux membres du réseau ? Autrement dit, dans le pire des cas, combien d'intermédiaires faut-il pour aller de n'importe qui à n'importe qui ? Retiens bien cette mesure, on y reviendra à la prochaine séance.
Exercice - Centre, rayon, diamètre
D'après tes excentricités : quel est le centre de G2 ? Son rayon ? Son diamètre ? Justifie chaque réponse en citant la définition.
Correction
Les excentricités sont : A = 3, B = 2, C = 2, D = 3, E = 2, F = 2.
- Centre : les sommets d'excentricité minimale. Le minimum est 2, atteint par B, C, E et F. Le centre peut donc contenir plusieurs sommets.
- Rayon : l'excentricité minimale, donc 2.
- Diamètre : l'excentricité maximale, donc 3 (atteinte par A et D, qui sont bien les deux sommets les plus éloignés l'un de l'autre).
Graphe complet et densité
Dernière question : ce réseau est-il très connecté, ou pas tellement ? Pour le dire, il faut un point de comparaison : le réseau où tout le monde connaît tout le monde.
Définitions
Un graphe est complet lorsque tous les sommets sont reliés deux à deux : tout le monde est directement relié à tout le monde.
On note \(K_n\) le graphe complet à \(n\) sommets. Il possède \(\dfrac{n(n-1)}{2}\) arêtes.
La densité d'un graphe à \(n\) sommets est le rapport entre son nombre d'arêtes et le nombre d'arêtes du graphe complet associé \(K_n\).
Exercice - Densité de G2
G2 a 6 sommets et 7 arêtes.
- Combien d'arêtes a le graphe complet associé, \(K_6\) ? Pose le calcul.
- Quelle est la densité de G2 ? Donne le résultat sous forme de fraction.
Correction
- \(K_6\) a \(\dfrac{6 \times 5}{2} = 15\) arêtes.
- Densité \(= \dfrac{7}{15}\), soit environ 0,47. Moins de la moitié des amitiés possibles existent réellement.
Exercice - Les bornes de la densité
- Un graphe peut-il avoir plus d'arêtes que son graphe complet associé ? Justifie.
- Quelle est donc la valeur maximale que peut prendre une densité ?
- Que dire d'un graphe dont la densité vaut 0 ?
Correction
- Non. Le graphe complet contient déjà toutes les arêtes possibles entre ces sommets : on ne peut pas en ajouter une de plus, il n'en reste aucune à créer.
- Au maximum, un graphe a autant d'arêtes que son graphe complet : la densité vaut alors \(\frac{n}{n} = 1\). La densité est donc toujours comprise entre 0 et 1.
- Une densité de 0 signifie aucune arête : des sommets isolés, personne n'est relié à personne. Aucun réseau.
Ce qu'on retient
- La matrice des distances rassemble toutes les distances du graphe. Elle est symétrique, et sa diagonale est nulle.
- L'excentricité d'un sommet est la plus grande distance entre lui et les autres. Une faible excentricité signifie « proche de tout le monde ».
- Le centre est l'ensemble des sommets d'excentricité minimale (il peut en contenir plusieurs). Le rayon est cette excentricité minimale ; le diamètre est l'excentricité maximale.
- Le diamètre dit combien d'intermédiaires séparent, au pire, deux membres du réseau.
- La densité compare le nombre d'arêtes du graphe à celui du graphe complet \(K_n\) (qui a \(\frac{n(n-1)}{2}\) arêtes). Elle est toujours entre 0 et 1.
Et ensuite
Le diamètre de notre petit graphe vaut 3. Et celui du graphe de tous les humains de la planète ? La réponse est stupéfiante, et c'est le sujet de la prochaine séance.