Gabrielgraaf

Punten $a$ en $b$ zijn 'Gabriel-buren', omdat er geen andere punten in de cirkel met diameter $ab$ 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 definieerden een graaf waarin twee punten $a$ en $b$ alleen dan met elkaar zijn verbonden, als alle andere punten buiten de cirkel met het lijnstuk $ab$ als middellijn liggen. De graaf die zo ontstaat, noemt men de gabrielgraaf. De definitie kan naar drie of meer dimensies worden uitgebreid.

Als $d(a,b)$ de euclidische afstand tussen punten $a$ en $b$ voorstelt, betekent dit dat $a$ en $b$ dan en slechts dan worden verbonden als:

$d(a,b)^{2}<d(a,c)^{2}+d(c,b)^{2}$

voor ieder punt $c$ in de verzameling verschillend van $a$ en $b$.

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.

Voetnoten