가브리엘 그래프

가브리엘 그래프 100개 랜덤 포인트

$포인트{\displaystyle }$ $a{\displaystyle }$ ${\displaystyle$ a$}$과 b {\$displaystyle b}$은(는) 가브리엘 이웃이며$$, c ${\displaystyle c}$이(가) 직경 원 밖에 있기$$ 때문이다.

원 안에$$ 점 $c{\displaystyle }$ ${\displaystyle c}$이(가) 존재하기 때문에 점 a ${\displaystyle a}$ 및 $b$ ${\displaystyle b}$이(가) 가브리엘 이웃이 되는 것을$$ 방지한다.

수학 및 계산 기하학에서 유클리드 평면에 있는 점의$$ S $설정{\displaystyle }${\$displaystyle S}$에 대한 가브리엘 그래프는 그러한 점의 근접성 또는 근접성에 대한 하나의 개념을 표현한다.형식적으로, $직경$으로$${\$displaystyle p$$\in$ S$}$을(를$$) 갖는 닫힌 디스크가 다른 점을 포함하지 않을 때 ${\displaystyle \mathrm{정확히}}$ ${\displaystyle \mathrm{인접}}$해 있는$$ $꼭지점{\displaystyle }$ $S{\displaystyle }${\$displaystyle$ $s}$이(가$)$ 설정된 $그래프{\displaystyle }$ G ${\displaystystyle$ $G$$}$이다.동일한 인접성 기준을 표현하는 또 다른 방법은 $p{\displaystyle }$ ${\displaystyle p}$과($와{\displaystyle }$)$q$ {\$displaystyle$q}이(가) 중간점에 가장 가까운 두 점이어야 하며$$, 다른 지정된 점만큼 가까운 점이 없어야 한다는 것이다.가브리엘 그래프는 자연스럽게 더 높은 차원으로 일반화되는데, 빈 디스크가 텅 빈 닫힌 공으로 대체된다.가브리엘 그래프는 K의 이름을 따서 명명되었다. 로버트 R과 함께 논문에서 그들을 소개한 루벤 가브리엘. 1969년 소칼.^[1]

퍼콜레이션

무한 무작위 점 집합의 가브리엘 그래프의 경우, 유한 사이트 퍼콜레이션 임계값은 연결을 지원하는 데 필요한 포인트의 분율을 제공한다. 임계값보다 정점 수가 적은 임의 부분 집합이 주어진다면, 나머지 그래프에는 거의 유한한 연결 구성요소만 있을 것이다. 반면, 무작위 부분 집합의 크기가 t보다 클 경우,hreshold, 그러면 나머지 그래프는 거의 확실히 무한 성분(유한 성분뿐만 아니라)을 가질 것이다.이 임계값은 베르틴, 빌리오트 & 드루일렛(2002)에 의해 존재한다는 것이 증명되었고,^[2] 사이트와 채권 임계값의 보다 정확한 값은 노렌브록에 의해 주어졌다.^[3]

관련 기하 그래프

가브리엘 그래프는 들로나이 삼각측량(Delaunay triangulation)의 서브그래프다.Delaunay 삼각측정이 주어지면 선형 시간에 찾을 수 있다.^[4]

가브리엘 그래프는 하위그래프로 유클리드 최소 스패닝 트리, 상대 이웃 그래프, 가장 가까운 이웃 그래프를 포함하고 있다.

그것은 베타 골격의 한 예다.베타 골격처럼, 그리고 델라우나이 삼각측량과는 달리 기하학적 스패너가 아니다: 어떤 점 집합의 경우 가브리엘 그래프 내의 거리는 점 사이의 유클리드 거리보다 훨씬 클 수 있다.^[5]

참조