Naar inhoud springen

Gabrielgraaf

Uit Wikipedia, de vrije encyclopedie
Punten en zijn 'Gabriel-buren', omdat er geen andere punten in de cirkel met diameter liggen.
Gabrielgraaf van een verzameling van 100 punten

De gabrielgraaf van een verzameling punten is een graaf die de "geografische verbondenheid" of de "nabijheid" van de punten uitdrukt. K Ruben Gabriel en R Sokal[1] definieerden een graaf waarin twee punten en alleen dan met elkaar zijn verbonden, als alle andere punten buiten de cirkel met het lijnstuk als middellijn liggen. De graaf die zo ontstaat, noemt men de gabrielgraaf. De definitie kan naar drie of meer dimensies worden uitgebreid.

Als de euclidische afstand tussen punten en voorstelt, betekent dit dat en dan en slechts dan worden verbonden als:

voor ieder punt in de verzameling verschillend van en .

Men kan bewijzen dat de gabrielgraaf een deelgraaf is van de delaunay-triangulatie en ook dat elke minimaal opspannende boom van de verzameling punten een deelgraaf is van de gabrielgraaf.

Gabriel en Sokal waren geen wiskundigen maar biologen die een hulpmiddel zochten om de geografische variaties te beschrijven van metingen of observaties op verschillende plaatsen. De gabrielgraaf verbindt plaatsen die 'in elkaars buurt' liggen, de graaf beeldt het begrip 'nabijheid' of 'verbondenheid' uit. In de delaunay-triangulatie, als de duale graaf van het voronoi-diagram, is dat ook het geval, maar op een andere manier. Nog een andere graaf die 'nabuurschap' uitdrukt is de relative neighborhood graph. Dat is ook een deelgraaf van de gabrielgraaf.