기하 그래프 이론

Geometric graph theory
네트워크 과학
Internet_map_1024.jpg
네트워크 유형
그래프
특징들
종류들
모델
위상
역학
  • 목록
  • 분류

더 넓은 의미에서의 기하학적 그래프 이론은 기하학적 수단으로 정의되는 그래프와 관련된 그래프 이론의 크고 비정형적인 하위 영역이다. 보다 엄격한 의미에서 기하학적 그래프 이론은 기하학적 그래프의 조합적 및 기하학적 특성, 즉 직선 가장자리가 교차할 가능성이 있는 유클리드 평면에서 그려진 그래프와 정점을 연결하는 임의의 연속 곡선일 수 있는 위상학적 그래프를 연구하므로 "지오메트리 이론"이다.c 및 위상 그래프" (Pach 2013). 기하학적 그래프는 공간 네트워크로도 알려져 있다.

다양한 유형의 기하학적 그래프

평면 직선 그래프는 유클리드 평면에 정점이 점으로 포함되고, 가장자리가 비교차 선 세그먼트로 포함된 그래프다. 파리의 정리에는 모든 평면 그래프는 평면 직선 그래프로 나타낼 수 있다고 명시되어 있다. 삼각형은 더 이상 가장자리가 추가될 수 없는 평면 직선 그래프로서, 모든 면은 삼각형이기 때문에 불리운다. 특별한 경우는 이 두 점만을 포함하는 원이 존재할 때마다 두 점을 가장자리로 연결하여 평면의 점 집합에서 정의한 그래프인 델라나이 삼각형 그래프다.

다면체 또는 다면체의 1-골격은 해당 다면체 또는 다면체의 정점과 가장자리의 집합이다. 어떤 볼록한 다면체의 골격은 평면 그래프, 어떤 k차원 볼록한 폴리토프의 골격은 k 연결 그래프다. 반대로, 스타인리츠의 정리에서는 어떤 3개의 연결 평면 그래프가 볼록한 다면체의 골격이라고 말하고 있다. 이러한 이유로, 이 종류의 그래프는 다면체 그래프로도 알려져 있다.

유클리드 그래프는 정점들이 평면의 점을 나타내고, 가장자리는 그 점들 사이의 유클리드 거리와 동일한 길이를 할당하는 그래프다. 유클리드 최소 스패닝 트리는 유클리드 전체 그래프의 최소 스패닝 트리다. 거리 조건에 따라 그래프를 정의할 수도 있다. 특히 단위 거리 그래프는 평면에서 단위 거리 떨어져 있는 점 쌍을 연결하여 형성된다. Hadwiger-Nelson 문제는 이러한 그래프의 색 개수에 관한 것이다.

교차로 그래프는 각 정점이 집합과 연관되어 있고 해당 집합이 비어 있지 않은 교차점을 가질 때마다 정점이 가장자리에 의해 연결되는 그래프를 의미한다. 세트가 기하학적 물체일 때 그 결과는 기하학적 그래프가 된다. 예를 들어, 한 차원에 있는 선 세그먼트의 교차 그래프는 구간 그래프, 평면에 있는 단위 디스크의 교차 그래프는 단위 디스크 그래프다. Circle packing 정리에서는 비교차 원들의 교차 그래프가 정확히 평면 그래프라고 명시하고 있다. 스키너먼의 추측(2009년 입증)은 모든 평면 그래프를 평면 내 선 세그먼트의 교차 그래프로 나타낼 수 있다고 기술하고 있다.

점 및 선군의 Levi 그래프에는 이러한 물체 각각에 대한 꼭지점과 모든 입사 점 선 쌍에 대한 가장자리가 있다. 투영형 구성의 Levi 그래프는 많은 중요한 대칭형 그래프와 우리로 이어진다.

닫힌 다각형의 가시성 그래프는 정점을 연결하는 선 세그먼트가 폴리곤에 완전히 위치할 때마다 각 정점 쌍을 가장자리로 연결한다. 비방향 그래프를 가시성 그래프로 나타낼 수 있는지 여부를 효율적으로 테스트하는 방법은 알려져 있지 않다.

부분 입방체는 그래프의 거리가 해당 하이퍼큐브 정점 사이의 해밍 거리인 것처럼 정점이 하이퍼큐브의 정점과 연관될 수 있는 그래프다. 그래프의 반복 방향 또는 하이퍼 평면 배열의 영역 간 보조성과 같은 조합 구조의 많은 중요한 패밀리는 부분 입방체 그래프로 나타낼 수 있다. 부분 입방체의 중요한 특별한 경우는 정점이 순서가 정해진 개체 집합의 순열을 나타내고 가장자리가 순서에 인접한 개체의 스왑을 나타내는 그래프인 순면체의 골격이다. 중위수 그래프를 포함한 몇 가지 다른 중요한 등급의 그래프에는 미터법 임베딩과 관련된 정의가 있다(Bandelt & Chepoi 2008).

플립 그래프는 점 집합의 삼각형에서 형성된 그래프로, 각 꼭지점은 삼각형을 나타내고 두 개의 삼각형이 다른 가장자리를 대신하여 서로 다른 경우 가장자리로 연결된다. 또한 칸막이를 사변측정감시나 가성방정계로 분할하고 고차원 삼각측량용으로 관련 플립 그래프를 정의할 수도 있다. 볼록 폴리곤의 삼각형 플립 그래프는 연관체 또는 스타셰프 폴리토프의 골격을 형성한다. 점 집합의 정삼각형(고차원 볼록 선체의 반대)의 플립 그래프는 이른바 이차 폴리토프의 골격으로도 나타낼 수 있다.

참고 항목

참조

  • Bandelt, Hans-Jürgen; Chepoi, Victor (2008). "Metric graph theory and geometry: a survey" (PDF). Surveys on Discrete and Computational Geometry - Twenty Years Later. Contemporary Mathematics. Vol. 453. American Mathematical Society. pp. 49–86.
  • Pach, János, ed. (2004). Towards a Theory of Geometric Graphs. Contemporary Mathematics. Vol. 342. American Mathematical Society.
  • Pach, János (2013). "The beginnings of geometric graph theory". Erdös centennial. Bolyai Soc. Math. Stud. Vol. 25. Budapest: János Bolyai Math. Soc. pp. 465–484. doi:10.1007/978-3-642-39286-3_17. MR 3203608.
  • Pisanski, Tomaž; Randić, Milan (2000). "Bridges between geometry and graph theory". In Gorini, C. A. (ed.). Geometry at Work: Papers in Applied Geometry. Washington, DC: Mathematical Association of America. pp. 174–194. Archived from the original on 2007-09-27.

외부 링크