Modélisation de différentes relations à l’aide de graphes.
par bernard.vuilleumier
Le courrier électronique est aujourd’hui la plus importante des applications de l’Internet en termes de quantité de données transportées. Pour éviter une saturation du réseau, il serait souhaitable que chaque usager respecte certaines règles.
Tableau des notions et des activités
Objectifs de l’activité
– Représenter différents types de relations entre n éléments.
– Donner une description concise des relations envisagées.
– Comparer une relation n à n à une relation n à 1.
– Dégager des règles de conduite à l’attention des usagers d’une messagerie.
Notions
– schéma
– graphe
– du bon usage d’une messagerie
Durée
– 2 fois 45 minutes
Description
Les n membres d’un groupe de travail souhaitent échanger des informations. Chaque personne dispose des adresses électroniques des autres membres du groupe ainsi que de l’adresse d’un espace commun accessible à tous.
Questions
- Combien d’envois faut-il effectuer pour informer tout le groupe ?
- Comment faut-il procéder pour apporter une correction à un document qui a déjà été envoyé ?
- Quels sont les avantages et inconvénients d’une diffusion :
- par liste de distribution ?
- par envoi sur un espace de travail commun ?
Activités
– Construisez une représentation schématique des échanges à l’aide de points et de lignes lorsque :
- chaque personne envoie des informations à tous les membres du groupe ;
- chaque personne envoie des informations sur un espace de travail commun.
– Donnez une description concise caractérisant les échanges entre les n membres dans chaque cas.
– Décrivez, de manière non ambiguë, les deux types d’échanges, pour différentes valeur de n.
À l’attention du maître
Réponses aux questions
- Pour informer un groupe de n personnes, il faut procéder à n - 1 envois si on ne s’envoie pas l’information à soi-même.
- Pour apporter une correction à un document envoyé, il faut l’expédier à nouveau à chacun.
- Les avantages et inconvénients respectifs sont les suivants :
- liste de diffusion : l’information est adressée personnellement à chaque membre. Le trafic réseau est plus « concentré » dans le temps.
- espace de travail commun : le trafic réseau est « dilué » dans le temps. Les membres doivent prendre l’initiative de consulter la zone de travail.
– Questions et réponses sur le courrier électronique.
– Représentation schématique de différents types d’échanges :
Échanges entre les acteurs à l’aide d’une liste de distribution :
Échanges par liste de distribution représentés d’une autre manière :
Mise en évidence du sens des échanges :
Échanges utilisant une zone de travail commune :
Autre représentation des échanges avec espace de travail commun :
– Description non ambiguë des deux types d’échanges
On peut numéroter les nœuds et donner explicitement les connexions entre eux. Dans Mathematica par exemple, cela se noterait ainsi :
GraphPlot[{1 -> 2, 2 -> 1, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2, 4 -> 4}, VertexLabeling -> True]et fournirait la représentation suivante :
On peut aussi donner les relations à l’aide d’un tableau de nombres (matrice adjacente) : chaque ligne comporte autant d’éléments qu’il y a de nœuds dans le graphe. La présence d’un 1 dans la première ligne signale que l’élément dont le numéro correspond à la position de ce 1 dans cette ligne est lié au premier élément. Pour le graphe ci-dessus, le tableau aurait l’allure suivante :
N. B. Les différentes représentations - circulaire ou linéaire - d’un type d’échange doivent donner lieu à la même description ! Un graphe est défini comme un ensemble de sommets ou noeuds et de côtés, un côté étant défini par une paire de sommets. La représentation des graphes revêt diverses formes selon qu’ils sont destinés à des humains ou à des machines. Les ordinateurs « digèrent » mieux les graphes lorsqu’ils sont représentés par des données structurées - listes ou tableaux de nombres, alors que les humains préfèrent représenter ces structures comme une collection de points liés par des lignes, ce qui implique l’ajout d’une information géométrique au graphe.
Remarque
Si vous disposez d’ordinateurs, utilisez le fichier joint « Graphes » [1] avec les élèves pour générer des figures comportant un nombre d’acteurs n différent (2 ≤ n ≤ 20). Si ce n’est pas le cas ou si vous préférez mettre les élèves en contact avec la matière, prévoyez des plaques de sagex, des épingles et du fil… et un peu plus de temps. Et limitez-vous à la représentation circulaire !
