title: Gabrielgraaf
text: 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  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.
  
  Grafentheorie
  Meetkunde