Qu'est-ce qu'un graphe planaire ?

Un graphe planaire est un graphe qui peut être dessiné sur un plan plat de sorte qu'aucune deux arêtes ne se croisent nulle part sauf à des extrémités partagées.

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

Il affirme qu'un graphe est non planaire si et seulement s'il contient une subdivision de K₅ ou K₃,₃ — c'est-à-dire que l'un de ces deux graphes, ou une version avec des sommets supplémentaires insérés le long de ses arêtes, apparaît comme sous-graphe.

Que sont K₅ et K₃,₃ ?

K₅ est le graphe complet à 5 sommets (chaque paire connectée). K₃,₃ est le graphe biparti complet sur deux groupes de 3 sommets chacun, avec chaque sommet d'un groupe connecté à chaque sommet de l'autre — les deux sont les plus petits graphes non planaires.

Que signifie la condition E ≤ 3V − 6 ?

Pour tout graphe planaire d'au moins 3 sommets, le nombre d'arêtes ne peut jamais dépasser 3V − 6 — une conséquence directe de la formule d'Euler pour les graphes planaires (V − E + F = 2). Dépasser cette borne prouve instantanément la non-planarité.

Pourquoi la borne est-elle plus stricte pour les graphes bipartis ?

Les graphes planaires bipartis ne peuvent avoir aucune face triangulaire (les cycles de 3 nécessitent un cycle impair, impossible dans un graphe biparti), ce qui impose une borne d'arêtes plus stricte de E ≤ 2V − 4.

Pourquoi ce vérificateur ne recherche-t-il K₅/K₃,₃ que jusqu'à 8 sommets ?

Rechercher un sous-graphe K₅ ou K₃,₃ littéral nécessite de vérifier des combinaisons de 5 ou 6 sommets du graphe, ce qui croît rapidement — 8 sommets garde cette recherche confortablement rapide tout en capturant les exemples classiques petits non planaires.

Pourquoi 'non concluant' n'est-il pas la même chose que 'planaire' ?

Ce vérificateur ne recherche K₅/K₃,₃ que comme sous-graphes littéraux, pas des subdivisions (où des sommets supplémentaires sont insérés le long des arêtes du graphe interdit) ni des mineurs — un graphe pourrait encore être non planaire d'une manière que cette recherche simplifiée ne détecte pas, donc 'non concluant' signifie 'aucune violation trouvée', pas 'planarité prouvée'.

Où la planarité des graphes est-elle utilisée dans la vie réelle ?

Elle est fondamentale pour la conception de circuits imprimés (éviter les pistes qui se croisent sur une seule couche), la disposition de cartes et diagrammes de réseau, et les algorithmes de dessin de graphes visant des visualisations lisibles et sans croisements.

Vérificateur de Graphe Planaire — Testez si un Graphe Peut Être Dessiné Sans Croisements

Notre Vérificateur de Graphe Planaire teste si un graphe pourrait potentiellement être dessiné sur un plan sans qu'aucune arête ne se croise, en appliquant la condition nécessaire de nombre d'arêtes (E ≤ 3V − 6, resserrée à E ≤ 2V − 4 pour les graphes bipartis) et, pour les graphes de 8 sommets ou moins, une recherche explicite d'un sous-graphe K₅ ou K₃,₃ — l'un ou l'autre prouvant définitivement la non-planarité selon le théorème de Kuratowski.

Réponse rapide

Saisissez votre graphe sous forme de liste d'arêtes pour vérifier la condition nécessaire de nombre d'arêtes et rechercher les sous-graphes interdits K₅/K₃,₃ — une vérification de planarité solide mais pas totalement exhaustive.

Arêtes (séparées par des virgules)

Saisissez des arêtes sous la forme NœudA-NœudB, par ex. A-B, A-C, A-D, B-C, B-D, C-D.

Comment utiliser Vérificateur de Graphe Planaire — Test de Type Kuratowski en Ligne

1
Saisissez votre graphe sous forme de liste d'arêtes séparées par des virgules, par ex. A-B, A-C, A-D, B-C, B-D, C-D.
2
Cliquez sur 'Calculer' pour vérifier les conditions nécessaires et rechercher des sous-graphes interdits.
3
Consultez le verdict — 'définitivement non planaire' ou 'probablement planaire (non concluant)' — et les étapes de raisonnement.

Pourquoi utiliser Vérificateur de Graphe Planaire — Test de Type Kuratowski en Ligne ?

Un graphe est planaire s'il peut être dessiné sur un plan plat sans que deux arêtes ne se croisent. Le théorème de Kuratowski donne une caractérisation exacte : un graphe est non planaire si et seulement s'il contient une subdivision de K₅ (le graphe complet à 5 sommets) ou de K₃,₃ (le graphe biparti complet sur deux groupes de 3). Détecter entièrement les subdivisions ou mineurs de ces graphes nécessite des algorithmes sophistiqués (comme Boyer-Myrvold) bien au-delà de ce qu'une calculatrice côté client peut exécuter instantanément — cet outil adopte donc plutôt une approche à portée transparente : il vérifie toujours la borne nécessaire sur le nombre d'arêtes (un moyen rapide et exact d'exclure de nombreux graphes non planaires), et pour les petits graphes (8 sommets ou moins), il recherche également directement K₅ ou K₃,₃ apparaissant comme sous-graphes littéraux. Trouver l'un ou l'autre prouve la non-planarité de façon concluante ; n'en trouver aucun est un fort indice de planarité mais pas une preuve complète, car cela ne détectera pas les copies subdivisées (avec arêtes étendues) de ces graphes interdits.

Questions fréquentes

Outils similaires

Validateur de Séquence de Degrés de Graphe — Théorème d'Erdős–Gallai en Ligne

Vérifiez si une séquence de nombres est une séquence de degrés valide (graphique) à l'aide du théorème d'Erdős–Gallai. Calculatrice gratuite avec vérification étape par étape.

Calculatrice de Coloration de Graphe — Algorithme de Welsh-Powell en Ligne

Coloriez les sommets d'un graphe pour qu'aucun nœud connecté ne partage une couleur, à l'aide de l'algorithme glouton de Welsh-Powell. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice de Matrice d'Adjacence — Construisez une Matrice de Graphe en Ligne

Construisez et affichez la matrice d'adjacence d'un graphe à partir d'une simple saisie de liste d'arêtes, avec sa séquence de degrés. Calculatrice gratuite, pondérée ou non pondérée.