Graphes

Vous allez découvrir les graphes.

Un réseau social a 6 abonnés : Fanny, Robin, Chloé, Tom, Elsa et Léo.

• Fanny est amie avec Robin, Chloé et Tom.
• Robin est ami avec Fanny et Tom.
• Chloé est amie avec Fanny, Elsa et Tom.
• Tom est ami avec tous les autres abonnés.
• Elsa est amie avec Chloé, Tom et Léo.
• Léo est ami avec Elsa et Tom.

Il existe un moyen plus "visuel" pour représenter ce réseau social : on peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le cercle) et chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite).

Ci contre ce que cela donne avec le réseau social décrit ci-dessus :

Ce genre de figure s'appelle un graphe. Les graphes sont des objets mathématiques très utilisés, notamment en informatique. Les cercles sont appelés des sommets et les segments de droites des arêtes.

Exercice 1

A l'aide de ce site, construisez un graphe de réseau social à partir des informations suivantes :

• Jade est ami avec Nino et Lily.
• Nino est ami avec Jade et Cléo.
• Cléo est ami avec Nino,Kaïs et Sina.
• Sina est ami avec Cléo,Kaïs et Lily.
• Lily est ami avec Jade,Sina et Kaïs.
• Kaïs est ami avec Cléo, Sina et Lily.

Voici quelques définitions sur les graphes :

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.

Exemple : Dans le graphe donné ci-dessus (graphe 1), Fanny-Chloé-Elsa-Léo 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.

exemple : La distance entre le sommet Fanny (graphe 1) et le sommet Léo est de 2 (chaîne Fanny-Tom-Léo). ATTENTION : on parle bien du nombre minimum d'arêtes, Fanny-Chloé-Elsa-Léo est aussi une chaîne entre Fanny et Léo mais dans ce cas, nous avons 3 arêtes.

excentricité : L'excentricité d'un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe.

Exemple 1 : dans le graphe 1 : distance (Chloé-Fanny) = 1 ; distance (Chloé-Tom) = 1 ; distance (Chloé-Elsa) = 1 ; distance (Chloé-Robin) = 2 ; distance (Chloé-Léo) = 2 ; nous pouvons donc dire que la distance maximale existant entre le sommet Chloé et les autres sommets du graphe est de 2 (distance (Chloé-Robin) et distance (Chloé-Léo)). Nous pouvons donc dire que l'excentricité de Chloé est de 2.

Exemple 2 : distance (Tom-Chloé) = 1 ; distance (Tom-Fanny) = 1 ; distance (Tom-Elsa) = 1 ; distance (Tom-Robin) = 1 ; distance (Tom-Léo) = 1 ; nous pouvons donc dire que l'excentricité de Tom est de 1.

centre : On appelle centre d'un graphe, le sommet d'excentricité minimale (le centre n'est pas nécessairement unique).

Exemple : Dans le graphe 1 tous les sommets ont une excentricité de 2 à l'exception du sommet Tom qui a une excentricité de 1, nous pouvons donc affirmer que le centre du graphe 1 est le sommet Tom.

rayon : On appelle rayon d'un graphe G, l'excentricité d'un centre de G.

Exemple : Tom a une excentricité de 1, c'est le centre du graphe 1, nous pouvons donc dire que le rayon du graphe 1 est de 1.

diamètre : On appelle diamètre d'un graphe G, la distance maximale entre deux sommets du graphe G.

Exemple : Dans le graphe 1 la distance maximale entre 2 sommets est de 2, nous pouvons donc dire que le diamètre du graphe est de 2.

Exercice 2

Déterminez le (ou les) centre(s) du graphe de l'exercice 1, en déduire son rayon. Déterminez le diamètre de ce même graphe.

Vous devrez utiliser Libre Office pour rédiger vos réponses. Une fois le travail terminé, vous rendez le travail ici.