Graf 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 $G$ cu mulțimea de noduri $S$ în care oricare două puncte distincte $p\in S$ și $q\in S$ sunt considerate adiacente atunci când discul închis având $pq$ drept diametru nu conține alte puncte din $S$ . Un alt mod de a exprima același criteriu de adiacență este acela că $p$ și $q$ 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]

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

Percolare

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

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

^ en Gabriel, K. Ruben; Sokal, Robert R. (1969), „A new statistical approach to geographic variation analysis”, Systematic Biology, 18 (3): 259–278, doi:10.2307/2412323, JSTOR 2412323
^ en Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002), „Continuum percolation in the Gabriel graph”, Advances in Applied Probability, 34 (4): 689–701, doi:10.1239/aap/1037990948, MR 1938937
^ en Norrenbrock, Christoph (mai 2016), „Percolation threshold on planar Euclidean Gabriel graphs”, European Physical Journal B, 89 (5), arXiv:1406.0663  , doi:10.1140/epjb/e2016-60728-0
^ en Matula, David W.; Sokal, Robert R. (1980), „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.x

Portal Matematică

[gabsok-1] Gabriel, K. Ruben; Sokal, Robert R. (1969), „A new statistical approach to geographic variation analysis”, Systematic Biology, 18 (3): 259–278, doi:10.2307/2412323, JSTOR 2412323

[bbd-2] Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002), „Continuum percolation in the Gabriel graph”, Advances in Applied Probability, 34 (4): 689–701, doi:10.1239/aap/1037990948, MR 1938937

[nor-3] Norrenbrock, Christoph (mai 2016), „Percolation threshold on planar Euclidean Gabriel graphs”, European Physical Journal B, 89 (5), arXiv:1406.0663  , doi:10.1140/epjb/e2016-60728-0

[matsok-4] Matula, David W.; Sokal, Robert R. (1980), „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.x 

[1]

[2]

[3]

[4]