边收缩

在图论中，边收缩是指將一個圖的其中一個邊移除，並將被移除邊的兩個頂點合併，同時保持與被移除邊之頂點相連的其他頂點之連接關係的一種變換，為圖子式理論中的基本運算元之一，然而此種變換不一定是圖論中的變換，亦可以作用於拓樸結構甚至是幾何體，例如邊收縮二十面體，即正二十面體經過一次邊收縮變換後的像。另一種與邊收縮類似的圖論變換為點合併（vertex contraction）是邊收縮變換的一個廣義形式。

對於邊uv的邊收縮（G / {uv}）示意圖。

定义

邊收縮是一種作用於邊上的變換，因此其需作用於特定的邊，令其計為e，並令e所連接的兩個頂點計為u和v，而邊收縮會使頂點u和v合併成一個新的頂點w，並使原本與u和v相連的所有邊都連到w。通常一系列的邊進行邊收縮變換的先後順序不會影響結果，換句話說即邊收縮是一個具有交換律的變換^[2]。

邊收縮變換有時會計為 G / e，類似於 G \ e，但 G \ e 指的是完全將e從G中移除。

 

不產生多重邊的邊收縮演算法。

根據下述的幾個定義，邊收縮可能會導致多重邊的形成，也就是產生了有至少二個邊的二個頂點完全相同、至少有二個頂點可以由二個邊相連接的圖，即使原本的圖是一個簡單圖，也可能導致變換結果為伪图^[4]。

正式定義

令G=(V,E)是一個圖，亦可以是有向圖或無向圖，並令e=(u,v)是圖G中的其中一個邊，且u≠v。 定義f是一個圖論變換函數，其可以將除了{u,v}外的所有頂點（V\{u,v}）映射（或變換）到本身，其餘情況則映射到新頂點w。而針對e的邊收縮變換函數其變換後的像可以表示為：

G′=(V′,E′)

其中V′為除了{u,v}外的所有頂點與{w}的聯集（V′=(V\{u,v})∪{w}）、E′為除了e之外的所有邊（E′=E\{e}）。對所有的x∈V，x′=f(x)∈V′，若邊e∈E與x相連則邊e′∈E′與x′相連，反之亦然。

用途

邊收縮或點合併可以用於圖論的數學歸納法，尤其是對於使用圖之邊或頂點個數的數學歸納法很有幫助，因為我們可以透過先假設某特性在所有較小的圖皆成立，並透過將該特性推導到較大的圖來證明。

相關變換

點合併

點合併 （Vertex identification）是指將兩個不一定落在同一條邊上的頂點合併成一個頂點，並將原本與舊頂點相連的頂點改連接到這個合併而成的新頂點。

簡化

簡化，又稱為平滑（smoothing），是邊收縮的一個特例，當邊收縮選定的邊其中一個頂點的度為2，則該變換又可稱為簡化（或平滑）。其逆變換稱為細分。

當一個圖套用平滑變換之後，其所產生的新圖會與原圖同胚。

幾何形狀的邊收縮

當一個幾何形狀是具有點可遞性質時，我們可以對該多面體進行邊收縮變換，其變換結果至少會少一條邊，且必定會少一個頂點，而面和邊數量的變化則要看所選的邊是哪一種多邊形的邊，例如三角形面會消失，若邊重合則會再多減少一條邊。例如正二十面體套用邊收縮變換之後少掉了2個三角形面、少掉了3條邊（2個三角形退化成邊並與原有邊重合因此被移除）和一個頂點。

正二十面體

邊收縮二十面體

参见

• 细分 (图论)

參考文獻

1. Gross, Jonathan; Yellen, Jay, Graph Theory and its applications, CRC Press, 1998, ISBN 0-8493-3982-0 
2. Gross & Yellen 1998^[1], p. 264
3. Rosen, Kenneth, Discrete Mathematics and Its Applications 7th, McGraw-Hill, 2011, ISBN 9780073383095 
4. Rosen 2011^[3], p. 664

1. Oxley, James, Matroid Theory, Oxford University Press, 1992 
2. West, Douglas B., Introduction to Graph Theory 2nd, Prentice-Hall, 2001, ISBN 0-13-014400-2 

外部链接

• 埃里克·韦斯坦因. Edge Contraction. MathWorld.