슈나이더의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

슈나이더의 정리(Schnyder's theorem, -定理)은 그래프 이론정리로, 평면 그래프의 특성화를 위한 조건을 제공한다. 월터 슈나이더(Walter Schnyder)[1]1989년 증명하였다.

어떤 무향 그래프 G = (V, E)에 대해 V를 이 꼭지점, E를 이 변들의 집합이라 하자. 그러면, 여기서 부분순서 집합 P(G) = (V∪E, <)를 높이[2]가 2가 되도록 구성할 수 있다. 구체적으로, 여기서 x < y일 때 x는 꼭지점, y는 변이며, x는 y의 두 끝점 중의 하나이다. 이때 슈나이더의 정리는 다음과 같이 기술할 수 있다.

확장[편집]

슈나이더의 정리는 임의의 차원으로 확장할 수 있다.(Ossona de Mendez 1999, 2002) 일반적으로, 임의의 추상 복체(abstract simplical complex)에 대하여 이 추상 복체가 적어도 d차원 유클리드 공간에서야 기하학적으로 구현(realization)된다면, 그 면과 꼭지점으로 위의 방법과 같이 유도한 부분 순서 집합이 많아야 1+d의 순서 차원을 가진다. 슈나이더의 정리는 이 확장 형태에서 d=2인 경우이다.

주석[편집]

  1. 수학 계보 계획이 인물로 추정되는데, Schneider가 아니라 Schnyder로 쓰는 것으로 보아 독일계는 아닌 듯하므로 일단 영어식으로 읽었음. 독일계일 경우 '발터 슈니더'와 '발터 슈나이더'가 모두 가능해 보이는데, 'Schnyder'가 영어권에서만 쓰이는 철자인지 아닌지를 확인할 자료가 없어 본문의 표기는 틀린 독법일 수 있음. 그럴 경우 수정 요망.
  2. 포함하는 최대 사슬의 길이.
  3. 교집합이 해당 부분순서가 되는 완전순서들의 최소 수

참고 문헌[편집]

  • Brightwell, G.; Trotter, W. T. (1993), "The order dimension of convex polytopes", SIAM Journal on Discrete Mathematics 6 (2): 230–245, doi:10.1137/0406018, MR1215230.
  • Brightwell, G.; Trotter, W. T. (1997), "The order dimension of planar maps", SIAM Journal on Discrete Mathematics 10 (4): 515–528, doi:10.1137/S0895480192238561, MR1477654.
  • Ossona de Mendez, P. (1999), "Geometric realization of simplicial complexes", in Kratochvil, J., Proc. Int. Symp. Graph Drawing (GD 1999), Lecture Notes in Computer Science, 1731, Springer-Verlag, pp. 323–332, doi:10.1007/3-540-46648-7_33, MR1856785.
  • Ossona de Mendez, P. (2002), "Realization of posets", Journal of Graph Algorithms and Applications 6 (1): 149–153, MR1898206.
  • Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5: 323–343, doi:10.1007/BF00353652, MR1010382.