Loading AI tools
来自维基百科，自由的百科全书
在圖論中，細分（subdivision）或分割[2]是指在一個圖的其中一條邊加入新的頂點，使這條邊轉變成由多個頂點構成之路徑的變換，又稱為擴展（expansion）[3]，為圖子式理論中的基本運算元之一，而變換完的像稱為細分圖[5]。
在圖論的一般情況下，細分通常是指對邊的細分，而在一些領域中會有對面或其他結構的細分（如高維度的標記），例如重心細分[6]，有時會稱為剖分及剖分圖。
細分是一種作用於邊上的變換，因此其需作用於特定的邊，令其記為e，並令e所連接的兩個頂點記為u和v，而細分會在頂點u和v之間加入一個新的頂點w，並使原本的邊uv改成路徑uwv則完成一次細分變換，換句話說，即先在uv邊之間加入頂點w，移除uv邊後將u和v連到w[5]。
例如現在有一條邊，記作e，其由頂點u和v組成，記為{u,v}：
|
透過細分變換，產生了新的頂點w，將e分割成兩條邊，分別記為e1和e2，皆連到新頂點w：
|
而細分變換存在逆變換，稱為平滑（smoothing）變換。
|
|
細分變換的結果套用平滑變換會形成原像：
|
|
更廣義的，細分變換不一定只加入一個頂點，只要在邊上有加入頂點的動作，都是一種細分，更精確地說，細分變換可以定義為將圖G中的某一條邊e替換為具有相同端點之路徑，且構成該路徑的頂點皆不在原本屬於圖G的頂點之中，且此路徑也不會跟其他現有的頂點相連[7]。
假設有二圖G和H，若圖H可以透過反覆對圖G套用細分變換而得，則圖H可以稱為圖G的細分圖[5]。
當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] 。
細分變換在圖論中有一些不同的定義，例如重心細分在圖論中就不是將多邊形分割成三角形。
在圖論中，重心細分（Barycentric subdivision）是指將圖的所有邊進行細分的變換[11]，為一種特殊的細分變換，其變換的像總會是二分图[12]，且是一個無迴路圖[1]，而任何無迴路圖的重心細分結果皆會是簡單圖[1]。
重心細分可以被重複套用，任何圖只要重複套用2次重心細分後結果總是簡單圖[11]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
