{{Double image|right|Digon_graph.svg|150|Circle graph C4.svg|150|細分也可以用於將無圖轉換成簡單圖，為圖子式理論中的基本運算元之一，而變換完的像稱為細分圖。
在圖論的一般情況下，細分通常是指對邊的細分，而在一些領域中會有對面或其他結構的細分（如高維度的標記），例如，有時會稱為剖分及剖分圖。
定義
細分
細分是一種作用於邊上的變換，因此其需作用於特定的邊，令其記為e，並令e所連接的兩個頂點記為u和v，而細分會在頂點u和v之間加入一個新的頂點w，並使原本的邊uv改成路徑uwv則完成一次細分變換，換句話說，即先在uv邊之間加入頂點w，移除uv邊後將u和v連到w，並且細分頂點具有度為2的特性。
歷史
細分的概念應用於圖論，最早出現在1930年波蘭數學家卡齐米日·库拉托夫斯基提出的一類禁用準則（指滿足某種條件的圖就一定無法具有某個性質）中，其所提出的庫拉托夫斯基定理使用了細分圖的概念。其中， K5 代表有 5 個點的完全圖，K3,3 代表兩部分各 3 個點的完全二分圖，特別地，若一圖的子圖是K5或 K3,3之細分圖，則該子圖又稱為库拉托夫斯基子圖 。
此外，細分也可以用於將一般的圖轉換成简单图，為一種特殊的細分變換，其變換的像總會是二分图，且是一個無圖，而任何無迴路圖的重心細分結果皆會是簡單圖。
重心細分可以被重複套用，任何圖只要重複套用2次重心細分後結果總是簡單圖。
参见
- 同胚 (圖論)
- 图子式
- 边收缩
參考文獻
#
评论 (0)