Mis à jour le 20/11/2013
  • 2 heures
  • Facile
Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Introduction du cours

Image utilisateur

Si la plupart des gens connaissent le mot percolation, c'est sans aucun doute grâce au procédé du même nom de préparation du café. Le verbe percoler signifie « passer à travers des matériaux poreux » et c'est bien là le fonctionnement du percolateur, machine à café qui produit son breuvage en faisant s'écouler de l'eau chaude à travers la poudre de café.

Mais savez-vous que derrière ce terme se cache un principe scientifique présent dans de nombreuses théories allant de la fonte des glaces à la porosité des roches en passant par les tortues de Darwin ou la migration des hérissons ?

Non ? Alors ce mini-cours est fait pour vous ! Après avoir expliqué le principe général de la percolation, nous ferrons un panorama des différents domaines dans lesquels on la retrouve et des multiples phénomènes qu'elle permet de modéliser. Nous finirons par un peu de théorie en montrant un joli résultat mathématique de cette théorie.

Des p'tits trous, des p'tits trous, encore des p'tits trous...

Pour voir apparaître un phénomène de percolation, deux ingrédients sont nécessaires : premièrement une structure présentant des pleins et des creux et deuxièmement un agent capable d'évoluer dans cette structure.

Image utilisateurImage utilisateur

En quelque sorte nous avons affaire à un labyrinthe. Comme nous allons le découvrir dans les exemples qui vont suivre, ces deux éléments peuvent prendre des formes très différentes selon les domaines auxquels on s'intéresse.

On dit alors qu'il y a percolation quand l'agent qui se déplace dans les creux de la structure est capable de traverser cette dernière de part en part. Dans le cas de la machine à café, il y a effectivement percolation puisque l'eau chaude traverse la poudre de café. Si cette poudre était trop dense pour que l'eau puisse s'y frayer un chemin il n'y aurait pas percolation et par conséquent pas de café. ^^

En géologie

En géologie, et plus précisément en pédologie, qui est l'étude du sol, on s'intéresse aux différentes matières qui composent la couche supérieure de la croûte terrestre (roches, argiles, sable,...). Une de leurs caractéristiques considérées est la porosité, c'est-à-dire la proportion de vide qu'elles contiennent.

Cette porosité est essentielle à l’absorption des pluies par le sol. Mais attention, ce n'est pas parce qu'une roche possède une certaine porosité qu'elle laisse forcément l'eau s'écouler. Il faut que cette porosité soit suffisamment forte pour que les trous connectent le haut de la roche au bas de la roche. Autrement dit, il faut qu'il y ait percolation.

Voici un tableau indiquant la porosité moyenne de certaines matières.

Matière

Porosité

Gravier

30%

Sable fin

45%

Calcaire

20%

Grès

35%

Basalte

15%

Question piège. Selon vous, à partir de quel niveau de porosité y a-t-il percolation ? Autrement dit à partir de quelle proportion de trous l'eau s'écoule-t-elle à travers le sol ?

La réponse est « ça dépend ! » En effet, le seuil de porosité à partir duquel il y a percolation dépend du type de la roche et de la façon dont sont disposés les trous. Voici quatre exemples qui montrent qu'il peut ou non y avoir percolation que la porosité soit forte ou faible.

Image utilisateur

Nous verrons dans la seconde partie que dans les modélisations théoriques on voit également apparaître des seuils différents selon la structure de base que l'on choisit.

En écologie

L'écologie du paysage étudie la structure des paysages et notamment leur faculté à permettre les mouvements de populations animales.

Certaines espèces se déplacent de façon privilégiée dans certains milieux. On trouve par exemple des animaux des bois et forêts qui n'osent que très rarement s'aventurer dans les plaines. Sur un territoire où les forêts sont nombreuses et interconnectées, il y a percolation et ces animaux vont pouvoir faire de longues migrations. Si au contraire la région présente de grandes prairies parsemées de bois isolés, les déplacements ne pourront pas se faire ou seront très ralentis.

Le hérissons par exemple aiment loger dans les haies. Avec le développement de l'agriculture humaine, certaines régions bocagères, formées de nombreux petits champs bordés de haies ont disparu. Le travail que nécessitait l'entretien de ces haies ainsi que l'évolution des techniques qui rend plus efficace le travail de vastes champs ont entraîné la destruction d'un grand nombre de haies ainsi que parfois le comblement de points d'eau. En d'autres termes, l'évolution de ces paysages à bloqué la percolation des hérissons entraînant une modification de leur mode de vie.

Image utilisateur

Les Tortues géantes des Galápagos forment un ensemble de dix espèces qui habitent, comme leur nom l'indique, les îles Galápagos. Ces tortues sont si proches les unes des autres qu'elles sont parfois considérées comme des sous-espèces d'une même espèce. Elles sont célèbres pour avoir été observées par Charles Darwin au XIXe siècle et lui avoir inspiré la théorie de l'évolution (ci-contre un timbre anglais célébrant Darwin et ses tortues).

Les îles Galápagos sont à la fois suffisamment proches les unes des autres pour avoir été toutes colonisées par ces tortues et suffisamment éloignées pour qu'elles aient pu évoluer et prendre des aspects sensiblement différents sur chacune d'entre elles. Nous sommes donc proche d'un seuil critique de percolation. Si les îles avaient été plus proches les unes des autres, les tortues auraient pu aller et venir facilement et nous n'aurions clairement qu'une seule espèce. Si au contraire elles avaient été plus éloignées, nous aurions des espèces totalement différentes, voire certaines îles qui n'auraient jamais été colonisées.

Dans les réseaux d'énergie et communication

La mise en place d'un réseau, par exemple d'électricité, nécessite l'étude de ses propriétés de connexité. En effet, dans la mesure où des pannes ponctuelles peuvent se produire sur un réseau, il est préférable que la structure de celui-ci soit étudiée de façon à ce que ces dysfonctionnement entraînent le moins de désagréments possible.

Image utilisateur

Dans le réseau ci-dessus, la coupure d'un seul des liens entraîne la déconnexion de quatre maisons.

Alors bien sûr, dans la théorie, la solution la plus efficace serait de relier chaque maison à la centrale avec un câble qui lui est propre. De cette façon, tout dysfonctionnement n'isole qu'une maison. Mais bien sûr dans la pratique ce schéma n'est pas possible. :-° Le but est donc, étant donné les moyens limités qui sont disponibles (notamment en fonction des coûts) de trouver la meilleure disposition du réseau pour minimiser les risques.

En sciences physiques

En sciences physiques, la percolation permet d'expliquer certains phénomènes de changement de phase. La matière possède principalement trois états : solide, liquide et gazeux. Le passage d'un état à un autre se fait, selon les matériaux et les conditions extérieures à une température donnée. Par exemple, la glace (eau solide) devient liquide à 0°C.

Vous vous êtes peut-être déjà demandé pourquoi ces transitions de phase se font brutalement à une température donnée et non progressivement. On aurait pu s'attendre à ce que la glace, en augmentant la température, devienne peu à peu de plus en plus molle, puis passe par un état de pâte visqueuse jusqu'à se fluidifier de plus en plus pour arriver à l'état d'eau liquide. Pourtant, la plupart du temps ce n'est pas le cas, il existe une température critique à laquelle la matière change d'un coup d'un état à un autre.

Un solide est composé d'atomes ou de molécules qui sont figés les uns par rapport aux autres. À l'échelle microscopique, la température correspond au niveau d'agitation de ces particules qui composent la matière. Ainsi, si on augmente la température d'un solide, les atomes vont commencer à s'agiter un peu et à vibrer. Tant que la température reste assez basse, les vibrations sont faibles et les atomes restent à leur emplacement.

Il faut cependant bien réaliser que les atomes ne vibrent pas tous bien en rythme et à la même intensité. L'agitation est désordonnée. Ainsi, si la température est faible alors en moyenne l'agitation est faible, mais cela n'empêche pas quelques rares atomes d'être beaucoup plus excités que la moyenne et se soustraire à la structure en quittant leur emplacement. Bien entendu, plus la température est forte, plus le nombre des molécules qui quittent la structure est grand.

Image utilisateurImage utilisateurImage utilisateurImage utilisateurImage utilisateurImage utilisateur

Solide froid.
Toutes les molécules sont bien rangées.

Solide prêt à fondre.
La structure ne tient plus que de justesse.

Liquide.
Tout a fondu !

Et quand la proportion de trous dans la structure devient trop grande, badaboum ! Tout s'écroule et la matière fond.

Nous avons donc bien une situation de percolation avec certaines molécules bien en place dans la structure et d'autres qui ont quitté leur emplacement et laissent des trous. Comme pour la porosité des roches qui ne laissent passer l'eau qu'à partir d'une certaine proportion de trous, la structure solide va tenir jusqu'à un seuil précis de trous. Quand la proportion de trous devient trop grande pour tenir la structure, l'ensemble s'effondre et le solide fond, c'est-à-dire qu'il passe à l'état liquide.

Modélisation mathématique

Dans cette seconde partie, nous allons aborder la modélisation mathématique des phénomènes de percolation.

Il existe une multitude de modèles plus ou moins sophistiqués de percolation. Celui que nous allons voir est l'un des plus simple qui existe. Le bon côté, c'est qu'il est plus facile à étudier, le mauvais, c'est qu'il est tellement simplifié qu'il n'est pas vraiment adapté pour modéliser de façon réaliste des phénomènes réels.

Vous allez voir que notre modèle jouet possède malgré tout de très jolies propriétés ! :)

La traversée du hérisson

La situation que nous allons étudier est la suivante : un hérisson qui cherche à traverser une région quadrillée de haies formant un réseau à mailles carrées.

Image utilisateur

Au départ, le hérisson se trouve à gauche et il veut traverser pour se rendre à droite. Rappelez-vous qu'il se déplace à l'intérieur des haies. Donc tant qu'aucune haie n'est supprimée, la situation est idéale puisqu'il peut se déplacer à son gré.

Image utilisateur

Il s'agit toujours d'un carré 6×6, mais un peu décalé. Chaque ligne contient 5 carrés entiers et deux demis carrés aux extrémités. Les colonnes quant à elles gardent bien 6 cases entières. Cela peut vous sembler un peu étrange mais vous allez comprendre par la suite que cette disposition particulière possède une jolie propriété qui permet de simplifier la solution. ^^

Bien. Pour l'instant notre hérisson peut traverser la région comme il veut, mais bien entendu, il reste à ajouter des trous dans la structure. Pour cela, nous allons supprimer chaque haie indépendamment avec une probabilité de 50%. En d'autre termes, pour chaque haie, on jette une pièce de monnaie :

  • si elle tombe sur pile alors la haie est sauvée et reste en place ;

  • si elle tombe sur face, la haie est supprimée.

Voici un exemple de ce que l'on peut obtenir :

Image utilisateur

Dans cet exemple, notre hérisson peut toujours traverser. Mais bien sûr, c'est un fait du hasard il aurait tout aussi bien été possible que tous les chemins soient coupés et qu'il ne puisse plus se rendre à droite.

La question que nous allons maintenant nous poser est la suivante.

Combien vaut exactement la probabilité pour que le hérisson puisse encore traverser après que les haies ont été supprimées ?

À première vue, la question n'est pas simple du tout. Essayez d'y réfléchir par vous même si vous voulez. Vous verrez qu'il semble difficile de trouver une façon d'amorcer notre calcul. Pourtant nous allons voir que ce modèle bien précis possède une propriété tout à fait particulière qui permet de répondre de façon très astucieuse à la question.

Nous allons procéder de la façon suivante : à chaque fois qu'une haie est supprimée, nous allons imaginer qu'elle est remplacée par une haie fantôme, située au même endroit mais pivotée de 90°.

Voici à quoi ressemble ces haies fantômes quand quatre haies ont été supprimées :

Image utilisateur

Regardez maintenant à quoi ressemble l'ensemble des haies fantômes si toutes les haies réelles sont supprimées :

Image utilisateur

Vous remarquez que le paysage fantôme de droite est identique au paysage de départ à gauche, pivoté de 90°. Étonnant, n'est-ce pas ? C'est cette jolie propriété qui va nous permettre de conclure.

Imaginez maintenant que nous avons un hérisson fantôme qui cherche à traverser le paysage en se déplaçant dans les haies fantômes de haut en bas.

Image utilisateur

Dans l'exemple ci-dessus, vous voyez que le hérisson fantôme peut traverser de haut en bas alors que le vrai hérisson ne peut pas traverser de gauche à droite.

Nous avons presque fini, il suffit maintenant de remarquer deux choses.

  • Premièrement, si le hérisson fantôme peut passer alors le vrai hérisson ne peut pas passer car les haies fantômes qui relient le haut au bas forment une barrière pour lui. Réciproquement si le vrai hérisson passe, le hérisson fantôme ne passe pas. D'autre part il y a forcément un des deux hérissons qui passe puisque si l'un ne passe pas cela signifie qu'un chemin de haies de l'autre lui barre la route. Autrement dit, quelque soient les haies qui ont été supprimées, il y a un et un seul des deux hérissons qui peut passer.

  • Deuxièmement, la probabilité de pouvoir traverser est la même pour les deux hérissons. En effet, le problème est exactement le même pour les deux hérissons : le paysage fantôme est identique au paysage réel et comme pour les haies réelle chaque haie fantôme existe ou n'existe pas avec une probabilité de 50%.

En conclusion, chacun des deux hérissons a une probabilité de 50% de pouvoir traverser.

Ce résultat est absolument remarquable pour deux raisons. Premièrement ce résultat est exact, il ne s'agit pas d'une approximation. En dépit de l'apparente complexité du problème de départ, la probabilité pour que le hérisson puisse traverser est précisément égale à 1/2. Deuxièmement il est vrai quelque soit la taille du carré de base. Les figures ci-dessus montrent un carré de haies formé de 6×6 cases, mais le même raisonnement s'applique pour un paysage de 1000×1000 cases ou de n'importe quelle autre taille. En d'autre terme, la probabilité pour que le hérisson traverse ne dépend pas de la dimension du paysage ! Épatant n'est-ce pas ?

La probabilité critique

En mathématiques on étudie souvent les phénomènes de percolation sur des réseaux infinis. Ainsi, il faut imaginer une grille du même type que le quadrillage précédent, mais qui s'étend infiniment sur l'ensemble du plan.

Image utilisateur

La deuxième chose que nous allons faire c'est généraliser le processus de destruction des arêtes. Au lieu de les supprimer avec une probabilité égale à 1/2, nous allons considérer un paramètre de percolation $p$ qui est la probabilité pour que chacune d'entre elle soit supprimée. Par exemple, si $p=2/5$ (c'est-à-dire $p=40\%$), cela signifie que chaque arête a 40% de chances de sauter et 60% de chances d'être conservée.

Voici des exemples de ce que l'on obtient pour trois valeurs de $p$.

p=1/5=20%

p=1/2=50%

p=4/5=80%

Image utilisateurImage utilisateurImage utilisateurImage utilisateurImage utilisateurImage utilisateur

La question que l'on se pose sur ce genre de modèle est la suivante : « y a-t-il percolation ? » Autrement dit existe-t-il ce que l'on appelle une composante connexe infinie. Une composante connexe, c'est un ensemble de sommets qui restent connectés entre eux après la suppression des arêtes.

S'il n'existe pas de CCI (j'abrège ;) ), cela signifie qu'il n'y a que des petits îlots déconnectés les uns des autres. Dans ce cas, le hérisson se retrouve coincé dans une petite portion du territoire sans pouvoir en sortir. Si au contraire il y a une CCI, le hérisson peut voyager à son aise aussi loin qu'il le souhaite.

Un résultat important de la théorie de la percolation dit alors qu'il existe une probabilité critique $p_c$ en dessous de laquelle il existe toujours une CCI et au dessus de laquelle il ne peut pas y en avoir.

En résumé,

  • si $p<p_c$, la probabilité d'avoir une CCI est égale à 1 (100%) ;

  • si $p>p_c$, la probabilité d'avoir une CCI est égale à 0.

Dans le cas du réseau à mailles carrées que nous avons étudié, la probabilité critique est égale à 50%, soit $p_c=1/2$. Cela vient du fait que le réseau à maille carré est auto-dual. Le graphe dual, c'est ce que l'on a appelé le paysage fantôme précédemment : c'est le graphe que l'on obtient en faisant pivoter toutes les arêtes de 90°. Le dual d'un réseau carré est encore un réseau carré.

C'est la raison pour laquelle le hérisson réel et le hérisson fantôme jouent à jeu égal et que la probabilité critique se retrouve à la valeur moyenne de 50%.

Mais imaginons à la place un paysage de haies formant des champs triangulaires. Alors le paysage fantôme, ou graphe dual, ressemble à ceci :

Image utilisateur

Le graphe triangulaire n'est pas auto-dual : le paysage fantôme est formé de champs hexagonaux. Ainsi, dans ce paysage, le vrai hérisson et le hérisson fantôme ne jouent pas à jeu égal. Ils n'évoluent pas dans la même structure.

La probabilité critique est dans ce ce cas égale à $1-2\sin(\pi/18)\approx 65\%$. Ce qui signifie que ce n'est qu'environ à partir du moment ou les deux tiers des haies sont supprimées que le hérisson se retrouve bloqué.

Ce cours sur la percolation s'arrête ici. Vous avez maintenant de quoi briller lors de votre prochaine pause café entre collègues ou entre amis.

N'hésitez pas à me laisser vos commentaires si vous avez la moindre remarque, incompréhension ou suggestion. :)

Exemple de certificat de réussite
Exemple de certificat de réussite