article mathematice

lundi 16 septembre 2019
par  Florent Girod

Cet article présente une réflexion autour de l’enseignement de SNT et notamment le thème des graphes.

Préambule

Pourquoi enseigner SNT ?

les bonnes raisons

l’envie d’apprendre de nouvelles choses, de se former, de partager des notions et échanger avec les élèves.

faire des liens avec les mathématiques, notamment par l’aspect programmation.

pourvoir avoir les élèves à la fois en mathématiques et en SNT

par pragmatisme !

On a beau dire ce qu’on veut, suite à la réforme du lycée, il y a souvent des pertes d’heures pour les enseignants de mathématiques.

Par ailleurs, des thèmes sont connexes aux mathématiques.

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

from graphviz import Digraph #pour un graphe orienté
from graphviz import Graph #pour un graphe non orienté


g = Digraph('G', filename='reseau', engine='sfdp')
#g = Graph('G', filename='reseau', engine='sfdp')

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é
g.edge('B' , 'A')
g.edge('B', 'C')
g.edge('C', 'B')
g.edge('C', 'D')
g.edge('C', 'G')
g.edge('D', 'G')
g.edge('E', 'F')
g.edge('E', 'B')
g.edge('F', 'B')
g.edge('G', 'C')
g.edge('G', 'H')
g.edge('H', 'D')


g.render(view=True)#on enregistre le fichier (nom précisé précédemment) et on visualise le document à chaque compilation, en format .pdf

résultat

PNG - 28.8 ko

détails d’installation

Pour la bibliothèque graphviz, on pourra l’installer classiquement par un ’pip install graphviz’

pour ce qui est du module Graphviz, il faut le télécharger ici par exemple et ensuite créer un raccourci en passant par le terminal windows. Ici un tutoriel pour le faire.

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 :

PNG - 24.1 ko

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

code python

from graphviz import Graph, Digraph

g = Graph('G', filename='graphe', engine='sfdp')

g.edge('Alan', 'Eline')
g.edge('Alan', 'Dylan')
g.edge('Bénédicte', 'Chloé')
g.edge('Bénédicte', 'Eline')
g.edge('Bénédicte', 'Dylan')

g.render("mes-amis", view=True)

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 di-é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 contact.

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

Question : En reprenant le graphe précédent, colorez les sommets touchés par une information au fur et à mesure où elles sont transmise. 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.

réponse

PNG - 35.9 ko

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 :

Voici une modélisation de graphe de grande dimension, avec une visualisation de transmission de l’information utilisant le même modèle que celui présenté précédemment :

PNG - 268.9 ko

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éseau dense. 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é :

PNG - 28.2 ko

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.8 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

def mat_connexe(n, p=0.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é p d'avoir 1"""
   m=np.full(shape=(n, n),fill_value=0)#initialise un matrice n*n avec des 0
   for i in range(n):#ligne
       for j in range(n):#colonne
           if i != j:
               m[i][j] = int(random() < p)# 1 en position (i,j) avec un probabilité de p
           else:
               m[i][j] = 0#0 sinon
   for i in range(n-1):
       if sum(m[i]) == 0:#pour ajouter un 1 au cas où la ligne ne comporte pas du tout de 1
           m[i][randint(i+1, n-1)]=1#on place un 1 aléatoirement après la diagonale
   return m

permet d’obtenir par exemple :

>>> mat_connexe(5)
array([[0, 0, 0, 1, 1],
      [0, 0, 0, 0, 1],
      [0, 1, 0, 1, 0],
      [0, 0, 0, 0, 1],
      [0, 0, 0, 0, 0]])

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’ :

>>> mat_tout_no(5)
array([[0, 1, 1, 1, 1],
      [0, 0, 1, 1, 1],
      [0, 0, 0, 1, 1],
      [0, 0, 0, 0, 1],
      [0, 0, 0, 0, 0]])

>>> mat_serveur_o(5)
array([[0, 1, 1, 1, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0]])

L’idée est ensuite de pouvoir 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 :

>>> M1=mat_connexe_sym(3)
>>> M1
array([[0, 0, 1],
      [0, 0, 1],
      [1, 1, 0]])
>>> M2=mat_serveur_o(4)
>>> M2
array([[0, 1, 1, 1],
      [1, 0, 0, 0],
      [1, 0, 0, 0],
      [1, 0, 0, 0]])
>>> M=conca(M1,M2)
>>> M
array([[0, 0, 1, 0, 0, 0, 0],
      [0, 0, 1, 0, 0, 0, 0],
      [1, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 1, 1],
      [0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 0]])
>>> lien_n(M,3)
array([[0, 0, 1, 0, 0, 0, 0],
      [0, 0, 1, 1, 0, 0, 0],
      [1, 1, 0, 0, 0, 0, 1],
      [0, 0, 0, 0, 1, 1, 1],
      [0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 0]])

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

>>> M
array([[0, 0, 0, 1, 0, 1, 0, 0, 0],
      [0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 0, 0, 0, 0],
      [0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 0],
      [0, 1, 0, 0, 0, 0, 1, 1, 0],
      [0, 0, 0, 0, 0, 1, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 0, 0]])
>>> graph(M,1)

Cela va donner le graphe orienté suivant :

PNG - 35.5 ko

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 simple ?

Cette méthode vous permettra à vous enseignant 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.


Navigation

Articles de la rubrique

  • article mathematice