Vérificateur de Graphe Planaire

Vérificateur de Graphe Planaire

Le Vérificateur de Graphe Planaire détermine si un graphe simple non orienté est planaire — c'est-à-dire s'il peut être dessiné dans le plan sans qu'aucune paire d'arêtes ne se croise — et, lorsque le graphe échoue au test, il trouve et visualise le témoin de Kuratowski : une subdivision de K₅ (le graphe complet à 5 sommets) ou de K₃,₃ (le graphe biparti complet à 3 + 3 sommets). Cet outil est conçu pour l'enseignement, les échauffements de programmation compétitive et la vérification rapide de petites constructions de graphes.

Que signifie "planaire" ?

Un graphe G = (V, E) est planaire s'il peut être immergé dans le plan de sorte que les arêtes ne se rencontrent qu'à leurs extrémités communes — aucun croisement. De même, G peut être dessiné sur la surface d'une sphère sans croisements. La planarité est une propriété purement topologique : elle ne dépend pas de la manière dont vous dessinez le graphe, mais seulement de l'existence d'un dessin sans croisement.

Les graphes planaires apparaissent partout — réseaux routiers et de services publics, routage de circuits imprimés, graphes d'arêtes des solides de Platon et structure des faces des polyèdres. Pourtant, de nombreux graphes "naturels" sont obstinément non planaires : dès que vous essayez de relier 3 maisons à 3 services publics sans croisement, vous vous heurtez à la barrière K₃,₃.

Théorème de Kuratowski — Le cœur du vérificateur

Kazimierz Kuratowski a prouvé en 1930 que la planarité possède une caractérisation purement combinatoire :

Une subdivision d'un graphe H est obtenue en remplaçant certaines arêtes de H par des chemins plus longs dont les sommets internes sont tous de nouveaux sommets de degré 2. Le théorème de Kuratowski stipule donc que K₅ et K₃,₃ sont les seules obstructions à la planarité — tout graphe non planaire contient l'un d'eux sous une forme "étirée".

Les graphes interdits

Formule d'Euler et conditions nécessaires rapides

Avant de lancer la recherche de subdivision (relativement coûteuse), le vérificateur applique deux conditions nécessaires rapides dérivées de la formule d'Euler : pour tout graphe planaire connecté dessiné dans le plan avec V sommets, E arêtes et F faces (en comptant la face extérieure non bornée), nous avons

Combiné à l'observation que chaque face d'un graphe planaire simple possède au moins 3 arêtes sur sa frontière, nous obtenons la borne supérieure des arêtes

Tout graphe violant ces inégalités est immédiatement non planaire, aucune recherche de subdivision n'est nécessaire. K₅ a m = 10, n = 5 ⇒ 3n − 6 = 9, donc 10 > 9 — viole la borne. K₃,₃ a m = 9, n = 6 ⇒ 2n − 4 = 8, donc 9 > 8 — viole la borne bipartite.

Comment fonctionne la recherche de subdivision

Après les vérifications rapides d'Euler, le vérificateur recherche directement une subdivision :

1. Victoire rapide — détecter K₅ ou K₃,₃ comme sous-graphe littéral. Si 5 sommets sont adjacents deux à deux, c'est un K₅ pur. Si 6 sommets se divisent en 3 + 3 avec les 9 arêtes croisées présentes, c'est un K₃,₃.
2. Recherche de subdivision K₅. Pour chaque ensemble candidat de 5 sommets de "branche" (chacun de degré ≥ 4 dans G), tenter de trouver 10 chemins — un par paire de branches — qui sont intérieurement disjoints au niveau des sommets (aucun sommet hors branche n'apparaît dans plus d'un chemin) et évitent d'utiliser les autres branches comme sommets internes. Un résultat positif prouve la non-planarité.
3. Recherche de subdivision K₃,₃. Choisir 6 branches (chacune de degré ≥ 3) et une bipartition 3 + 3. Rechercher 9 chemins de paires croisées avec la même exigence de disjonction interne.
4. Aucun témoin ⇒ planaire. Si aucune subdivision n'est trouvée dans les limites de taille, le théorème de Kuratowski garantit que le graphe est planaire.

La recherche de chemins disjoints au niveau des sommets est globalement NP-difficile, c'est pourquoi le vérificateur utilise une recherche gloutonne aléatoire bornée : chaque itération ordonne les paires requises par difficulté, choisit d'abord un chemin pour la paire la plus difficile à l'aide d'un BFS aléatoire, supprime ces sommets internes et continue. Si cet ordonnancement particulier échoue, il réessaie avec un ordre mélangé — jusqu'à 40 tentatives par configuration de branche. Sur tous les petits graphes testés (jusqu'à 16 sommets), cela suffit pour localiser un témoin dès qu'il en existe un.

Comment utiliser ce calculateur

1. Choisissez un format d'entrée à l'aide des onglets en haut : liste d'arêtes ou liste d'adjacence. Les deux encodent le même graphe.
2. Entrez votre graphe. Le graphe est traité comme non orienté, donc A-B et B-A représentent la même arête.
3. Cliquez sur Vérifier la Planarité. L'outil affiche un verdict, présente le raisonnement pas à pas (Euler, biparti, Kuratowski) et génère le graphe.
4. Pour un graphe non planaire, la visualisation colore la subdivision K₅ ou K₃,₃ et énumère les 10 (ou 9) chemins disjoints au niveau des sommets. Cliquez sur une ligne de chemin pour l'isoler.
5. Pour un graphe planaire, le nombre de faces F = m − n + 1 + c est indiqué parallèlement à la structure du graphe.

Exemple concret 1 — K₄ est planaire

K₄ a n = 4, m = 6. Tout graphe sur ≤ 4 sommets est planaire, et en effet K₄ s'immerge comme un triangle avec un seul sommet à l'intérieur relié aux trois coins. Euler indique F = 6 − 4 + 2 = 4 faces : trois faces triangulaires internes plus la face externe.

Exemple concret 2 — K₃,₃ est non planaire

K₃,₃ a n = 6, m = 9. Il est biparti, la borne bipartite s'applique donc : m = 9 > 2n − 4 = 8. Cela seul prouve la non-planarité. Le témoin est trivial — K₃,₃ est lui-même le sous-graphe interdit. L'outil met alors en évidence la partition 3 + 3 et les 9 arêtes directes.

Exemple concret 3 — Le graphe de Petersen

Le graphe de Petersen a n = 10, m = 15, donc m ≤ 3n − 6 = 24 et les vérifications rapides d'Euler réussissent. Pourtant, il est célèbre pour être non planaire. Le vérificateur localise une subdivision K₃,₃ : choisissez six sommets du pentagone extérieur et du pentagramme intérieur de sorte que chaque paire croisée puisse être acheminée via les quatre sommets restants par des chemins disjoints au niveau des sommets. L'outil dessine le témoin, rendant tangible la géométrie des années 1930.

Applications de la planarité

• Routage VLSI et PCB. Un circuit monocouche n'est réalisable que si le graphe de connexion est planaire ; les réseaux non planaires imposent des vias ou des couches supplémentaires.
• Dessin et visualisation de graphes. Les graphes planaires permettent des tracés clairs et sans croisement — utiles pour les plans de métro, les graphes d'appels et les schémas.
• Conception d'algorithmes. De nombreux problèmes NP-difficiles (coupe maximale, couverture de sommets, isomorphisme de graphes) deviennent polynomiaux lorsqu'ils sont limités aux graphes planaires.
• Coloration de graphes. Le théorème des quatre couleurs garantit que tout graphe planaire est colorable avec 4 couleurs — un résultat classique dont l'énoncé dépend de la planarité.
• Optimisation combinatoire. Le chemin le plus court planaire, le flot maximal et la coupe minimale bénéficient tous d'algorithmes rapides spécialisés.
• Chimie moléculaire. Les graphes d'hydrocarbures aromatiques à cycle benzénique sont planaires ; certaines molécules en cage ne le sont pas.

Foire aux questions

Que signifie planaire pour un graphe ?

Un graphe est planaire si vous pouvez le dessiner sur le plan de sorte qu'aucune paire d'arêtes ne se croise, sauf aux sommets partagés. De même, un graphe est planaire si et seulement s'il peut être dessiné sur la surface d'une sphère sans croisements. Les arbres, les cycles, le graphe du cube et les solides de Platon sont tous planaires, tandis que K₅ et K₃,₃ sont les exemples canoniques non planaires.

Qu'est-ce que le théorème de Kuratowski ?

Le théorème de Kuratowski stipule qu'un graphe fini est planaire si et seulement s'il ne contient aucun sous-graphe qui soit une subdivision de K₅ ou de K₃,₃. Une subdivision est obtenue en remplaçant certaines arêtes par des chemins plus longs, chacun passant par de nouveaux sommets de degré 2. Cela donne un certificat combinatoire concret de non-planarité.

Quelle est la différence entre K₅ et K₃,₃ ?

K₅ possède 5 sommets, dont chaque paire est reliée par une arête, pour 10 arêtes au total. K₃,₃ possède 6 sommets répartis en deux groupes de 3, chaque sommet d'un groupe étant connecté à chaque sommet de l'autre, pour 9 arêtes. Tous deux sont les plus petits graphes non planaires de leur genre, et forment ensemble les mineurs interdits pour la planarité.

Comment l'inégalité d'Euler aide-t-elle ?

La formule d'Euler V − E + F = 2 pour les graphes connectés planaires, combinée au fait que chaque face d'un graphe planaire simple a au moins 3 arêtes, donne m ≤ 3n − 6. Tout graphe simple violant cette borne est immédiatement non planaire. Pour les graphes planaires bipartis, chaque face a au moins 4 arêtes, donnant la borne plus étroite m ≤ 2n − 4. Le vérificateur applique les deux comme règles de rejet rapide.

Quelle est la limite de taille ?

Le vérificateur gère jusqu'à 16 sommets et 60 arêtes. Cela couvre les graphes classiques d'enseignement et de compétition, notamment le graphe de Petersen, le graphe de Möbius-Kantor, les petits hypercubes et le graphe complet K₇. Les graphes plus grands nécessitent des tests de planarité spécialisés en temps linéaire tels que Hopcroft-Tarjan ou la planarité gauche-droite.

Comment la subdivision témoin est-elle dessinée ?

Lorsque le graphe est non planaire, les 5 sommets de branche du K₅ trouvé — ou les 6 sommets de branche de K₃,₃ répartis en deux triplets A et B — sont mis en évidence sur un anneau interne. Les 10 (ou 9) chemins requis intérieurement disjoints au niveau des sommets sont chacun dessinés dans une couleur distincte pour que vous puissiez tracer visuellement la topologie de K₅ ou K₃,₃. Les sommets et les arêtes ne faisant pas partie de la subdivision sont estompés.

Lectures complémentaires

• Graphe planaire — Wikipédia
• Théorème de Kuratowski — Wikipédia
• Caractéristique d'Euler — Wikipédia
• Graphe de Petersen — Wikipédia
• Théorème de Wagner (version mineure) — Wikipédia