Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > Articles à paraître dans les numéros à venir > SNT : des activités autour des graphes et des (...)

SNT : des activités autour des graphes et des réseaux sociaux
Moteur de recherche
Mis en ligne le 2 octobre 2019, par Florent Girod

Pourquoi enseigner la SNT quand on est professeur de mathématiques ? Comment utiliser des notions mathématiques pour illustrer les thématiques ?

La notion de graphe paraît particulièrement pertinente dans les thématiques ’réseaux informatiques’, ’réseaux sociaux’ et ’cartographie’. On présentera une manière de représenter des graphes grâce à la bibliothèque Graphviz de Python.

On présente ici une activité qui peut être menée en classe sur le thème des réseaux sociaux, illustrant à partir d’un cas concret certaines notions liées aux graphes.

Préambule

Pourquoi enseigner SNT ?

L’envie de découvrir de nouvelles choses est un moteur, pas seulement pour les élèves ! ça peut être le cas pour des enseignants, et si cet enseignement se fait par choix, cela peut apporter un enrichissement pour celui qui apprend.

Cela impose des temps de formation, souvent en autodidacte il faut bien dire. La communauté éducative s’est vite organisée et on trouve toutes sortes de ressources sur internet.

Sans faire un étalage exhaustif, je citerai les ressources issues du travail de David Roche [1] que l’on trouve ici.

Il est certain que notre posture d’enseignant est à revoir, certains thèmes à enseigner ne nous étant pas très familiers, et voire dans certains cas, avec des élèves pouvant être plus performants que nous !

Mais en tant que professeur de mathématiques, je pense pouvoir apporter un cadre de travail dans différents thème de cet enseignement, notamment faire par les graphes.

Dans mon établissement, nous nous sommes organisés, autant que faire se peut, pour que l’enseignant de SNT soit le professeur de mathématiques de la classe ; cela permet une meilleure prise en main de la classe et la possibilité de faire des liens entre les deux matières.

Il faut reconnaître aussi que le tableau n’est pas aussi idyllique ! Beaucoup d’heures de mathématiques sont perdues dans mon lycée, et le fait d’enseigner SNT permet une forme d’équilibre.

Organisation

Dans notre établissement (et j’ai remarqué que c’est le cas dans d’autres), nous avons une heure dédoublée chaque semaine et une heure pleine classe une semaine sur deux.

Les heures de dédoublement sont dédiées essentiellement à des séances en salle informatique, et les séances en classe entière à :

  • exposés d’élèves ;
  • visionnage ou étude de documents ;
  • échanges sur des sujets du programme.

Nous avons choisi qu’un même enseignant suive une classe sur l’ensemble de l’année ; certains collègues se sont ’spécialisés’ dans certaines thématiques et l’enseignent à des groupes d’élèves. Pour ma part, je trouve que d’une part, cela crée moins une ambiance de classe, un relationnel plus délicat avec les groupes. D’autres part, on aura du mal à faire un lien entre les différents thèmes, alors que certains sont possibles.

Graphe

La notion mathématique de graphe a toute sa place en SNT :

  • pour modéliser des réseaux informatiques ;
  • pour modéliser des réseaux routiers ;
  • pour modéliser des réseaux sociaux.

Il est donc important qu’un enseignant puisse créer à sa guise des graphes pour créer des documents pour ses élèves, ou pour illustrer des situations modélisées.

Python est un thème transverse en SNT ; plusieurs thèmes peuvent être traités d’une manière ou d’une autre par ce langage de programmation, et c’est l’un des objectifs de la classe de 2nde (en maths, sciences).

Il faut savoir qu’il est possible de créer des graphes par Python grâce à la bibliothèque graphviz. Cette bibliothèque, pour fonctionner, doit être importée et complétée par un module Graphviz à installer sur votre pc.

Un exemple de code donnant le graphe suivant :

code python

  1. from graphviz import Digraph #pour un graphe orienté
  2. from graphviz import Graph #pour un graphe non orienté
  3.  
  4.  
  5. g = Digraph('G', filename='reseau', engine='sfdp')
  6. #g = Graph('G', filename='reseau', engine='sfdp')
  7.  
  8. g.edge('A', 'E')#on crée deux sommets A et E qui seront reliés, de A vers E si on construit un graphe orienté
  9. g.edge('B' , 'A')
  10. g.edge('B', 'C')
  11. g.edge('C', 'B')
  12. g.edge('C', 'D')
  13. g.edge('C', 'G')
  14. g.edge('D', 'G')
  15. g.edge('E', 'F')
  16. g.edge('E', 'B')
  17. g.edge('F', 'B')
  18. g.edge('G', 'C')
  19. g.edge('G', 'H')
  20. g.edge('H', 'D')
  21.  
  22.  
  23. g.render(view=True)#on enregistre le fichier (nom précisé précédemment) et on visualise le document à chaque compilation, en format .pdf

Télécharger

détails d’installation

Cette installation se fait en plusieurs temps :

Tout d’abord, il faut installer la bibliothèque graphviz, ce qui se fait par un ’classique’ pip install graphviz

Mais il faut également installer un module Graphviz (avec une majuscule !).

Pour cela, on peut télécharger depuis cette page la version correspondant à votre système d’exploitation.

Reste une dernière opération, sous peine d’avoir ce message :

Sous Windows, il faut créer une forme de raccourci qui exécute Graphivz.
Ici un tutoriel pour vous aider sur ce point.

La bibliothèque graphviz installée, Graphviz installé et la manipulation décrite dans le tutoriel réalisés, les codes présentés dans cet article doivent fonctionner.

une activité


Nous proposons de modéliser un ’mini’ réseau social par un graphe, et de travailler sur certaines questions concrètes qui permettront d’aborder les notions plus générales sur les graphes, dans l’esprit de ce qui peut être fait en classe de 2nde.

consigne

Considérons la situation suivante :

  • Alan et Dylan sont amis ;
  • Alan et Éline sont amis ;
  • Bénédicte et Chloé sont amies ;
  • Bénédicte et Dylan sont amis ;
  • Bénédicte et Éline sont amies.

Une première modélisation de ce réseau d’amis peut se faire à l’aide du tableau
suivant :

Alan Bénédicte Chloé Dylan Éline
Alan
X
X
Bénédicte
X
X
X
Chloé
X
Dylan
X
X
Éline
X
X


Question 1 : Expliquez le fonctionnement de ce tableau.

réponse

Une croix est placée à l’intersection des prénoms qui désignent des personnes amies ; on considère dans ce modèle que si A est ami avec B, alors B est ami avec A.



On peut aussi modéliser ce réseau social par le graphe suivant :

Remarque pour l’enseignant : ce graphe est réalisé à partir d’un programme Python dont voici le code :

code python

  1. from graphviz import Graph, Digraph
  2.  
  3. g = Graph('G', filename='graphe', engine='sfdp')
  4.  
  5. g.edge('Alan', 'Eline')
  6. g.edge('Alan', 'Dylan')
  7. g.edge('Bénédicte', 'Chloé')
  8. g.edge('Bénédicte', 'Eline')
  9. g.edge('Bénédicte', 'Dylan')
  10.  
  11. g.render("mes-amis", view=True)

Télécharger



Question 2 : Expliquez le fonctionnement de ce graphe.

réponse

Chaque prénom est recensé et les prénoms en relation sont reliés par un segment.



vocabulaire : Chaque prénom représente un sommet du graphe ; le lien entre deux sommets est une arête du graphe.


Si on considère que seules les personnes amies peuvent communiquer entre elles, Bénédicte devra passer par Dylan, ou par Éline pour communiquer avec Alan. On dira que la distance entre Bénédicte et Alan est 2. La distance maximale entre Bénédicte et les autres personnes est 2 dans la situation présentée.

Question 3 : Compléter le tableau ci-dessous en notant la distance maximale correspondant à chaque personne :

Alan Bénédicte Chloé Dylan Éline
2

réponse

Alan Bénédicte Chloé Dylan Éline
3
2
3
2
2


vocabulaire : Cette distance maximale est appelée écartement d’un sommet.


Dans un graphe donné, un centre est un sommet dont l’écartement est minimal.

Un graphe peut comporter plusieurs centres. On interprète ici le centre du graphe comme l’élément d’un réseau par lequel l’information circulera le plus vite.

Question 4 : Qui est (sont) le (les) centre(s) du graphe dans notre situation ?

réponse

Bénédicte, Dylan et Éline sont les centres de ce graphe.



Le rayon d’un graphe est l’écartement d’un centre du graphe (c’est-à-dire la valeur minimale des écartements déterminés pour les différents sommets).

Question 5 : Quel est le rayon du graphe dans notre situation ?

réponse

Le rayon vaut ici 2.



Dans un graphe donné, le diamètre est la plus longue distance entre deux sommets.

Question 6 : Quel est le diamètre du graphe dans notre situation ?

réponse

Le diamètre vaut ici 3.

activité (suite)

Il est possible, en poursuivant l’activité précédente, de modéliser la transmission de l’information au sein d’un réseau social.

On peut proposer le modèle simple suivant, au sein d’un graphe non orienté : si quelqu’un, à un moment donné, est porteur d’une information, il la transmet à tous ses contacts.

On pourra alors étudier la propagation de l’information, étape par étape, au sein d’un réseau, et comparer les évolutions en fonction du point de départ de l’information.

Question : En reprenant le graphe précédent, coloriez les sommets touchés par une information au fur et à mesure de l’endroit d’où elles sont transmises. On traitera les deux cas suivants :

  • 1er cas : Alan a une information qu’il va transmettre ;
  • 2nd cas : Bénédicte a une information qu’elle va transmettre.


Question 2 : selon vous, qui transmet l’information le plus rapidement au sein d’un réseau ?

réponse

Ce sont les personnes qui sont centre du graphe.



Un graphe de grande taille :

Pourquoi ne pas demander aux élèves de réaliser un schéma représentant le graphe d’un réseau social de grande taille ?

En voici en tout cas une modélisation, avec une visualisation de transmission de l’information utilisant le même modèle que celui présenté précédemment :

Question 1 : Comment décririez-vous ce graphe ?

réponse

Ce graphe est composé de plusieurs sous-graphes. Un sous-graphe important et très dense, un second qui lui-même est composé de deux sous-graphes reliés par un seul sommet, et par ailleurs, de nombreux sommets isolés.



Question 2 : Quelle réalité peut modéliser ce graphe ?

réponse

Des réseaux sont parfois "refermés" sur eux-mêmes ; des réseaux peuvent être reliés entre eux, ou pas. Enfin, des individus peuvent être isolés.



Question 3 : Comment se transmet l’information dans chacune des deux parties distinctes du réseau ?

réponse

L’information circule rapidement au sein de sous-réseaux denses. Même si peu de personnes sont à l’origine de l’information transmise, la quasi totalité du réseau est informé en trois étapes.
Ce n’est pas le cas du sous-réseau moins dense, qui bien qu’ayant une proportion de personnes informées au départ comparable à celle de l’autre sous-réseau, la transmission est beaucoup moins efficace.

graphe orienté

Il est possible de poursuivre l’activité précédente pour introduire la notion de graphe orienté :

Prenons deux réseaux sociaux bien connus : Facebook et Twitter

Question 1 : Quelle est la différence principale dans le mode de fonctionnement de ces deux réseaux ?

réponse

La différence principale est la non réciprocité automatique des relations entre deux " amis " : A peut voir B sans que B ait besoin d’accepter.



Question 2 : Quelle adaptation faut-il faire pour représenter un réseau social du type Twitter par un graphe ?

réponse

On peut donc avoir des relations non symétriques.



Question 3 : Adapter une situation analogue à la précédente (un nombre limité de personnes concernées) pour modéliser des liens entre des personnes sur Twitter. Construire le graphe correspondant.

réponse

Si Alan est en lien avec Éline, mais que ce n’est pas réciproque et que Dylan est en lien avec Bénédicte sans que ce soit réciproque, on a le tableau suivant :

Alan Bénédicte Chloé Dylan Éline
Alan
X
X
Bénédicte
X
X
Chloé
X
Dylan
X
X
Éline
X

Voici le nouveau graphe adapté :



Ici une version ’papier’ de cette activité :

PDF - 2.4 Mo
fiche élève
PDF - 2.5 Mo
fiche enseignant

les codes

Pour réaliser des graphes de grande taille, j’ai utilisé le principe suivant : un réseau est modélisé par une matrice qui est associée à un graphe. Dans ce modèle, on placera un 1 chaque fois qu’une relation entre deux personnes existe, 0 sinon.

Si on modélise un graphe non orienté, la matrice sera symétrique.

Ainsi, créer une matrice de grande taille permettra de générer un graphe modélisant des réseaux sociaux de grande taille.

Ce programme

Zip - 1.9 ko

regroupe diverses fonctions permettant de :

  1. générer certains types de matrices associés à des réseaux ’classiques’ ;
  2. créer une matrice à partir de ces matrices de base ;
  3. représenter le graphe (orienté ou non) associé à la matrice précédente.

Remarque : ces programmes sont ’faits maison’ donc pas toujours optimisés ... et les Pythoneurs trouveront sans doute bien des points à améliorer !

Quelques exemples :

matrice connexe de taille n

Ce code

  1. def mat_connexe(n, p=0.2):
  2. """génère une matrice n*n avec des 0 et des 1 , 0 sur la diagonale, au moins un 1 par ligne, une probabilité de l'ordre de p d'avoir 1"""
  3. m=np.full(shape=(n, n),fill_value=0)#initialise un matrice n*n avec des 0
  4. for i in range(n):#ligne
  5. for j in range(n):#colonne
  6. if i != j:
  7. m[i][j] = int(random() < p)# 1 en position (i,j) avec un probabilité de p
  8. else:
  9. m[i][j] = 0#0 sinon
  10. for i in range(n-1):
  11. if sum(m[i]) == 0:#pour ajouter un 1 au cas où la ligne ne comporte pas du tout de 1
  12. m[i][randint(i+1, n-1)]=1#on place un 1 aléatoirement après la diagonale
  13. return m

Télécharger

permet d’obtenir par exemple :

  1. >>> mat_connexe(5)
  2. array([[0, 0, 0, 1, 1],
  3. [0, 0, 0, 0, 1],
  4. [0, 1, 0, 1, 0],
  5. [0, 0, 0, 0, 1],
  6. [0, 0, 0, 0, 0]])

Télécharger

On modélise ainsi un réseau social orienté peu dense constitué de 5 personnes.

On peut de même générer une matrice symétrique de même type.


deux cas classiques

Les fonctions suivantes permettent de générer des réseaux classiques (type ’serveur’ ou ’peer to peer’) :

  1. >>> mat_tout_no(5)
  2. array([[0, 1, 1, 1, 1],
  3. [0, 0, 1, 1, 1],
  4. [0, 0, 0, 1, 1],
  5. [0, 0, 0, 0, 1],
  6. [0, 0, 0, 0, 0]])
  7.  
  8. >>> mat_serveur_o(5)
  9. array([[0, 1, 1, 1, 1],
  10. [1, 0, 0, 0, 0],
  11. [1, 0, 0, 0, 0],
  12. [1, 0, 0, 0, 0],
  13. [1, 0, 0, 0, 0]])

Télécharger


L’idée est ensuite de concaténer diverses matrices ; si par exemple on concatène une matrice n.n et une matrice m.m, on va créer une matrice (n+m).(n+m) par blocs reprenant les matrices précédentes et en complétant par des 0.

On modélise ainsi deux réseaux sociaux sans lien.

On peut ensuite positionner quelques 1 au hasard dans les blocs de 0, créant ainsi quelques liens entre ces deux réseaux.

Un exemple

Voici les différentes étapes (avec de petites tailles) que l’on obtient :

  1. >>> M1=mat_connexe_sym(3)
  2. >>> M1
  3. array([[0, 0, 1],
  4. [0, 0, 1],
  5. [1, 1, 0]])
  6. >>> M2=mat_serveur_o(4)
  7. >>> M2
  8. array([[0, 1, 1, 1],
  9. [1, 0, 0, 0],
  10. [1, 0, 0, 0],
  11. [1, 0, 0, 0]])
  12. >>> M=conca(M1,M2)
  13. >>> M
  14. array([[0, 0, 1, 0, 0, 0, 0],
  15. [0, 0, 1, 0, 0, 0, 0],
  16. [1, 1, 0, 0, 0, 0, 0],
  17. [0, 0, 0, 0, 1, 1, 1],
  18. [0, 0, 0, 1, 0, 0, 0],
  19. [0, 0, 0, 1, 0, 0, 0],
  20. [0, 0, 0, 1, 0, 0, 0]])
  21. >>> lien_n(M,3)
  22. array([[0, 0, 1, 0, 0, 0, 0],
  23. [0, 0, 1, 1, 0, 0, 0],
  24. [1, 1, 0, 0, 0, 0, 1],
  25. [0, 0, 0, 0, 1, 1, 1],
  26. [0, 0, 0, 1, 0, 0, 0],
  27. [0, 0, 0, 1, 0, 0, 0],
  28. [0, 0, 0, 1, 0, 0, 0]])

Télécharger


Reste à visualiser ces matrices pour représenter des graphes ; c’est le rôle des dernières fonctions présentes dans le code proposé.

  1. >>> M
  2. array([[0, 0, 0, 1, 0, 1, 0, 0, 0],
  3. [0, 0, 1, 0, 0, 0, 0, 0, 0],
  4. [0, 0, 0, 0, 1, 0, 0, 0, 0],
  5. [0, 0, 1, 0, 0, 0, 0, 0, 0],
  6. [0, 0, 0, 0, 0, 0, 0, 1, 0],
  7. [0, 1, 0, 0, 0, 0, 1, 1, 0],
  8. [0, 0, 0, 0, 0, 1, 0, 0, 0],
  9. [0, 0, 0, 0, 0, 0, 1, 0, 0],
  10. [0, 0, 0, 0, 0, 0, 1, 0, 0]])
  11. >>> graph(M,1)

Télécharger

Cela va donner le graphe orienté suivant :

retour d’expérience

Les activités que nous venons de écrire seront proposées dans les mois à venir aux élèves.

Nous rendrons compte de l’expérimentation à cet endroit de l’article.

Ce retour d’expérience sera annoncé dans une brève de MathémaTICE.

conclusion

Cet article présente une manière de créer des graphes à l’aide de Python pour créer des situations à proposer aux élèves.

Si l’installation a été possible sur les postes de votre lycée, pourquoi ne pas proposer aux élèves de coder des graphes correspondants à diverses situations simples ?

Cette méthode vous permet, à vous enseignants en tout cas, de créer des graphes de taille raisonnable, support d’exercices pour les élèves.

Mais cela permet aussi de générer des matrices et donc des graphes de grande taille susceptibles de modéliser des réseaux sociaux existants.

Citons également d’autres manières de créer des graphes (remarques d’Alain Busser) :

  • les outils de LaTeX issus notamment du package tikz ;
  • Nirina974 qui exporte au format svg ;
  • l’utilisation de CaRMeTal : citons en particulier une activité à destination des élèves de SNT qui permet de créer un graphe de manière collaborative par le biais du réseau informatique du lycée ; à voir ici, sur le site de l’IREM de La Réunion.

notes

[1D. ROCHE précise que ce site est actuellement visité 10 000 fois par semaine ...

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197