AIV15

ACTIVITÉ IV.1.5 : Exemples de graphes

Pour décrire la structure des réseaux sociaux nous avons besoin d'outils mathématiques. L'un de ces outils est le graphe. Dans un graphe, on place les sommets qui représentent les membres du réseaux et on les relie par des arêtes qui peuvent être orientées ou non, étiquetées ou même pondérées. On définite alors :
- la chaîne : suite finie d'arêtes reliant deux sommets ;
- la distance : chaîne la plus courte reliant deux sommets ;
- l'excentricité ou écartement : distance maximale entre un sommet et les autres sommets du graphe ;
- le centre : sommet (ou groupe de sommets) d'excentricité minimale ;
- le rayon : excenticité du centre du graphe ;
- le diamètre : distance maximale entre deux sommets d'un graphe.

1. Schématiser le graphe non orienté représentant les relations suivantes :
  Alban est ami avec Béatrice, Éric et Fatima.
  Béatrice est amie avec Alban, Charles, Déborah.
  Charles est ami avec Béatrice, Déborah et Gérald.
  Déborah est amie avec Béatrice, Charles et Gérald.
  Éric est ami avec Fatima et Alban.
  Fatima est amie avec Alban Éric.
  Gérald est ami avec Charles et Déborah

2. Faire un tableau à double entrée dans lequel seront notées les distances entre chaque sommet du graphe.

	A	B	C	D	E	F	G
A
B
C
D
E
F
G

3. Déterminer l'écartement pour chaque sommet du graphe.

	A	B	C	D	E	F	G	Écartement
A
B
C
D
E
F
G

4. Déterminer alors le centre, le rayon et le diamètre de ce graphe.

5. Schématiser le graphe orienté représentant les relations ci-dessous. les arêtes seront maintenant représentées par des flèches orientées du suiveur vers le suivi.
  Alban suit Béatrice et Déborah.
  Béatrice suit Alban.
  Charles suit Béatrice et Gérald.
  Déborah suit Alban, Charles et Fatima.
  Éric suit Alban et Déborah.
  Fatima suit Éric.
  Gérald suit Déborah.

6. Déterminer le centre, le rayon et le diamètre de ce graphe en suivant la même procédure que pour le graphe non orienté. Attention, il faut suivre le sens des flèches !