Grev Gabriel

Gabriel-grafen for et sæt punkter i et todimensionelt rum udtrykker konceptet om nærhed af disse punkter. Formelt er dette en graf med hjørner , hvor alle punkter og er tilstødende, når de er forskellige, det vil sige , , og en lukket cirkel med et segment som en diameter ikke indeholder andre elementer i sættet . $S$ $G$ $S$ $p\in S$ $q\in S$ $p\neq q$ ${\overline {pq))$ $S$

Gabriel-grafer generaliserer naturligvis til højere dimensioner, hvor tomme skiver erstattes af tomme lukkede kugler . Opkaldt efter Ruben Gabriel , som introducerede dem i et fælles papir med Robert Sokal i 1969.

Lækage

Eksistensen af en endelig node- perkolationstærskel for Gabriel-grafer blev bevist af Bertin, Billiot og Drouilhet [1] , mens Norrenbrock [2] gav mere præcise værdier for både node- og kant(forbindelse)-tærsklerne .

Relaterede geometriske grafer

Gabriel-grafen er en undergraf af Delaunay-trianguleringen . Den kan findes i lineær tid, hvis Delaunay-trianguleringen er givet [3] .

Gabriel-grafen indeholder som undergrafer det euklidiske minimumspændingstræ , den relative nabograf og grafen for den nærmeste nabo .

Grafen er et specialtilfælde af beta-skelettet . Ligesom beta-skeletter og, i modsætning til Delaunay-triangulering, er denne graf ikke et geometrisk spændingstræ - for nogle sæt punkter kan afstandene i Gabriel-grafen være meget større end de euklidiske afstande mellem punkter [4] .

Noter

↑ Bertin, Billiot, Drouilhet, 2002 .
↑ Norrenbrock, 2014 .
↑ Matula, Sokal, 1980 .
↑ Bose, Devroye, Evans, Kirkpatrick, 2006 .

Litteratur

Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Kontinuum perkolation i Gabriel-grafen // Advances in Applied Probability. - 2002. - T. 34 , no. 4 . — S. 689–701 . - doi : 10.1239/aap/1037990948 .
Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. Om spændingsforholdet mellem Gabriel-grafer og β-skeletter // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , no. 2 . — S. 412–427 . - doi : 10.1137/S0895480197318088 .
Kuno Ruben Gabriel, Robert Reuven Sokal. En ny statistisk tilgang til geografisk variationsanalyse // Systematisk biologi . - Selskabet for Systematiske Biologer, 1969. - V. 18 , Nr. 3 . — S. 259–278 . - doi : 10.2307/2412323 . — .
David W. Matula, Robert Reuven Sokal. Egenskaber for Gabriel-grafer, der er relevante for forskning i geografisk variation og klyngedannelse af punkter i planet // Geogr. Anal .. - 1980. - T. 12 , no. 3 . — S. 205–222 . - doi : 10.1111/j.1538-4632.1980.tb00031.x .
Christoph Norrenbrock. Perkolationstærskel på plane euklidiske Gabriel-grafer . - 2014. - . - arXiv : 1406.0663 .