graphe planaire

Imaginez trois maisons à relier chacune à trois réseaux. Les maisons et les réseaux deviennent des points, les neuf raccordements deviennent des traits. Si aucun trait n'en coupe un autre, sauf à leur point d'arrivée, le dessin est planaire.

Ce qui compte n'est pas le premier tracé essayé. Un graphe est planaire dès qu'il existe au moins une manière de déplacer ses points et ses traits pour supprimer tous les croisements interdits. Pour les trois maisons, aucune disposition n'y parvient.

Un graphe est planaire lorsqu'il admet une représentation dans le plan où deux arêtes ne se rencontrent qu'en un sommet qui leur est commun. Dans un graphe orienté, la même condition porte sur les arcs. Une représentation qui respecte cette condition est un plongement planaire. La propriété appartient au graphe : un tracé particulier peut comporter des croisements alors qu'un autre tracé du même graphe n'en comporte aucun.

Pour les graphes finis, le théorème de Kuratowski, établi en 1930, donne un critère complet. Le graphe est planaire exactement lorsqu'il ne contient aucun sous-graphe obtenu en subdivisant K₅ ou K₃,₃. Le graphe K₅ relie deux à deux cinq sommets. Le graphe biparti complet K₃,₃ relie chacun des trois sommets d'un groupe à chacun des trois sommets de l'autre groupe ; il compte donc six sommets et neuf arêtes. Une expansion, aussi appelée subdivision, s'obtient en insérant zéro, un ou plusieurs sommets sur certaines arêtes, sans changer le schéma de connexion essentiel.

Le théorème de Wagner formule le même verdict autrement : un graphe est planaire si et seulement s'il ne contient ni K₅ ni K₃,₃ comme mineur. Cette caractérisation ne doit pas être confondue avec la simple recherche de K₅ ou K₃,₃ tels quels parmi les sommets visibles.

Quatre éléments interviennent. Les sommets représentent les objets reliés. Les arêtes, ou les arcs dans le cas orienté, portent les connexions entre ces sommets. Le tracé dans le plan attribue une position aux sommets et un chemin aux arêtes. Enfin, le plongement planaire est un tracé dans lequel les arêtes ne se croisent pas hors des sommets communs.

Les arêtes dépendent des sommets qu'elles relient, mais leur forme dessinée peut changer sans modifier le graphe. De même, déplacer un sommet peut supprimer un croisement du dessin sans supprimer aucune arête. L'orientation éventuelle des arcs ne définit pas la planarité : elle conserve la même exigence géométrique de non-croisement. Sommets et connexions suffisent à poser le problème ; un plongement réussi en donne le certificat visuel.

Trois maisons doivent recevoir chacune l'eau, le gaz et l'électricité par des raccordements qui ne se croisent pas. Les données sont trois maisons, trois réseaux et neuf raccordements, puisque chaque maison doit rejoindre chacun des trois réseaux.

1. Représentez les maisons par un groupe de trois sommets et les réseaux par un second groupe de trois sommets.
2. Reliez chaque sommet du premier groupe aux trois sommets du second. Aucun raccordement ne relie deux maisons ni deux réseaux.
3. Le graphe obtenu possède six sommets et neuf arêtes : c'est K₃,₃.
4. Essayez de déplacer les six sommets et de courber les arêtes sans en retirer. Un dessin particulier montre des croisements, mais le théorème de Kuratowski affirme qu'aucun tracé ne peut tous les éliminer.

Le contrôle est structurel : les neuf paires maison-réseau doivent rester présentes. Dès qu'une liaison manque, le dessin ne représente plus le problème posé et ne prouve rien sur K₃,₃. Le résultat est donc que le réseau complet des trois maisons n'est pas planaire.

Dans le problème des trois maisons, on traduit les habitations et les réseaux en sommets, puis les raccordements exigés en arêtes. Si les neuf connexions sont obligatoires, K₃,₃ apparaît et un simple changement de tracé ne résout pas les croisements.

Pour le problème des quatre couleurs, les zones voisines sont représentées par des sommets adjacents. Lorsque le graphe ainsi obtenu est planaire, quatre couleurs au plus suffisent pour que deux sommets voisins aient des couleurs différentes.

Pour décider si un graphe fini est planaire, un dessin sans croisement fournit immédiatement un plongement. Si les essais échouent, il faut préférer un critère structurel : rechercher une subdivision interdite selon Kuratowski, ou un mineur interdit selon Wagner.

Graphe planaire et plongement planaire. Le graphe est l'objet abstrait formé par les sommets et leurs connexions ; le plongement est une représentation particulière sans croisement interdit. Un dessin croisé d'un graphe ne suffit donc pas à conclure que le graphe est non planaire.

Graphe biparti et K₃,₃. Dans un graphe biparti, les sommets se répartissent en deux groupes et chaque arête relie les deux groupes. Le graphe K₃,₃ impose en plus trois sommets dans chaque groupe et toutes les neuf connexions possibles entre eux. Une liaison absente donne un autre graphe et peut changer le verdict de planarité.

Une rencontre en un sommet n'est pas un croisement interdit. Plusieurs arêtes peuvent partager une extrémité. Le symptôme problématique est une intersection située ailleurs ; il faut alors chercher un autre tracé ou établir qu'aucun n'existe.

Un essai de dessin ne tranche pas la non-planarité. Voir des croisements montre seulement que ce tracé n'est pas un plongement planaire. Pour conclure, il faut exhiber la structure interdite de Kuratowski ou appliquer la formulation de Wagner.

Les sommets ajoutés sur une arête peuvent masquer l'obstruction. Une subdivision de K₅ ou de K₃,₃ reste décisive, même si les deux graphes n'apparaissent pas tels quels. Il faut suivre les chemins entre sommets essentiels plutôt que compter seulement les arêtes directes.

Sous-graphe et mineur ne sont pas interchangeables. Kuratowski recherche un sous-graphe homéomorphe à K₅ ou K₃,₃ dans un graphe fini ; Wagner recherche K₅ ou K₃,₃ comme mineur. Mélanger les deux formulations rend le critère inexact.

Le glossaire Sous-graphe précise la structure recherchée dans le critère de Kuratowski.

La fiche Graphe complet détaille la famille à laquelle appartient l'obstruction K₅.

La notion de graphe biparti éclaire les deux groupes de trois sommets qui composent K₃,₃.

Le nombre chromatique d'un graphe prolonge le lien entre planarité et problème des quatre couleurs.

L'article Colorier les pavés du plan donne un autre cadre concret aux questions de coloration dans le plan.