跳至內容

拓撲圖論

維基百科,自由的百科全書
帕普斯圖是嵌入及在環面中的相關映射

拓撲圖論圖論的一個分支,研究曲面中的圖嵌入圖的空間嵌入及作為拓撲空間[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).