La théorie des graphes ou comment ne pas prendre la grosse tête | Voyages au pays des maths | ARTE

Visite express du pays des mathématiques où existent des graphes hiérarchiques, des pavages semi-périodiques, et des polytopes de dimension 4.

Un graphe est un ensemble de sommets reliés par des arêtes. Certains sommets peuvent ne pas être reliés, certaines paires peuvent être reliées plusieurs fois, et on autorise même les boucles qui relient un sommet à lui-même.

Un graphe est un objet abstrait où seules les connexions comptent, pas la position spatiale des sommets et des arêtes. Des graphes différents graphiquement sont parfaitement identiques s'ils ont la même structure de connexion.

• Plans de métro modélisés comme des graphes avec stations et rails • Graphes reliant chaque être humain aux autres selon les rencontres • Étude des réseaux sociaux, propagation des maladies, réseaux informatiques et séquences d'ADN

Le cerveau peut être simplifié en graphe avec neurones comme sommets et synapses comme arêtes. Le vers C. elegans a un graphe neuronal entièrement connu avec 300 neurones et environ 8000 synapses, tandis qu'un cerveau humain contient près de 100 milliards de neurones et environ 10000 milliards de connexions par centimètre cube.

Le mathématicien russe Andreï Kolmogorov et son collègue Bars Dean ont entrepris d'étudier à la fin des années 60 comment faire entrer un graphe neural avec ses nombreuses connexions dans un espace minimal. La question est : quelle est la taille minimale d'un cube pouvant contenir un graphe à N sommets.

Pour transformer un graphe abstrait en objet concret, on imagine les sommets comme des billes de diamètre 1 et les arêtes comme des tubes extensibles et flexibles de même rayon, similaire à des jeux de construction magnétique.

• Un graphe linéaire avec 64 sommets peut être plié pour rentrer dans une boîte cubique de côté 4 au lieu d'une boîte rectangulaire de longueur 64 • Un graphe linéaire avec N sommets peut être placé dans une boîte de côté racine cubique de N

Le degré d'un graphe en un sommet est le nombre d'arêtes attachées à ce sommet. Un graphe est peu hérissé si le degré en chaque sommet est petit, et hérissé si les sommets ont des connexions nombreuses.

Tout graphe fini avec N sommets et de degré inférieur ou égal à 6 peut grosso modo rentrer dans une boîte de côté racine de N. Cette limite théorique établit la compacité minimale possible pour ranger physiquement le graphe.

Un graphe fini est un bon expenseur quand on sépare ses sommets en deux groupes de taille équivalentes et que le nombre d'arêtes reliant les deux groupes est grand. Plus ce nombre rapporté au nombre de sommets est grand, meilleure est l'expansion.

• Un graphe constitué de deux morceaux disjoints n'est pas du tout expenseur • Un graphe rectiligne est un très mauvais expenseur car couper une seule arête le sépare en deux groupes • Un bon expenseur représente un réseau robuste qu'un accident ne peut pas couper en deux • Les graphes complets sont les meilleurs expenseurs puisque chaque sommet est relié à tous les autres

• Un graphe complet n'est pas pratique : chaque sommet ajouté augmente de 1 le degré du graphe qui devient énorme • Un réseau téléphonique où chaque foyer serait relié à tous les autres par des câbles individuels est impossible à construire physiquement

Peut-on construire un graphe expenseur sans que son degré devienne trop grand et dans un volume raisonnable ? La réponse est oui, mais les graphes expenseurs ne sont pas faciles à construire.

Les graphes expenseurs sont précisément ceux qui occupent le plus grand volume. Quand on divise un graphe expenseur contenu dans une sphère avec un plan en deux parties égales, le plan doit rencontrer beaucoup d'arêtes, ce qui limite le diamètre minimal de la sphère.

• Les premières solutions constructives sont venues de la théorie des nombres dans les années 2000 avec Winnie Lee, Alex le bodski, Bad Samuels et Osé Vishnu • Ces mathématiciens ont imaginé des expenseurs multidimensionnels avec des applications pour les codes correcteurs d'erreur et l'informatique quantique

Pour un graphe expenseur avec N neurones et synapses d'épaisseur 1, il est impossible de faire rentrer tous les neurones et synapses dans un volume inférieur à la racine cubique de N.

Pour optimiser l'espace occupé par le graphe, il faut placer les sommets à proximité de la paroi extérieure de la boîte. La plus grande partie du cerveau est occupée par des fibres nerveuses tandis que les neurones sont placés à la surface.

Ce que la nature accomplit sans effort à l'intérieur de nos crânes s'avère formidablement difficile à réaliser pour un ingénieur qui voudrait tracer explicitement les plans d'un réseau. La biologie a résolu ce problème que les mathématiciens modélisent.

L'évolution qui a créé nos cerveaux est étonnamment douée en maths, ou les mathématiques et les graphes en particulier sont étonnamment efficaces pour modéliser les produits mous de l'évolution que sont les cerveaux.