Gábriel gróf
A kétdimenziós térben lévő ponthalmaz Gabriel -gráfja kifejezi e pontok közelségének fogalmát. Formálisan ez egy csúcsú gráf , amelyben bármely pont és pont szomszédos, ha különbözik, azaz , és egy zárt kör , amelynek átmérője egy szakasz , nem tartalmazza a halmaz többi elemét .
A Gabriel gráfok természetesen magasabb dimenziókra általánosítanak, ahol az üres lemezeket üres zárt golyók váltják fel . Ruben Gabriel nevéhez fűződik , aki 1969-ben Robert Sokal -vel közös közleményében bemutatta őket .
Szivárgás
A véges csomóponti perkolációs küszöb létezését a Gabriel gráfokhoz Bertin, Billiot és Drouilhet [1] bizonyította, míg Norrenbrock [2] pontosabb értékeket adott mind a csomóponti, mind az él (kapcsolati) küszöbértékhez .
Kapcsolódó geometriai grafikonok
- A Gabriel-gráf a Delaunay-háromszögelés részgráfja . Lineáris időben megtalálható, ha a Delaunay-háromszögelés adott [3] .
- A Gabriel-gráf részgráfokként tartalmazza az euklideszi minimális feszítőfát , a relatív szomszédsági gráfot és a legközelebbi szomszéd gráfot .
- A gráf a béta váz egy speciális esete . A béta-csontvázakhoz hasonlóan és a Delaunay-háromszögeléstől eltérően ez a gráf nem egy geometriai feszítőfa – egyes ponthalmazok esetében a Gabriel-gráf távolsága sokkal nagyobb lehet, mint az euklideszi pontok közötti távolságok [4] .
Jegyzetek
- ↑ Bertin, Billiot, Drouilhet, 2002 .
- ↑ Norrenbrock, 2014 .
- ↑ Matula, Sokal, 1980 .
- ↑ Bose, Devroye, Evans, Kirkpatrick, 2006 .
Irodalom
- Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Continuum perkoláció a Gabriel-gráfban // Advances in Applied Probability. - 2002. - T. 34 , sz. 4 . – S. 689–701 . - doi : 10.1239/aap/1037990948 .
- Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. A Gabriel-gráfok és a β-vázak feszítési arányáról // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , sz. 2 . – S. 412–427 . - doi : 10.1137/S0895480197318088 .
- Kuno Ruben Gabriel, Robert Reuven Sokal. A földrajzi eltérések elemzésének új statisztikai megközelítése // Systematic Biology . - Szisztematikus Biológusok Társasága, 1969. - V. 18 , sz. 3 . – S. 259–278 . - doi : 10.2307/2412323 . — .
- David W. Matula, Robert Reuven Sokal. Gábriel-gráfok tulajdonságai a földrajzi eltérések kutatása és a pontok síkbeli klaszterezése szempontjából // Földrajzi címszó Anal .. - 1980. - T. 12 , no. 3 . – S. 205–222 . - doi : 10.1111/j.1538-4632.1980.tb00031.x .
- Christoph Norrenbrock. Perkolációs küszöb a síkbeli euklideszi Gabriel gráfokon . - 2014. - . - arXiv : 1406.0663 .