Graphe Gabriel
- Graphe Gabriel
-
Graphe de Gabriel
Un graphe de Gabriel est un graphe qui connecte un ensemble de point dans un plan Euclidien. Étant donné un ensemble S de points dans un plan, deux points P et Q de S sont connectés par une arête dans le graphe de Gabriel de S si et seulement si le disque ayant le segment PQ comme diamètre ne contient aucun autre point de 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 R. R. Sokal en 1969.
Le graphe de Gabriel de S est un sous-graphe de la triangulation de Delaunay de S. Il peut être calculé en un temps linéaire si la triangulation de Delaunay est connue (Matula and Sokal, 1980). Le graphe de Gabriel a pour sous-graphes les arbres couvrants minimums et le graphe des plus proches voisins.
Portail des mathématiques
Catégorie : Graphe géométrique
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe Gabriel de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Gabriel Andrew Dirac — (Budapest, 13 mars 1925 Arlesheim, 20 juin 1984), mathématicien spécialiste de la théorie des graphes. Il établit une condition suffisante pour qu un graphe contienne un cycle hamiltonien. Il reçoit son doctorat en 1952 à Londres. Il est le beau… … Wikipédia en Français
Graphe de Gabriel — Un graphe de Gabriel est un graphe qui connecte un ensemble de point dans un plan euclidien. Étant donné un ensemble S de points dans un plan, deux points P et Q de S sont connectés par une arête dans le graphe de Gabriel de S si et seulement si… … Wikipédia en Français
Triangulation de Pitteway — À gauche: Une triangulation de Pitteway. Chaque arrête de la triangulation de Delaunay, en noir, coupe son dual associé dans le diagramme de Voronoi, en pointillé bleu. À droite : une triangulation de Delaunay qui n est pas une triangulation … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Réseau de Petri — Pour les articles homonymes, voir Réseau. Exemple d un réseau de Petri Place Transition, composé de : deux places, les cercles trois transitions, les traits noirs quatre arcs, les … Wikipédia en Français
Structures de données dans un SIG — Un Système d information géographique contient des données alphanumériques et des données spatiales. Dans un SIG, les données sont stockées soit sous format vectoriel, soit sous format raster[1],[2]. Le format vectoriel gère les points, les… … Wikipédia en Français
Delaunay triangulation — Triangulation de Delaunay Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles … Wikipédia en Français
Triangulation de Delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits en gris. En mathématiques et plus particulièrement en … Wikipédia en Français
Triangulation de delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles … Wikipédia en Français
