拓撲圖論
拓撲圖論是圖論的一個分支,研究曲面中的圖嵌入、圖的空間嵌入及作為拓撲空間的圖,[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 [2004]. CiteSeerX 10.1.1.499.1516
. arXiv:math.CO/0409054
. doi:10.1016/j.aim.2006.10.014
.
- ^ 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).