Hrabě Gabriel

Gabrielův graf množiny bodů ve dvourozměrném prostoru vyjadřuje pojem blízkosti těchto bodů. Formálně se jedná o graf s vrcholy , ve kterém jsou libovolné body a sousedící, když jsou různé, tedy , , a uzavřený kruh s úsečkou jako průměrem neobsahuje další prvky množiny . $S$ $G$ $S$ $p\in S$ $q\in S$ $p\neq q$ ${\overline {pq))$ $S$

Gabrielovy grafy přirozeně zobecňují do vyšších dimenzí, kde jsou prázdné disky nahrazeny prázdnými uzavřenými koulemi . Pojmenované po Rubenu Gabrielovi , který je představil ve společném dokumentu s Robertem Sokalem v roce 1969.

Únik

Existenci prahu perkolace konečných uzlů pro Gabrielovy grafy dokázali Bertin, Billiot a Drouilhet [1] , zatímco Norrenbrock [2] uvedl přesnější hodnoty pro prahové hodnoty uzlů i hran (spojení) .

Související geometrické grafy

Gabrielův graf je podgrafem Delaunayovy triangulace . Lze jej nalézt v lineárním čase , pokud je dána Delaunayova triangulace [3] .

Gabrielův graf obsahuje jako podgrafy euklidovský minimální kostru , graf relativního sousedství a graf nejbližšího souseda .

Graf je speciální případ beta kostry . Stejně jako beta-skelety a na rozdíl od Delaunayovy triangulace není tento graf geometrickým kostrou — pro některé sady bodů mohou být vzdálenosti v Gabrielově grafu mnohem větší než euklidovské vzdálenosti mezi body [4] .

Poznámky

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

Literatura

Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Perkolace kontinua v Gabrielově grafu // Pokroky v aplikované pravděpodobnosti. - 2002. - T. 34 , no. 4 . — S. 689–701 . - doi : 10.1239/aap/1037990948 .
Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. O poměru rozpětí Gabrielových grafů a β-skeletů // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , no. 2 . — S. 412–427 . - doi : 10.1137/S0895480197318088 .
Kuno Ruben Gabriel, Robert Reuven Sokal. Nový statistický přístup k analýze geografických variací // Systematic Biology . - Společnost systematických biologů, 1969. - V. 18 , no. 3 . — S. 259–278 . - doi : 10.2307/2412323 . — .
David W. Matula, Robert Reuven Sokal. Vlastnosti Gabrielových grafů relevantní pro výzkum geografických variací a shlukování bodů v rovině // Geografické heslo Gdǎnsk ; Anal .. - 1980. - T. 12 , no. 3 . — S. 205–222 . - doi : 10.1111/j.1538-4632.1980.tb00031.x .
Christoph Norrenbrock. Perkolační práh na rovinných euklidovských Gabrielových grafech . - 2014. - . - arXiv : 1406.0663 .