La chasse aux graphes

118 13 19
                                    

CN : Je crois qu'on a déjà parlé de graphes, Gudule, non ?

Gudule : gné.

CN : En revanche je n'ai jamais raconté (et personne ne m'a jamais demandé) d'où tu viens.

Gudule : euh...

Zorlax tambourine contre les portes du placard dans lequel il est enfermé.

Zorlax (voix étouffée) : moi non plus ! Moi non plus ! Mais pourquoi personne ne s'intéresse à moi ?

Un silence s'écoule.

Zorlax : au secours ! Il y a une betterave qui parle dans ce placard ! Sauvez-moi !

On n'entend plus crier Zorlax.

(Une autre voix étouffée dans le placard, légèrement grinçante, presque lugubre) : je suis le maîiiiitre du moooooonde...


Un jour, je me promenais sur les bords de l'Elbe lorsque je vis un berceau dériver au fil de l'eau (il était équipé d'un moteur à diesel Wolkswagen, et celui-ci était apparemment en panne).

Je regardai le berceau (enfin, ça ressemblait à un berceau) se crasher contre le rivage lorsque l'idée me vint d'aller y jeter un coup d'œil. On ne sait jamais, peut-être qu'il y avait quelque chose à gagner dans cette histoire. Peut-être que le FTM, qui préside à tout (sauf pour les arcs narratifs où je me fais capturer par Zorlax) m'observait de très loin.

FTM (perché, ou plutôt emmêlé, dans un arbre) : avance, abruti !

Je m'avançai donc, regardai dans le berceau...

... et y vis juste un poisson qui me regardait avec des yeux de poisson (le fond du paquet prenait l'eau).

Le moteur Wolkswagen se mit ensuite à relâcher des émanations toxiques que les tests techniques n'avaient jamais pu mettre en évidence, et je décidai de prendre la fuite.

FTM : où est-il, nom d'un spaghetti ?

(NdA : je laisse aux commentateurs le soin de se battre entre eux quant à savoir si on dit un spaghetto ou un spaghetti. LibreOffice ne reconnaît pas spaghetto. Râmen.)

Je rentrai donc chez moi, mais un étrange pressentiment me fit m'arrêter sur le pont qui enjambait le fleuve. J'assistais alors à une scène des plus incongrues.

Le FTM volait derrière Gudule, qui courait après un Snark.

Je sus immédiatement que l'individu se nommait Gudule (il me le confirmerait plus tard de vive voix en me préparant un café, tout en se demandant comment et pourquoi, dès notre première rencontre, il était entré à mon service – à moins que ce soit cette histoire de pari sur le nombre de fois qu'un crapaud peut croasser d'affilée sans avoir la gorge enrouée, mais je m'égare).

CN (du passé) : voici une scène sans doute tout à fait normale en Allemagne.

Gudule (du passé) : attrapez ce Snark !

Je ne sais pas si vous avez déjà vu un Snark. Il faut savoir que certains d'entre eux sont des Boojums, et donc y faire attention, et... bon, c'est un poème de Carroll.

Gudule (du présent) : maître, vous n'allez quand même pas en profiter pour vous faire encore de la pub ?

Bref, un Snark, c'est ça (par Koko90 sur Wiki Commons).

Bref, un Snark, c'est ça (par Koko90 sur Wiki Commons)

Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.

Gudule : les lecteurs vont être déçus.

Les Snarks (en maths, donc) sont une famille de graphes spéciaux. Plus exactement, chaque sommet a trois voisins et vous ne pouvez pas colorer les arêtes avec 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet.

Je ne vais pas recopier ici toutes les belles images de Wikipédia.

Gudule : parce que ce serait honteux.

Le plus petit Snark (intéressant, en tout cas) est le graphe de Petersen, que voici (par Leshabirukov sur Wikimédia Commons). Il sert de contre-exemple fameux à plein de propriétés (qui ne sont donc pas vraies à cause de lui).

Comment ? Tout ceci ne sert à rien ? Attendez un peu, drogués que vous êtes aux résultats clinquants et aux annonces faramineuses

Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.

Comment ? Tout ceci ne sert à rien ? Attendez un peu, drogués que vous êtes aux résultats clinquants et aux annonces faramineuses. Parfois on peut aussi s'arrêter en chemin juste pour cueillir un « Snark fleur ».

Ah, Gudule me fait signe qu'on a quand même une annonce clinquante. Bon, oubliez ce que j'ai dit.

On a parlé du théorème des 4 couleurs, celui qui dit qu'on peut colorier toute carte avec seulement 4 couleurs ; autrement dit, tout graphe « planaire » (qui peut se dessiner sans que les arêtes se croisent) avec 4 couleurs aussi.

Eh bien, les matheux ont souffert avec ce théorème, mais ils savaient depuis 1880 (et un certain Peter Guthrie Tait) que démontrer ce théorème était équivalent à démontrer que tous les Snarks étaient planaires. Joli, n'est-ce pas ? D'où la course aux Snarks.

Gudule : placement de produit.

Hem. La chasse aux Snarks.

Il y a un certain (et sans doute grand) nombre d'exemples comme ça : de petites familles de graphes ou des graphes « spéciaux » qui sont sous les projecteurs pour une raison ou une autre. Ça permet de se souvenir que malgré leur apparente simplicité, les graphes offrent une grande variété d'explorations mathématiques...

Et voilà pourquoi un jour, j'attrapai Gudule qui attrapait un Snark.

Pour finir, le singleton de Hoffman, par Uzyel sur Wikimédia. Je ne sais pas à quoi sert ce graphe. Si quelqu'un sait, qu'il me le dise. Mais il est beau quand même.

Voilà (aussi) pourquoi j'aime les graphes

Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.

Voilà (aussi) pourquoi j'aime les graphes.

Pourquoi j'adore les mathsOù les histoires vivent. Découvrez maintenant