Communications dans une grille

Communiquer dans une grille ?

proposé par P. Duchet

Des personnes (ou des relais électroniques, si vous préférez) sont régulièrement disposées dans un plan.

Chaque personne peut envoyer des informations à d'autres personnes, à condition de respecter certaines règles.

Ces règles, bien précises et immuables, sont les mêmes pour toutes les personnes. En fait, à proprement parler, c'est l'ensemble de ces règles qui définit le réseau.

Donnons un exemple de réseau, baptisé "ABC", car il est défini par trois règles A, B et C .

Figure 2. Exemple de réseau

Dans ABC, une personne quelconque du réseau (placée en P sur la figure 2) peut informer

• la personne située 1 pas à l'Est, 2 pas au Sud : c'est la règle "A".

• la personne située 3 pas à l'Est, 2 pas au Nord : c'est la règle "B".

• la personne située 3 pas à l'Ouest, 1 pas au Nord : c'est la règle "C".

Ainsi, P ne peut pas informer directement la personne située en S, bien que celle-ci soit géographiquement très proche : 1 pas vers l’Est, 1 pas vers le Nord.

Par contre, S peut être aisément informé en trois étapes :

- à la première étape, P prévient Q, en utilisant la règle A.

- à la deuxième étape, Q prévient R, en utilisant la règle B.

- à la troisième étape, R prévient S, en utilisant la règle C.

Figure 3. Information de S en 3 étapes

Les règles de transmission d'un réseau étant fixées, le problème est le suivant :

Une nouvelle, connue d'une personne particulière peut-elle être transmise à tout le monde en suivant les règles du réseau ?

Sinon, quelles sont les personnes qui peuvent être informées ?

Le problème général, qui est non résolu à ce jour, peut être abordé sous bien des aspects :

Si chacun diffuse immédiatement ce qu'il sait en utilisant toutes les règles, comment se propagent les nouvelles ? En particulier, on peut se demander combien de personnes seront au courant au bout de 1,2, 3,..., n étapes.
Comment savoir si une personne choisie à l'avance pourra être informée ? En combien d'étapes ? De quelle manière ?
Si on ne trouve aucun moyen de prévenir quelqu'un, comment être vraiment sûr qu'il n'existe aucun moyen ?
Y a-t-il des réseaux plus efficaces que d'autres pour la diffusion ? Pour des dispositions moins régulières des personnes à prévenir, peut-on trouver des méthodes de diffusion rapides générales ?

Motivation — La diffusion rapide d'une information dans une ville, un pays, un réseau téléphonique, peut être organisée de bien des façons : le principe dit "du téléphone arabe" où chacun transmet la nouvelle à ses voisins est bien connu. C'est suivant le même principe que se propage le feu dans une forêt (à la différence essentielle près qu'un arbre brûlé ne transmet plus). La recherche des meilleures organisations possibles des transmissions dans un réseau relève de la théorie des graphes. Le problème particulier où l'on cherche à informer tout le monde en un minimum de temps est connu sous le nom de "problème des ragots".

L'étude systématique des propagations aléatoires, du type feu de forêt, utilise des techniques mathématiques variées : les probabilités, la théorie de la percolation (appelée ainsi à cause de la propagation de la vapeur dans la poudre de café) et la théorie ergodique qui étudie notamment les zones d'un billard atteintes par une boule qui y circule indéfiniment.

retour aux sujets lycée.