L' Isomorphisme des graphes, moins complexe qu'on ne pensait / Sean Bailly

Article

Bailly, Sean

Comment s'assurer que deux graphes d'aspect différent sont en fait les mêmes ? Ce problème était réputé très difficile sur le plan informatique, mais un algorithme a démenti cette idée.

Voir le numéro de la revue «Pour la science, 473, Mars 2017»

Autres articles du numéro «Pour la science»

Suggestions

Du même auteur

Les Lacs cachés d'Europe / Sean Bailly | Bailly, Sean

Les Lacs cachés d'Europe / Sean Bailly

Article | SYRACUSE | Bailly, Sean | 2012

Le satellite de Jupiter recèlerait de grands lacs d'eau liquide au sein de sa croûte de glace. Leur présence expliquerait les chaos observés en surface.

La Lune soufflée par des bourrasques solaires / Sean Bailly | Bailly, Sean

La Lune soufflée par des bourrasques solaires...

Article | SYRACUSE | Bailly, Sean | 2012

Chaque nuage de particules énergétiques éjectées par le Soleil arracherait plusieurs centaines de tonnes de matière à la surface de la Lune.

Ondes de surface en forme d'étoile (Des) / Sean Bailly | Bailly, Sean

Ondes de surface en forme d'étoile (Des) / Se...

Article | SYRACUSE | Bailly, Sean | 2013

Des interactions non linéaires de plusieurs ondes se propageant à la surface d'un liquide peuvent créer des formes spectaculaires.

Le Fond diffus cosmologique révèle ses modes B / Sean Bailly | Bailly, Sean

Le Fond diffus cosmologique révèle ses modes ...

Article | SYRACUSE | Bailly, Sean | 2013

Une composante de la polarisation du rayonnement fossile de l'Univers a été mise en évidence grâce au radiotélescope SPT. C'est un pas de plus pour comprendre l'Univers primordial.

Pulsar pour sonder le trou noir galactique (Un) / Sean Bailly | Bailly, Sean

Pulsar pour sonder le trou noir galactique (U...

Article | SYRACUSE | Bailly, Sean | 2013

Grâce à la découverte récente d'un pulsar situé à proximité du trou noir central de la Voie lactée, les astrophysiciens ont pu caractériser le champ magnétique régnant dans cette région.

Jumelle brûlante de la Terre (Une) / Sean Bailly | Bailly, Sean

Jumelle brûlante de la Terre (Une) / Sean Bai...

Article | SYRACUSE | Bailly, Sean | 2013

L'exoplanète Kepler 78b est semblable à la Terre par sa taille, sa densité et sa composition. Mais, étant très proche de son étoile, elle est beaucoup plus chaude.

Du même sujet

Les Graphes-allumettes / Jean-Paul Delahaye | Delahaye, Jean-Paul

Les Graphes-allumettes / Jean-Paul Delahaye

Article | SYRACUSE | Delahaye, Jean-Paul | 2014

Les graphes d'un seul tenant et dont toutes les arêtes sont de même longueur peuvent être dessinés en disposant des allumettes sur une table. Ils sont loin d'avoir livré tous leurs secrets.

Les Arbres des mathématiciens sont-ils tous gracieux ? / JeanoePaul Delahaye | Delahaye, Jean-Paul

Les Arbres des mathématiciens sont-ils tous g...

Article | SYRACUSE | Delahaye, Jean-Paul | 2016

Au détour de questions sur les graphes et leur décomposition surgit un problème qui se formule simplement et qui, cinquante ans plus tard, résiste toujours.

Ces grilles de tiges articulées sont-elles rigides ? / Jean-Paul Delahaye | Delahaye, Jean-Paul

Ces grilles de tiges articulées sont-elles ri...

Article | SYRACUSE | Delahaye, Jean-Paul | 2018

Comment savoir si un assemblage plan de tiges articulées est déformable ou rigide ? En appelant à la rescousse la théorie des graphes, qui fournit des algorithmes efficaces.

Graphe universel et singulier (Un) / Jean-Paul Delahaye | Delahaye, Jean-Paul

Graphe universel et singulier (Un) / Jean-Pau...

Article | SYRACUSE | Delahaye, Jean-Paul | 2018

Qu'un seul nombre puisse contenir, dans ses décimales, tous les autres est déjà un fait étrange et troublant. Mais le monde des graphes présente une situation analogue encore plus surprenante, qui frôle le paradoxe.

Graphes et algorithmes pour ballons / Jean-Paul Delahaye | Delahaye, Jean-Paul

Graphes et algorithmes pour ballons / Jean-Pa...

Article | SYRACUSE | Delahaye, Jean-Paul | 2009

Les sculptures réalisées avec des ballons sont à l'origine d'un nouveau domaine de recherche mathématique : l'algorithmique des ballons

Dessous des cartes du rulpidon (Le) / Sylvie Benzoni-Gavage | Benzoni-Gavage, Sylvie (1967-....)

Dessous des cartes du rulpidon (Le) / Sylvie ...

Article | SYRACUSE | Benzoni-Gavage, Sylvie (1967-....) | 2024

L'étude des surfaces mathématiques trouées constitue un défi de taille. Pour appréhender le rulpidon, figure emblématique à trois trous, on s'interroge sur la possibilité de le " cartographier " en respectant certaines contraintes...

Chargement des enrichissements...