Graphe planaire
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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.

Exemples

1)Graphe planaire 2)Graphe K4 3)Graphe K5 4)Graphe K3,3

  1. Ce graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) est clairement planaire (Les planaires sont des vers plats libres nageurs ou rampants. Des espèces vivent en mer, d'autres en eau douce, jusque dans les sols très humides.), car il n'existe pas d'intersection entre deux arêtes.
  2. C'est un graphe complet (Un graphe complet est un graphe dont les sommets sont tous reliés deux à deux par une arête. Dans un graphe G, on nomme clique un sous-graphe complet de G, c'est-à-dire une partie de...) à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle (En géométrie euclidienne, un triangle est une figure plane, formée par trois points et par les trois segments qui les relient. La dénomination de « triangle » est justifiée...) 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.

Caractérisation de Kuratowski

Le mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité...) 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 K5 (la clique ( En théorie des graphes, dans les ouvrages de référence, une clique est un ensemble de sommets deux-à-deux adjacents. Dans les armées, une clique désigne...) à 5 sommets) ou K3,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 •—•—•).

Intérêt

Un graphe de mouvement brut à gauche ; le même graphe réorganisé à droite
Un graphe de mouvement brut à gauche ; le même graphe réorganisé à droite

Voici un problème classique du cavalier aux échecs. Sur un échiquier, on dispose un cavalier. Le but est de le faire passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) 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 (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...) ne sert souvent que l'intérêt de savoir s'il est possible de présenter facilement les problèmes au cerveau (Le cerveau est le principal organe du système nerveux central des animaux. Le cerveau traite les informations en provenance des sens, contrôle de...) humain ; pour la machine, si les algorithmes n’utilisent pas de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par...) topographique et que le graphe n'est pas réorganisé, cela revient au même.

Page générée en 0.119 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique