拓扑图论
拓扑图论是图论的一个分支,研究曲面中的图嵌入、图的空间嵌入及作为拓扑空间的图,[1]还研究图的浸入。
将图嵌入曲面意味着在曲面(如球面)上绘制图,而不使两条边相交。常作为数学谜题的基本嵌入问题是三间小屋问题,其他应用如印刷电子电路,即在电路板(面)上印刷(嵌入)电路(图),且不短路。
作为拓扑空间的图编辑
对无向图,可将抽象单纯复形C与每个顶点的单元素集同每个边的2元素集联系起来。复形的几何实现|C|由每条边的单位区间[0,1]的副本组成,这些区间的端点在顶点处粘合在一起。这样来看,将图嵌入曲面或作为其他图的细分都是拓扑嵌入的实例,图同胚只是拓扑同胚的特例,连通图的概念与拓扑连通重合,并且当且仅当连通图的基本群平凡时,才是树。
与图相关的其他单纯复形还有团复形 (以图的每个团为集合)与匹配复形(以图的每个匹配为集合)(等同于线图补集的团复形) 。完全二分图的匹配复形称作棋盘复形,因为其也可描述为棋盘上非攻击车集合的复形。[2]
实例研究编辑
约翰·霍普克洛夫特和罗伯特·塔扬[3]提出了一种图的平面性检验的方法,且用时与边数成线性关系。他们的算法通过构建图嵌入(他们称作“棕榈树”)实现。高效的平面性检验是图形绘制的基础。
金芳蓉等人[4]研究了书嵌入问题,图的顶点沿书脊排列,图的边分别绘制在不同页上,使同一页的边不交叉。这个问题抽象了多层印刷电路板布线问题。
另见编辑
参考编辑
- ^ Gross, J.L.; Tucker, T.W. Topological graph theory. Dover. 2012 [1987] [2024-01-19]. ISBN 978-0-486-41741-7. (原始内容存档于2022-09-30).
- ^ Shareshian, John; Wachs, Michelle L. Torsion in the matching complex and chessboard complex. Advances in Mathematics. 2007, 212 (2): 525–570. CiteSeerX 10.1.1.499.1516 . arXiv:math.CO/0409054 . doi:10.1016/j.aim.2006.10.014 . 已忽略未知参数
|orig-date=
(帮助) - ^ 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 .
- ^ 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).
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命