조합 지도

Combinatorial map

결합 지도는 세분화된 객체와 함께 위상학적 구조를 모델링하는 결합 객체다.역사적으로, 이 개념은 평면 그래프인 다면체 표면을 위해 J. Edmonds에 의해 비공식적으로 도입되었다.A씨가 '콘스텔레이션스(Constellations)'라는 이름으로 처음 확정한 형식적 표현을 받았다.자크 그러나 이 개념은 이미 헤우드 지도 채색 문제의 유명한 해법에서 게르하르트 링겔과[3] J.W.T 영스의 "회전"이라는 이름으로 널리 사용되었다."구성"이라는 용어는 유지되지 않았고 대신 "조합 지도"가 선호되었다.그 개념은 후에 더 높은 차원 방향의 세분화된 사물을 나타내기 위해 확장되었다.조합 맵은 이미지 표현과 처리, 기하학적 모델링에서 효율적인 데이터 구조로 사용된다.이 모델은 단순화 복합체 및 조합 토폴로지와 관련이 있다.조합 지도는 뫼비우스 스트립이나 클라인 병과 같은 방향성이 없는 물체를 나타낼 수 있는 일반화된 지도까지 확장되었다는 점에 유의한다.결합 지도는 경계 표현 모델이다. 그것은 경계로 물체를 나타낸다.

조합 지도는 둘 다 방향적으로 내장된 그래프를 나타내기 때문에 회전 시스템과 동일하다.

동기

몇몇 애플리케이션은 개체의 분열을 나타내기 위해 데이터 구조를 요구한다.예를 들어, 2D 물체는 꼭지점(0-셀), 가장자리(1-셀), 면(2-셀)으로 분해될 수 있다.보다 일반적으로 n차원 물체는 0~n차원 셀로 구성된다.더욱이 이러한 세포들 사이의 이웃 관계를 나타내는 것도 종종 필요하다.

따라서 우리는 분단의 모든 세포와 더불어 이 세포들 사이의 모든 발생과 인접 관계를 기술하고자 한다.표시된 모든 세포가 심플렉스일 때는 단순화 콤플렉스가 사용될 수 있지만, 어떤 종류의 세포라도 대표하고 싶을 때는 결합 지도나 일반화 지도와 같은 세포 위상학적 모델을 사용할 필요가 있다.

평면 그래프 표현

조합 지도에[4][5] 대한 첫 번째 연구는 평면 그래프를 포함하는 표면에 있는 그래프의 조합 표현을 개발한다: 2차원 조합 지도(또는 2-맵)는 다음과 같은 3중 M = (D, σ, α)이다.

  • D는 유한한 다트 집합이다.
  • σ은 D에 대한 순열이다.
  • α는 고정점이 없는 D에 대한 비자발성이다.

직관적으로 2맵은 각 가장자리가 두 개의 다트(반쪽 편집이라고도 함)로 세분되는 평면 그래프에 해당한다.순열 σ은 각 다트에 대해 정점을 양의 방향으로 돌림으로써 다음 다트를 주고, 다른 순열 α는 각 다트에 대해 동일한 에지의 다른 다트를 준다.

α는 에지(프랑스어에서는 아레테의 알파)를, α는 정점(프랑스어에서는 소멧의 시그마)을 검색할 수 있게 한다.우리는 각각의 다트에 대해 같은 얼굴의 다음 다트를 주는 define = o o α를 정의한다(프랑스어로도 얼굴용 피).

따라서 순열이 σ인지 φ인지에 따라 결합 지도를 나타내는 두 가지 방법이 있다(아래 예 참조).이 두 가지 표현은 서로 이중적이다: 정점과 얼굴은 교환된다.

조합 지도 예제: 우리가 표기법(D, σ, α)을 사용하는지 또는 (D, α, α)을 사용하는지에 따라 평면 그래프와 두 개의 조합 지도.
평면 그래프
해당 결합 지도(D, σ, α)다트는 번호가 매겨진 세그먼트로 표시되며, α로 연결된 두 개의 다트는 연속적으로 그리고 작은 막대(예: α(1)=2)로 구분된다.
해당 결합 지도(D, φ, α)다트는 번호가 매겨진 화살표로 나타내고, ,으로 연결된 다트 2개는 연속적으로 그린다(예: φ(1)=3), α로 연결된 다트 2개는 평행으로 그리고 역방향으로 그린다(예: α(1)=2).

일반적 정의

어떤 차원에서도 조합지도의 정의는 다음과 같다.[6][7]

n-차원 결합체 지도(또는 n-map)는 (n + 1)-투플 M = (D, β1, ..., βn)로서 다음과 같다.

  • D는 유한한 다트 집합이다.
  • β는1 D에 대한 순열이다.
  • β2, ..., β는n D에서 비자발적이다.
  • βi o β는j i + 2 ≤ j(i, j ∈ { 1, ,..., n })일 경우 비자발적이다.

n차원 결합 지도는 폐쇄된 방향의 n차원 공간의 분열을 나타낸다.다트는 일대일 매핑을 정의하는 데만 필요한 추상적 요소다.이 정의의 마지막 줄은 표시된 개체의 위상적 타당성을 보장하는 제약조건을 수정한다. 결합 지도는 준매니폴드 분할을 나타낸다.2차원 콤비네이터럴 맵의 초기 정의는 n = 2를 고정하고 β에1 의한 σ, α에2 의한 이름을 바꾸면 검색할 수 있다.

참고 항목

참조

  1. ^ Edmonds J, 다면 표면의 조합 표현, 통지 아머.수학. Soc, 제7권, 1960년
  2. ^ 자크 A, 별자리 et Graphes Topologicals, Colorque Math.Soc. 야노스 볼랴이, 657-672, 1970.
  3. ^ 링겔 G, 지도 색상 정리, 스프링거-베를라크, 1974년 베를린
  4. ^ 자크, A.별자리 등 소유주 알제브리크는 토폴로지, 박사 논문, 파리 1969년
  5. ^ Cori R, Un code pour les pour les graphes et ses 애플리케이션, Astérisque, vol. 27, 1975
  6. ^ Lienhardt P, 경계표현을 위한 위상학적 모델 : n차원 일반화된 지도와의 비교, 컴퓨터 지원 설계, 제23권, 제1권, 페이지 59-82, 1991.
  7. ^ Lienhardt P, N차원 일반화된 결합 지도와 세포 준매니폴드, 계산 기하학 및 응용에 관한 국제 저널, 제4권, 제3권, 페이지 275-324, 1994.

외부 링크

  • CGAL의 Computing Geometric Algorithm Library의 조합 지도:
    • Damiand, Guillaume. "Combinatorial maps". Retrieved February 6, 2021.
  • 일반 N차원 맵을 사용한 CGoGN, 조합 및 기하학적 모델링에서의 조합 맵
  • nLab의 조합 지도