위상 그래프 이론
Topological graph theory
수학에서 위상 그래프 이론은 그래프 이론의 한 분야다. 표면의 그래프의 내장, 그래프의 공간적 내장, 위상학적 공간으로서의 그래프를 연구한다.[1] 그것은 또한 그래프의 산재에 대해서도 연구한다.
그래프를 표면에 삽입하는 것은 우리가 그래프를 표면, 예를 들어 두 가장자리가 교차하지 않는 구에 그리기를 원한다는 것을 의미한다. 수학 퍼즐로 자주 제시되는 기본적인 내장 문제는 세 가지 유틸리티 문제다. 다른 용도는 전자 회로 인쇄에서 두 개의 연결부가 서로 교차하지 않고 회로 기판(표면)에 회로(그래프)를 인쇄(임베딩)하여 단락을 초래하는 것을 목적으로 하는 경우에 찾을 수 있다.
위상학적 공간으로서의 그래프
비방향 그래프에 추상적인 단순 복합 C를 정점당 단일 요소 세트 및 에지당 2 요소 세트와 연관시킬 수 있다.[2] 복합체의 기하학적 실현 C는 에지당 단위 간격[0,1]의 복사본으로 구성되며, 이러한 간격의 끝점은 꼭지점에서 서로 붙어 있다. 이 견해에서 그래프를 지표면에 내장하거나 다른 그래프의 세분화 모두 위상학적 내장 사례로서 그래프의 동형성은 위상학적 동형성의 특화일 뿐이며, 연결된 그래프의 개념은 위상학적 연결성과 일치하며, 연결된 그래프는 만약의 경우에 한해서만 나무다.roop은 하찮은 것이다.
그래프와 관련된 다른 단순화 복합체로는 휘트니 콤플렉스 또는 클릭 콤플렉스(그래프의 clique complex)가 있으며, 그래프의 clique complex(선 그래프 보어의 clique complex)는 그래프의 clique click complex와 일치한다. 완전한 초당적 그래프의 매칭 콤플렉스를 체스판 콤플렉스라고 하는데, 체스판 위에 비공격적인 루크의 집합체라고도 설명할 수 있기 때문이다.[3]
예제 스터디
John Hopcroft와 Robert Tarjan은[4] 가장자리 수에 선형적으로 시간 단위로 그래프의 평면성을 시험하는 수단을 도출했다. 그들의 알고리즘은 그들이 "팔름나무"라고 부르는 그래프를 내장함으로써 이것을 한다. 효율적인 평면성 테스트는 그래프 그리기의 기본이다.
팬청 등은 책의 척추를 따라 선으로 그래프의 정점이 있는 책에 그래프를 삽입하는 문제를 연구했다.[5] 그것의 가장자리는 같은 페이지에 있는 가장자리가 교차하지 않도록 별도의 페이지에 그려진다. 이 문제는 다층 인쇄 회로 기판의 라우팅에서 발생하는 배치 문제를 추상화한다.
그래프 임베딩은 그래프 마이너 이론과 그래프 구조 정리를 통해 그래프에 대한 구조적 결과를 입증하는 데도 사용된다.
참고 항목
메모들
- ^ J.L. 그로스 앤 T.W. 터커, 위상학 그래프 이론, 와일리 인터사이언스, 1987
- ^ 그래프 위상, PlanetMath에서.
- ^ Shareshian, John; Wachs, Michelle L. (2004). "Torsion in the matching complex and chessboard complex". arXiv:math.CO/0409054.
{{cite arxiv}}: CS1 maint : 복수이름 : 작성자 목록(링크) - ^ Hopcroft, John; Tarjan, Robert E. (1974). "Efficient Planarity Testing" (PDF). Journal of the ACM. 21 (4): 549–568. doi:10.1145/321850.321852. hdl:1813/6011.
- ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. (1987). "Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design" (PDF). SIAM Journal on Algebraic and Discrete Methods. 8 (1): 33–58. doi:10.1137/0608002.
