슈나이더의 정리
위키백과, 우리 모두의 백과사전.
슈나이더의 정리(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인 경우이다.
주석 [편집]
참고 문헌 [편집]
- 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.
