主題
Search

環面圖


每個平面圖(即,圖虧格為 0 的圖)都可以在環面上嵌入。相比之下,環面圖可以在環面上嵌入,但不能在平面上嵌入,即,它們的圖虧格為 1。等價地,環面圖是非平面圖,其環面交叉數為 0,即,可以嵌入到環面表面且沒有邊交叉的非平面圖

圖虧格為 2 的圖被稱為雙環面圖 (West 2000, p. 266)。

環面圖的例子包括完全圖 K_5K_7 以及完全二分圖 K_(3,3) (West 2000, p. 267)。環面圖族包括 2n-交叉稜柱圖,對於 n>2圈補圖 C^__n,對於 n>6 (E. Weisstein,2023 年 5 月 9 日)。

如果存在,環面圖(在環面上)的對偶圖也是環面的。此類對的示例包括完全圖 K_7希伍德圖,以及 戴克圖什裡克漢德圖

對於曲面 S,(拓撲)障礙是一個圖 G,其最小度至少為 3,且不能嵌入到 S 上,但對於 G 的每條邊 eG-e(刪除了邊 eG)可以嵌入到 S 上。一個子式階障礙 G 具有附加屬性:對於 G 的每條邊 eG·e(邊 e 收縮G)可以嵌入到 S 上 (Myrvold 和 Woodcock 2018)。用於圖的環面嵌入的停用子式的完整列表尚不清楚,但已知數千個障礙 (Neufeld 和 Myrvold 1997,Chambers 2002,Woodcock 2007;參見 Mohar 和 Skoda 2020)。Chambers (2002) 發現了 239322 個拓撲障礙和 16629 個子式階障礙,包括頂點數最多為 11 個的障礙、頂點數為最多 24 個的 3-正則障礙、不連通障礙以及具有割頂的障礙。Myrvold 和 Woodcock (2018) 發現了 250815 個停用拓撲子式拓撲子式和 17523停用子式。此外,Gagarin等人 (2009) 發現了四個停用子式和十一個停用的圖擴張,用於不具有 K_(3,3) 子式的環面圖,並證明了這些列表是充分的。

下表總結了幾種型別的停用子式障礙,包括具有頂點連通度k 的障礙 (Olds 2019)。此處,G·H 表示頂點收縮,G+H 表示圖的連線

屬性計數停用子式參考文獻
K_(3,3)42K_5, K_5·K_5, G_3, G_4=3C_3+K^__2Gagarin 等人 (2009)
kappa=032K_(3,3), 2K_5, K_5 union K_(3,3)Olds (2019)
kappa=13K_(3,3)·K_(3,3), K_5·K_5, K_5·K_(3,3)Olds (2019)
kappa=268Mohar 和 Skoda (2014)

n=1, 2, ... 個節點上的環面圖的數量為 0, 0, 0, 0, 1, 14, 222, 5365, ... (OEIS A319114),並且連通環面圖的相應數量為 0, 0, 0, 0, 1, 13, 207, 5128, ... (OEIS A319115;E. Weisstein,2018 年 9 月 10 日)。

環面圖的圖虧格g=1,因此龐加萊公式給出了頂點數 V邊數 E 和麵數 F 之間的關係,如下所示

 V-E+F=0.
(1)

然而,環面圖也滿足

 2E>=3F,
(2)

這可以透過對每個面的邊數求和來推導得出。由於每個面至少有 3 條邊,因此該總和的下界為 3F。另一方面,由於每條邊恰好界定兩個面,因此它也正好是 2E (Bartlett 2015)。將這兩個公式結合起來,得到不等式

 E/V<=3
(3)

對於一個圖成為環面圖,該不等式必須成立 (West 2000, p. 268)。

對於環面圖,以下情況也為真:

 2E>=deltaV,
(4)

其中 delta最小頂點度。這可以與上面類似地透過對所有頂點的每個頂點的度數求和來推導得出。根據最小頂點度的定義,該總和必須大於 deltaV,但它也等於 2E (Bartlett 2015)。

將上述兩個不等式代入龐加萊公式,則得到

 0=V-E+F>=2/deltaE-E+2/3E,
(5)

因此對於任何環面圖,delta<=6 (Bartlett 2015)。

Duke 和 Haggard (1972;Harary等人 1973) 給出了頂點數為 8 個或更少的所有圖的虧格的判據。定義雙環面圖

B_1=K_8-K_3
(6)
B_2=K_8-(2K_2 union P_3)
(7)
B_3=K_8-K_(2,3),
(8)

其中 G-H 表示 G 減去 H 的邊。那麼,K_8子圖 G 如果包含庫拉托夫斯基圖(即,是非平面的),但不包含任何 B_i,對於 i=1,2,3,則它是環面的。


另請參見

雙環面圖停用子式圖交叉數圖虧格非平面圖平面圖椒鹽捲餅圖環面交叉數環面

使用 探索

參考文獻

Bartlett, P. "Lecture 5: Toroidal Graphs." CCS Discrete III, Week 10, UCSB. 2015. http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_discrete_s2015/ccs_discrete_s2015_lecture5.pdfChambers, J. "Hunting for Torus Obstructions." 碩士論文,計算機科學系,維多利亞大學,2002 年。Duke, R. A.; 和 Haggard, G. "The Genus of Subgraphs of K_8." Israel J. Math. 11, 452-455, 1972.Gagarin, A.; Myrvold, W.; 和 Chambers, J. "The Obstructions for Toroidal Graphs with no K_3,3's." Disc. Math. 309, 3625-3631, 2009.Harary, F.; Kainen, P. C.; Schwenk, A. J.; 和 White, A. T. "A Maximal Toroidal Graph Which Is Not a Triangulation." Math. Scand. 33, 108-112, 1973.Mohar, B. 和 Škoda, P. "Excluded Minors for the Klein Bottle I. Low Connectivity Case." 2020 年 2 月 1 日。https://arxiv.org/abs/2002.00258Mohar, B. 和 Škoda, P. "Obstructions of Connectivity Two for Embedding Graphs Into the Torus." Canad. J. Math. 66, 1327-1357, 2014.Myrvold, W. 和 Woodcock, J. "A Large Set of Torus Obstructions and How They Were Discovered." Electronic J. Comb. 25, P1.16, 2018.Neufeld, E. 和 Myrvold, W. "Practical Toroidality Testing." 載於第八屆 ACM-SIAM 離散演算法研討會論文集,SODA '97。 工業與應用數學學會,第 574-580 頁,1997 年。Olds, T. "Forbidden Graph Minors." 2019 年。https://www.whitman.edu/Documents/Academics/Mathematics/2019/Olds-Guichard.pdfRiskin, A. "On the Nonembeddability and Crossing Numbers of Some Toroidal Graphs on the Klein Bottle." Disc. Math. 234, 77-88, 2001.Sloane, N. J. A. 序列 A319114A319115,收錄於“整數序列線上百科全書”。Thomassen, C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface." Trans. Amer. Math. Soc. 323, 605-635, 1991.West, D. B. "Surfaces of Higher Genus." 圖論導論,第二版。 Englewood Cliffs, NJ: Prentice-Hall, 第 266-269 頁,2000 年。Woodcock, J. "A Faster Algorithm for Torus Embedding." 碩士論文,計算機科學系,維多利亞大學,2007 年。

請引用為

Weisstein, Eric W. “環面圖。” 來自 Web 資源。https://mathworld.tw/ToroidalGraph.html

主題分類