Deux exercices de graphes

Exercices sur représentations de réseaux sociaux

Nous vous proposons ici deux exercices de graphes pour modéliser des réseaux sociaux. Ils peuvent par exemple servir d’entraînement en cours de SNT (Sciences Numériques et Technologie), c’est-à-dire qu’un élève de seconde doit être capable de les mener à bien. Ils ne devraient pas trop torturer vos neurones.

Exercice 1

Pour certains réseaux, par exemple Facebook, la relation est réciproque. A est ami avec B et donc B est ami avec A. Le graphe qui résume ce type de relation est dit non orienté. Concrètement, on relie les noms des personnes par des traits appelés arêtes et non par des flèches.

On suppose donc un réseau de ce type.

Ce premier exercice permet de se placer à un moment de l’Histoire.

Nous sommes en 1530. Le roi de France François 1^er s’oppose à ses deux ennemis jurés : l’empereur Charles Quint et le roi d’Angleterre Henri VIII. Politiquement, ce dernier est assez isolé mais il maintient des canaux diplomatiques : avant d’épouser puis de faire décapiter Anne Boleyn, il est très amoureux d’elle et la future reine, déjà influente, ne laisse pas indifférent l’ambassadeur de France, Gilles de la Pommeraie. Vis-à-vis de Charles Quint, la politique de François est un savant équilibre de démonstrations de force et de tentatives de rapprochement (qui ne durent jamais très longtemps). La force, c’est notamment l’alliance avec le sultan Soliman 1^er qui a envahi une partie de la Hongrie dont le roi, futur empereur Ferdinand 1^er, n’est autre que le frère de Charles Quint. Le rapprochement, c’est son mariage avec la propre sœur de celui-ci, Éléonore d’Autriche.

• Imaginer un graphe d’amitié entre ces protagonistes. Il s’agit d’amitié au sens large : amour, fratries, liens professionnels… Mais pas de lien direct entre des monarques qui s’opposent !


• En déduire la matrice d’adjacence, à présenter sous forme de tableau (respecter l’ordre alphabétique). Par convention, on n’est pas ami avec soi-même.

Corrigé 1

Le graphe ci-dessous a été réalisé avec le logiciel gratuit yEd. Il ne fallait pas oublier qu’Éléonore est la sœur de Ferdinand.

Tableau (Excel) :

On remarque la symétrie qui caractérise les graphes non orientés.

Exercice 2

Sur d’autres réseaux, par exemple X et Instagram, le fait de suivre quelqu’un n’implique aucune réciprocité. Le type de graphe est donc différent puisqu’il ne comporte pas d’arêtes mais des arcs (représentés par des flèches).

Adam et Betty suivent Charlie. Celui-ci suit Adam, Daniel, Elliott et Franck. Daniel, Elliott, Franck et Greg suivent Adam. Helen suit Greg et réciproquement. Ingrid suit Betty, Helen et Franck. Joan est suivie par Daniel.

• Représenter le graphe correspondant à la situation (indiquer la première lettre de chaque prénom).


• Présenter la matrice d’adjacence.

Corrigé

Le graphe possède dix nœuds. La difficulté consiste surtout à bien les placer pour que le résultat ne soit pas trop brouillon !

Ci-dessous, il a été réalisé en ligne avec Graph Online. Notez que l'on peut éviter les croisements d'arcs.

Ce logiciel sépare les valeurs de la matrice par des virgules mais en principe on n’écrit rien entre les nombres.