跳转到内容

细分 (图论)

维基百科,自由的百科全书
细分也可以用于将无回路英语Loop (graph theory)图转换成简单图[1]。上图展示了使用重心细分伪图(左)转换为简单图(右)的一个例子。

图论中,细分(subdivision)或分割[2]是指在一个图的其中一条边加入新的顶点,使这条边转变成由多个顶点构成之路径的变换,又称为扩展(expansion)[3],为图子式理论中的基本算子之一,而变换完的像称为细分图[5]

在图论的一般情况下,细分通常是指对边的细分,而在一些领域中会有对面或其他结构的细分(如高维度的标记),例如重心细分英语Barycentric subdivision[6],有时会称为剖分剖分图

定义

细分

细分是一种作用于边上的变换,因此其需作用于特定的边,令其记为e,并令e所连接的两个顶点记为u和v,而细分会在顶点u和v之间加入一个新的顶点w,并使原本的边uv改成路径uwv则完成一次细分变换,换句话说,即先在uv边之间加入顶点w,移除uv边后将u和v连到w[5]

例如现在有一条边,记作e,其由顶点uv组成,记为{u,v}:

透过细分变换,产生了新的顶点w,将e分割成两条边,分别记为e1e2,皆连到新顶点w:

而细分变换存在逆变换,称为平滑(smoothing)变换。

细分变换的结果套用平滑变换会形成原像

这两种变换的共通点是,其原像与变换像互为同胚

广义的细分

更广义的,细分变换不一定只加入一个顶点,只要在边上有加入顶点的动作,都是一种细分,更精确地说,细分变换可以定义为将图G中的某一条边e替换为具有相同端点之路径,且构成该路径的顶点皆不在原本属于图G的顶点之中,且此路径也不会跟其他现有的顶点相连[7]

细分图

假设有二图G和H,若图H可以透过反复对图G套用细分变换而得,则图H可以称为图G的细分图[5]

扩展

扩展变换是指在一张图的某个边上,加入新的为2之顶点,而产生的图可以称为原图的扩展[3]

性质

当G'是G的细分时,则G'称为G的细分图,亦可以将G'称为G的扩展,记为TG,其中T表示扩展变换。G的原有的顶点若其位于细分作用的边上时,称为TG的分支顶点(branch vertex),在细分作用的边上加入之新的顶点称为TG的细分顶点(subdivision vertex),细分后产生的边称为细分边(subdivision edge)[8],并且细分顶点具有度为2的特性[9]

历史

细分的概念应用于图论,最早出现在1930年波兰数学家卡齐米日·库拉托夫斯基提出的一类禁用准则(指满足某种条件的图就一定无法具有某个性质)中,其所提出的库拉托夫斯基定理使用了细分图的概念[2]

用途

细分可以用于几个与图论相关的证明和定理,例如判断两图是否同胚以及库拉托夫斯基定理中,对于简单图是否为平面图的准则,该定理为:如果一个简单图并不包含一个是 K5 或 K3,3细分图的子图,则该简单图平面图,反之亦然,上述两条件为当且仅当关系[2]。其中, K5 代表有 5 个点的完全图,K3,3 代表两部分各 3 个点的完全二分图,特别地,若一图的子图是K5或 K3,3细分图,则该子图又称为库拉托夫斯基子图[10]

此外,细分也可以用于将一般的图转换成简单图[1]

相关变换

细分变换在图论中有一些不同的定义,例如重心细分英语Barycentric subdivision在图论中就不是将多边形分割成三角形。

重心细分

在图论中,重心细分(Barycentric subdivision)是指将图的所有边进行细分的变换[11],为一种特殊的细分变换,其变换的像总会是二分图[12],且是一个无回路英语Loop (graph theory)[1],而任何无回路图的重心细分结果皆会是简单图[1]

重心细分可以被重复套用,任何图只要重复套用2次重心细分后结果总是简单图[11]

参见

参考文献

  1. Yellen, Jay; Gross, Jonathan L., Graph Theory and Its Applications, Discrete Mathematics and Its Applications 2nd, Boca Raton: Chapman & Hall/CRC, 2005, ISBN 978-1-58488-505-4 
  1. ^ 1.0 1.1 1.2 1.3 Ahmad, A and Imran, M and Al-Mushayt, O and Bokhary, SAUH. ON THE METRIC DIMENSION OF BARYCENTRIC SUBDIVISION OF CAYLEY GRAPHS Cay. Zn Zm (PDF). Miskolc Mathematical Notes. 2015, 16 (2): 637––646 [2019-05-11]. (原始内容 (PDF)存档于2021-01-18). 
  2. ^ 2.0 2.1 2.2 王树禾. 《圖論》. 科技出版社. 2004. ISBN 9787030124234. 
  3. ^ 3.0 3.1 Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 76 [8 August 2012]. ISBN 978-0-486-67870-2. (原始内容存档于2019-05-05). Definition 20. If some new vertices of degree 2 are added to some of the edges of a graph G, the resulting graph H is called an expansion of G. 
  4. ^ 演算法觀點的圖論. 教科书. 国立台湾大学出版中心出版. 2017: 142 [2019-05-05]. ISBN 9789863502586. (原始内容存档于2021-04-13). 
  5. ^ 5.0 5.1 5.2 算法观点的图论, 2017[4], p.142
  6. ^ Bayer, Margaret. Barycentric subdivisions. Pacific journal of mathematics (Mathematical Sciences Publishers). 1988, 135 (1): 1––16. 
  7. ^ 7.0 7.1 Diestel, R. 图 论: 第五版 (2018). Springer Graduate Texts in Mathematics (GTM). Reinhard Diestel. 2018 [2019-05-05]. (原始内容存档于2021-01-24). 
  8. ^ Liu, Xiaogang and Lu, Pengli. Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae. Linear Algebra and its Applications. 2012-12, 438: 3547–. doi:10.1016/j.laa.2012.12.033. 
  9. ^ 图 论: 第五版 (2018)[7], p. 17
  10. ^ Tutte, W. T., How to draw a graph, Proceedings of the London Mathematical Society, Third Series, 1963, 13: 743–767, MR 0158387, doi:10.1112/plms/s3-13.1.743 .
  11. ^ 11.0 11.1 Gross, J.L. and Yellen, J. Graph Theory and Its Applications, Second Edition. New York, USA: Chapman and Hall/CRC, Taylor & Francis. 2005 [2019-05-11]. ISBN 9781584885054. LCCN 2005052906. (原始内容存档于2021-01-24). 
  12. ^ Ghodasara, GV and Rokad, AH. Cordial Labeling in context of barycentric subdivision of special graphs (PDF). International Journal of Mathematics Research. 2013, 5 (5): pp. 475–483 [2019-05-11]. ISSN 0976-5840. (原始内容 (PDF)存档于2019-02-24).