Graphe de Gabriel

Un graphe de Gabriel est un graphe qui connecte un ensemble de points dans un plan euclidien. Étant donné un ensemble ${\displaystyle S}$ de points dans un plan, deux points ${\displaystyle P}$ et ${\displaystyle Q}$ de ${\displaystyle S}$ sont connectés par une arête dans le graphe de Gabriel de ${\displaystyle S}$ si et seulement si le disque ayant le segment ${\displaystyle [PQ]}$ comme diamètre ne contient aucun autre point de ${\displaystyle S}$. De façon plus générale, en dimension quelconque, le graphe de Gabriel connecte n'importe quelle paire de points formant les extrémités du diamètre d'une sphère vide. Les graphes de Gabriel sont nommés ainsi d'après K. R. Gabriel, qui les a introduits dans un article avec Robert R. Sokal (en) en 1969.

Le graphe de Gabriel de ${\displaystyle S}$ est un sous-graphe de la triangulation de Delaunay de ${\displaystyle S}$. Il peut être calculé en un temps linéaire si la triangulation de Delaunay est connue (Matula et Sokal, 1980). Le graphe de Gabriel a pour sous-graphes les arbres couvrants minimums et le graphe des plus proches voisins.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.