Extrait du Chapitre 2. Graphes et cartes

Sur un graphe, un mineur se construit comme suit : on divise les sommets
connectés en groupes, et on considère les incidences entre les différents groupements
ainsi composés (voir figure suivante). Le mineur se définit comme un graphe
dont les sommets sont les groupements (les taches grises où se trouvent les sommets)
et les arêtes sont les incidences entre ceux-ci. Ci-dessous, la construction d’un
mineur selon la technique décrite.

Un graphe et l’un de ses mineurs.

Dans le monde de la théorie des graphes, il existe certains graphes particuliers
qui ont une histoire et possèdent un petit nom bien à eux du fait de leur
importance. C’est ce qui se passe dans le problème que nous traitons. Les
graphes phares ici sont les deux qui sont présentés dans l’illustration suivante :
le graphe à cinq sommets et toutes les arêtes possibles (graphe noté $K_5$ qu’on
appelle graphe complet à cinq sommets) et le graphe à six sommets et neuf arêtes
($K_{3,3}$ ). Le lecteur peut tenter de dessiner ces graphes dans le plan sans intersection
et s’apercevra que c’est impossible. De même, on peut essayer de démontrer
qu’en ôtant l’une des arêtes, on parviendra alors à les dessiner. De fait, ces
deux graphes sont les plus petits (en termes de nombres de sommets) qui ne
soient pas planaires. Dans ce sens, ce sont des graphes non planaires minimaux,
car éliminer l’une de leurs arêtes leur permet d’acquérir la propriété de pouvoir
être tracés sans intersection.

Le graphe complet à 5 sommets,$K_5$ , et le graphe biparti $K_{3,3}$.

On peut démontrer au moyen d’un raisonnement élémentaire que ces deux
graphes ne sont pas planaires. Mais ce qui est surprenant, c’est que la réciproque
est vraie : si un graphe ne possède aucun de ces deux graphes comme mineur, alors
il est planaire. On doit ce résultat désormais classique au mathématicien polonais
Kazimierz Kuratowski (Varsovie, 1896-1980), l’un des principaux représentants
de l’école mathématique polonaise du XXe siècle. Voici l’énoncé du théorème de
Kuratowski :

« Un graphe est planaire si et seulement s’il n’a pas $K_{3,3}$ ou $K_5$ comme mineur. »

L’observation suivante se révèle très intéressante : une condition topologique comme
la planarité est intrinsèque au graphe, non pas liée à une quelconque représentation de celui-ci sur une surface. Il convient également de remarquer qu’une condition aussi
difficilement réalisable que la représentation sans intersection d’un graphe hautement
complexe se traduit par la seule recherche de deux sous-structures
clairement définies
dans celui-ci. Le théorème de Kuratowski est, de fait, la partie visible de l’iceberg d’une
construction mathématique extrêmement complexe
et riche, au cœur de l’attention
d’une grande partie de la communauté des spécialistes de la combinatoire et de l’étude
des algorithmes dans ce que l’on appelle la théorie des mineurs.

On dit que la famille des graphes planaires est fermée pour les mineurs, ce qui
signifie que tout mineur d’un graphe planaire est également planaire. Cette propriété
découle directement de la définition de mineur que nous avons énoncée
précédemment. Dans ce cas, le théorème de Kuratowski garantit que les graphes
de la famille en question sont uniquement caractérisés par les deux graphes qui
déterminent la condition de planarité. Mais est-il certain que, d’une manière
générale, toute famille de graphes fermée pour des mineurs soit caractérisée
par un ensemble fini de graphes interdits ? Cette question, appelée conjecture
de Wagner, est difficile, mais on peut y répondre par l’affirmative : toute famille
fermée pour des mineurs est caractérisée par un ensemble fini de mineurs exclus.
Ces considérations ont occupé le devant de la scène de la théorie des graphes
dans la seconde moitié du xxe siècle. Dans leur gigantesque série comportant
plus de vingt travaux scientifiques (regroupés sous le nom de « Graph Minors » et
consécutivement énumérés par des lettres latines), Neil Robertson et Paul Seymour
posent les bases structurelles de cette théorie mathématique. Ses implications
sont capitales dans la théorie des graphes actuelle et, de ce fait, une grande
partie des recherches de la discipline est aujourd’hui guidée par cette œuvre
monumentale. Le théorème de Robertson-Seymour est le résultat impressionnant
du travail conjoint des deux scientifiques :

« Soit un ensemble infini de graphes. Alors il existe deux graphes de cet ensemble
tels que l’un des deux soit mineur de l’autre. »

Cette théorie a des implications plus profondes dans l’étude structurelle des
graphes ; en réalité, il s’agit de l’un des thèmes de recherche les plus développés
dans le domaine de la combinatoire et de l’algorithmique de la théorie des graphes.

Une application industrielle de la planarité

Savoir si un graphe donné admet ou non une représentation planaire est un problème capital
dans le domaine industriel.
En électronique, il est indispensable de savoir mettre en œuvre un
modèle électrique donné de la manière la plus simple qui soit. En effet, plus il y a de complications,
plus les méthodes de production sont onéreuses. Par exemple, lorsque l’on sait quel
modèle de circuit on souhaite mettre en place, il faut être capable de dire si ce modèle peut
être représenté sur un circuit imprimé dans le plan. S’il n’est pas possible de représenter le circuit
sans intersection, le procédé industriel de mise en œuvre coûtera plus cher, dans la mesure
où les plaques de silicium auront besoin de plus d’une couche pour couvrir les différentes
connexions en cuivre. Sachant que le processus de production desdits circuits compte des
millions d’unités, l’étude de la planarité
est un facteur clé dans une
logique d’optimisation des coûts.
Il existe différents logiciels spécialement
conçus pour déterminer si
un modèle électrique admet une
représentation planaire, et, le cas
échéant, pour optimiser cette représentation
sur un circuit imprimé.

Sommaire du livre

Pour aller plus loin

Voici quelques billets et articles sur ce sujet :

• Le problème 3n+1 : élémentaire mais redoutable (I) (piste verte).

• La conjecture de Hadamard (I) (piste bleue).

• Quelques questions ouvertes sur les polyominos (piste bleue).

• Comment Google classe les pages web (piste rouge).

• Le charme discret des mathématiques ( hors-piste ).