Graf Gabriel

De la Wikipedia, enciclopedia liberă
Graf Gabriel al 100 de puncte aleatorii
Punctele a și b sunt vecini Gabriel, deoarece c este în afara cercului cu diametrul ab
Deoarece punctul c este în cerc, a și b nu sunt vecini Gabriel

În matematică și geometria algoritmică⁠(d), graful Gabriel al unei mulțimi S de puncte din planul euclidian exprimă o noțiune de apropiere a acelor puncte. Formal, este graful cu mulțimea de noduri S în care oricare două puncte distincte și sunt considerate adiacente atunci când discul închis având drept diametru nu conține alte puncte din S. Un alt mod de a exprima același criteriu de adiacență este acela că și ar trebui să fie cele două puncte date cele mai apropiate de punctul lor de mijloc, fără ca vreun alt punct dat să fie la fel de apropiat. Grafurile Gabriel se generalizează în mod natural pentru dimensiuni mai mari, cu discurile înlocuite cu bile închise. Grafurile Gabriel sunt denumite după K. Ruben Gabriel, care le-a prezentat într-o lucrare împreună cu Robert R. Sokal în 1969.[1]

Percolare[modificare | modificare sursă]

Pentru grafurile Gabriel ale mulțimilor infinite de puncte, pragul de percolare⁠(d) este fracția de puncte necesară pentru a susține conectivitatea: dacă se dă o submulțime aleatorie cu mai puține noduri decât pragul, graful rămas va avea aproape sigur doar un număr finit de noduri conectate, iar dacă dimensiunea submulțimii aleatorie este mai mare decât pragul, atunci graful rămas va avea aproape sigur o componentă infinită (precum și componente finite). S-a demonstrat că acest prag există de către Bertin, Billiot și Drouilhet în 2002,[2] iar valori mai precise au fost date de Norrenbrock.[3]

Grafuri geometrice înrudite[modificare | modificare sursă]

Un graf Gabriel este un subgraf al triangulării Delaunay. El poate fi obținut în timp liniar din triangularea Delaunay.[4]

Graful Gabriel conține, ca subgrafuri, arborele de acoperire minim euclidian⁠(d), graful de vecinătate relativă și graful celor mai apropiați vecini.

Note[modificare | modificare sursă]

  1. ^ en Gabriel, K. Ruben; Sokal, Robert R. (), „A new statistical approach to geographic variation analysis”, Systematic Biology, 18 (3): 259–278, doi:10.2307/2412323, JSTOR 2412323 
  2. ^ en Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (), „Continuum percolation in the Gabriel graph”, Advances in Applied Probability, 34 (4): 689–701, doi:10.1239/aap/1037990948, MR 1938937 
  3. ^ en Norrenbrock, Christoph (mai 2016), „Percolation threshold on planar Euclidean Gabriel graphs”, European Physical Journal B, 89 (5), arXiv:1406.0663Accesibil gratuit, doi:10.1140/epjb/e2016-60728-0 
  4. ^ en Matula, David W.; Sokal, Robert R. (), „Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane”, Geographical Analysis, 12 (3): 205–222, doi:10.1111/j.1538-4632.1980.tb00031.xAccesibil gratuit