Grafo de Gabriel
En geometria computacional, el grafo de Gabriel és un grafo que expressa una idea de proximitat d'un conjunt S de punts del pla Euclídeo. El grafo de Gabriel pren el seu nom del matemàtic K. Ruben Gabriel, quí els va introduir en un artícul junt a Robert Sokal en 1969.[1][2]
Formalment, és el grafo els vèrtiços del qual són els punts de S en el que dos punts P i Q són adjacents si són distints i el disc tancat que el seu diàmetro és el segment de llínea PQ no conté atres elements de S. Els grafos de Gabriel es poden generalisar a dimensions més altes, reemplaçant els discs buits per boles tancades.
-
Els punts a i b són veïns de Gabriel, si cap punt c és interior al círcul de diàmetro ab. -
La presència del punt c dins del círcul impedix que a i b puguen ser marcats com a veïns en el Grafo de Gabriel.
Propietats
[editar | editar còdic]
- El grafo de Gabriel és un grafo pla, és dir, pot ser dibuixat en el pla sense que cap aresta es creue.
- El grafo de Gabriel és un subgrafo de la triangulació de Delaunay.
- El grafo de Gabriel pot ser calculat en temps llineal a partir de la triangulació de Delaunay.[3]
- El grafo de Gabriel conté com subgrafos al arbre recubridor mínim, al grafo de veïnat relatiu, i al grafo del veí més propenc.
- És un cas d'un beta-esquelet. De la mateixa manera que els beta-esquelets, i a diferència de les triangulacions de Delaunay, no és un recobriment geomètric, ya que existixen conjunts de punts les distàncies medides dels quals dins del grafo de Gabriel poden ser molt majors que les distàncies euclidianas entre els punts[4]
- Existix un llindar d'percolación per als grafos de Gabriel de conjunts de punts finitos.[5][6]
Referències
[editar | editar còdic]- ↑ (1969).Systematic Zoology.3(18)
- 259-270.doi:10.2307/2412323.JSTOR 2412323
- ↑ . Vore en particular pp. 273–274.
- ↑ (1980).Geographical Analysis.3(12)
- 205-222.doi:10.1111/j.1538-4632.1980.tb00031.x.
- ↑ Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David (2006), "On the spanning ràtio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics, 20 (2): 412–427, MR 2257270, doi:10.1137/S0895480197318088
- ↑ Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002), "Continuum percolation in the Gabriel graph", Advances in Applied Probability, 34 (4): 689–701, MR 1938937, doi:10.1239/aap/1037990948
- ↑ Norrenbrock, Christoph (2014), Percolation threshold on planar Euclidean Gabriel Graphs, arXiv:1406.0663
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Grafo de Gabriel» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.