graphe planaire
- Domaine
-
- informatiqueprogrammation informatique
- Dernière mise à jour
Définition :
Graphe non orienté que l'on peut dessiner sur un plan de telle manière que les sommets soient des points distincts, les arêtes des courbes simples et que deux arêtes ne s'intersectent pas en dehors de leurs extrémités.
Notes :
La notion de graphe planaire est utilisée dans la réalisation des circuits électroniques imprimés.
Une courbe de Jordan est une application F réelle continue de [0, 1] dans R . À une arête (a, b) d'un graphe non orienté est associée une courbe de Jordan telle que F (0) = a, F (1) = b. On impose que F soit injective. On appelle représentation d'un graphe non orienté la figure obtenue en associant à chaque arête une courbe de Jordan ainsi définie. Un graphe non orienté est planaire si et seulement s'il existe une représentation du graphe dans le plan telle que les courbes de Jordan associées aux arêtes ne s'intersectent qu'aux sommets. On dit qu'un graphe qui satisfait à la définition est « applicable sur un plan ». La représentation de G sur le plan est appelée « graphe planaire topologique ». Deux graphes planaires topologiques seront identiques si on peut les amener à coïncider par déformation élastique du plan. On a étudié des représentations sur des surfaces diverses : sphère, tore, etc.
Terme privilégié :
- graphe planaire n. m.
Traductions
-
anglais
Auteur : Office québécois de la langue française,Terme :
- planar graph