主题
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.net.cn/ToroidalGraph.html

主题分类