Graphe planaire

Un article de Wikipédia, l'encyclopédie libre.

Dans la théorie des graphes, un graphe planaire est un graphe quelconque qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre.

Sommaire 1 Exemples 2 Caractérisation de Kuratowski 3 Intérêt 4 Liens externes

[modifier] Exemples

1) 2) 3) 4)

1. Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.
2. C'est un graphe complet à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle 1 2 3, on constate qu'il n'y a plus d'intersection d'arêtes.
3. C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.
4. C'est un graphe complet biparti à 6 sommets, 3 d'entre eux se connectant aux trois autres (K3,3). Il n'est pas planaire.

En fait, K5 et K3,3 sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.

[modifier] Caractérisation de Kuratowski

Le mathématicien polonais Kazimierz Kuratowski a établi la caractérisation suivante des graphes planaires :

Un graphe fini est planaire si et seulement si il ne contient pas de sous-graphe qui est une expansion de K₅ (la clique à 5 sommets) ou K_3,3 (le graphe complet biparti à 3+3 sommets).

L'expansion d'un graphe est le résultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arêtes (par exemple, transformation de l'arête •——• en •—•—•).

[modifier] Intérêt

Voici un problème classique du cavalier aux échecs. Sur un échiquier, on dispose un cavalier. Le but est de le faire passer par toutes les cases, une seule fois par case, en respectant le mouvement classique de la pièce aux échecs. Pour illustrer le problème, on utilise ici un plateau de quatre cases sur trois rangées. Le problème est représenté par un graphe de mouvement ; les sommets du graphe correspondent aux cases de l’échiquier ; les arcs figurent les mouvements possibles. Ainsi, à partir de la case 1, il est possible de se rendre à la case 8 ou à la case 6 car celles-ci sont liées à la première sur le graphe.

Présenté de cette manière, le problème reste complexe. Toutefois, le graphe est planaire et on peut le représenter de façon plus intuitive. On peut facilement extraire de cette nouvelle représentation une solution (tracée en vert) partant de la case 3 et arrivant à la case 10.

La propriété du graphe planaire ne sert souvent que l'intérêt de savoir s'il est possible de présenter facilement les problèmes au cerveau humain ; pour la machine, si les algorithmes n’utilisent pas de recherche topographique et que le graphe n'est pas réorganisé, cela revient au même.

[modifier] Liens externes

• bibliothèque d'algorithmes et éditeur de graphes — bibliothèque d'algorithmes sur les graphes en GPL, parmi lesquels un test de planarité, une représentation planaire, une exhibition de sous-graphes de Kuratowski en temps linéaire.
• Planarity — pour jouer avec les graphes planaires.