Le graphe le plus célèbre de Bruxelles
(ou pas)

 
Ou pas. Car il existe un autre graphe très connu à Bruxelles: l’Atomium ! Le point commun avec la carte d’un métro ? Un ensemble d’objets (appelés des sommets ou nœuds) et des liaisons (appelées arrêtes). L’Atomium est composée de 9 nœuds (8 boules définissant les coins d’un cube + 1 boule au centre) et de 20 liens au total (1). Dans le cas du métro, si on prend le nœud «Gare du Midi» (entouré en rouge), on constate qu’il y a 8 liens avec ce nœud, dont 4 avec la Porte de Hal (un autre nœud du graphe). 

Le cerveau humain est aussi un exemple de graphe: un réseau de neurones reliés par des synapses. C’est un très gros graphe: on estime de 86 à 100 milliards le nombre de neurones dans le cerveau humain (en réalité ce nombre varie d’une personne à l’autre mais aussi avec l’âge, rendant difficile de donner un unique chiffre). Quant au nombre de synapses, il a été estimé dans une étude récente à 150 millions dans à peine 1 mm³ de cerveau (Alexander Shapson-Coe, 2024).

Dans un graphe, seuls les nœuds et les liens comptent: la position physique des nœuds n’a en fait aucune importance (voir Fig. 1a). On peut représenter un graphe sous forme d’un tableau bien rangé dans lequel on va croiser tous les nœuds avec eux-mêmes; pareil tableau est appelé dans le jargon une matrice d’adjacence (voir Fig. 1b). Petite particularité du graphe à 4 nœuds illustré: il possède un cycle, une boucle formée des nœuds 1 à 3. Il y a aussi des cycles dans le graphe du métro bruxellois ci-dessus, par exemple le cycle surligné en vert et composé des stations Rogier, Botanique, Madou, Arts-Loi, Park, Gare Centrale et De Brouckère. Vous devrez changer de ligne à 2 reprises pour parcourir cette boucle, mais il est bien possible de tourner en rond indéfiniment !

Certains graphes sont très particuliers. Leurs liens sont dirigés, ils présentent un nœud appelé racine de laquelle on ne peut que s’éloigner si on se promène dans le graphe et enfin ils ne présentent aucun cycle. Pareil graphe est appelé un arbre en raison de leur ressemblance avec la végétation dans le monde réel (voir Fig. 2a et b ci-dessous).

Savez-vous ce que je trouve magique avec un arbre ? S’il est livré en kit de sous-arbres sur 3 feuilles, il est possible de reconstituer le «grand» arbre original sur base du kit. Comme un exemple vaut mieux qu’un long discours, voici pareil kit:

Félicitations si vous avez compris l’idée: c’est ni plus ni moins que l’un des sujets travaillés dans le cadre de ma propre thèse de doctorat (Nathan Uyttendaele, 2016).

Vous allez me dire, mais à quoi ce résultat peut-il servir ? Plutôt que de vous lister les usages concrets (j’en propose plusieurs dans ma thèse), j’aimerais vous inviter à considérer ceci: pourquoi le moindre sujet mathématique devrait systématiquement avoir une utilité ? Comme en musique ou en peinture, on peut juste aimer la beauté de l’œuvre sans réclamer une utilité autre que le plaisir qu’elle procure à certains et certaines ! Oui, il m’arrive de fantasmer d’un monde où les gens se rendraient les week-ends à l’université comme on se rend au théâtre pour écouter pendant une heure un professeur de maths présenter, en des termes clairs et accessibles de tous et toutes… un joli théorème.