Réseaux sociaux et graphes

FICHE DE REVISION

Réseaux sociaux et graphes

Ce qu’il faut savoir

Il est souvent possible de représenter un réseau social par un objet mathématique appelé graphe. Un graphe est composé de sommets et d'arêtes. 

[pic 1]         

Définitions :

● chaîne​ : Dans un graphe, une chaîne reliant un sommet x à un sommet y est définie par une suite finie d'arêtes consécutives, reliant x à y. Dans le graphe donné ci-dessus, A-D-E-C est une chaîne

● distance entre 2 sommets​ : La distance entre deux sommets d'un graphe est le nombre ​minimum​ d'arêtes d'une chaîne allant de l'un à l'autre. La distance entre le sommet A et le sommet F est de 2 (chaîne A-D-F).

● excentricité​ : L'excentricité d'un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe. distance (A-B) = 1 ; distance (A-C) = 1 ;distance (A-D) = 1 ; distance (A-E) = 2 ; distance (A-F) = 2 ; nous pouvons donc dire que la distance maximale existant entre le sommet A et les autres sommets du graphe ci-dessus est de 2 (distance (A-E) et distance (A-F)). Nous pouvons donc dire que l'excentricité de A est de 2.

● centre​ : On appelle centre d'un graphe, le sommet d'excentricité minimale (le centre n'est pas nécessairement unique). Dans le graphe ci-dessus tous les sommets ont une excentricité de 2 à l'exception du sommet D qui a une excentricité de 1, nous pouvons donc affirmer que le centre du graphe ci-dessus est le sommet D

● rayon​ : On appelle rayon d'un graphe G, l'excentricité d'un centre de G. D a une excentricité de 1, c'est le centre du graphe ci-dessus, nous pouvons donc dire que le rayon du graphe ci-dessus est de 1.

● diamètre​ : On appelle diamètre d'un graphe G, la distance maximale entre deux sommets du graphe G. Dans le graphe ci-dessus la distance maximale entre 2 sommets est de 2, nous pouvons donc dire que le diamètre du graphe est de 2.

Ce qu’il faut savoir faire

Vous devez être capable de déterminer les grandeurs définies ci-dessus sur n’importe quel graphe.

ATTENTION : La lecture de cette fiche de révision ne remplace en rien l’étude approfondie du cours (lecture attentive). Cette fiche a uniquement pour but de vous donner des points de repère lors de vos révisions.

...