細分 (圖論)

圖論中,細分(subdivision)或分割[2]是指在一個圖的其中一條邊加入新的頂點,使這條邊轉變成由多個頂點構成之路徑的變換,又稱為擴展(expansion)[3],為圖子式理論中的基本運算元之一,而變換完的像稱為細分圖[5]

細分也可以用於將無迴路英語Loop (graph theory)圖轉換成簡單圖[1]。上圖展示了使用重心細分偽圖(左)轉換為簡單圖(右)的一個例子。

在圖論的一般情況下,細分通常是指對邊的細分,而在一些領域中會有對面或其他結構的細分(如高維度的標記),例如重心細分英語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).