跳转到内容

拓扑图论

维基百科,自由的百科全书
帕普斯图是嵌入及在环面中的相关映射

拓扑图论图论的一个分支,研究曲面中的图嵌入图的空间嵌入及作为拓扑空间[1]还研究图的浸入

将图嵌入曲面意味着在曲面(如球面)上绘制图,而不使两条相交。常作为数学谜题的基本嵌入问题是三间小屋问题,其他应用如印刷电子电路,即在电路板(面)上印刷(嵌入)电路(图),且不短路

作为拓扑空间的图

无向图,可将抽象单纯复形C与每个顶点的单元素集同每个边的2元素集联系起来。复形的几何实现|C|由每条边的单位区间[0,1]的副本组成,这些区间的端点在顶点处粘合在一起。这样来看,将图嵌入曲面或作为其他图的细分都是拓扑嵌入的实例,图同胚只是拓扑同胚的特例,连通图的概念与拓扑连通重合,并且当且仅当连通图的基本群平凡时,才是

与图相关的其他单纯复形还有团复形 (以图的每个为集合)与匹配复形(以图的每个匹配为集合)(等同于线图补集的团复形) 。完全二分图的匹配复形称作棋盘复形,因为其也可描述为棋盘上非攻击车集合的复形。[2]

实例研究

约翰·霍普克洛夫特罗伯特·塔扬[3]提出了一种图的平面性检验的方法,且用时与边数成线性关系。他们的算法通过构建图嵌入(他们称作“棕榈树”)实现。高效的平面性检验是图形绘制的基础。

金芳蓉等人[4]研究了书嵌入问题,图的顶点沿书脊排列,图的边分别绘制在不同页上,使同一页的边不交叉。这个问题抽象了多层印刷电路板布线问题。

通过图子式理论和图结构定理图嵌入还可用于证明图的结构结果。

另见

参考

  1. ^ Gross, J.L.; Tucker, T.W. Topological graph theory. Dover. 2012 [1987] [2024-01-19]. ISBN 978-0-486-41741-7. (原始内容存档于2022-09-30). 
  2. ^ Shareshian, John; Wachs, Michelle L. Torsion in the matching complex and chessboard complex. Advances in Mathematics. 2007, 212 (2): 525–570 [2004]. CiteSeerX 10.1.1.499.1516可免费查阅. arXiv:math.CO/0409054可免费查阅. doi:10.1016/j.aim.2006.10.014可免费查阅. 
  3. ^ Hopcroft, John; Tarjan, Robert E. Efficient Planarity Testing (PDF). Journal of the ACM. 1974, 21 (4): 549–568. S2CID 6279825. doi:10.1145/321850.321852. hdl:1813/6011可免费查阅. 
  4. ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design (PDF). SIAM Journal on Algebraic and Discrete Methods. 1987, 8 (1): 33–58 [2023-12-02]. doi:10.1137/0608002. (原始内容存档 (PDF)于2017-09-21).