边收缩
在图论中，边收缩是指将一个图的其中一个边移除，并将被移除边的两个顶点合并，同时保持与被移除边之顶点相连的其他顶点之连接关系的一种变换，为图子式理论中的基本算子之一，然而此种变换不一定是图论中的变换，亦可以作用于拓朴结构甚至是几何体，例如边收缩二十面体，即正二十面体经过一次边收缩变换后的像。另一种与边收缩类似的图论变换为点合并（vertex contraction）是边收缩变换的一个广义形式。
定义[编辑]
边收缩是一种作用于边上的变换，因此其需作用于特定的边，令其计为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个三角形退化成边并与原有边重合因此被移除）和一个顶点。
 正二十面体 |
 边收缩二十面体 |
参见[编辑]
参考文献[编辑]
- ^ Gross, Jonathan; Yellen, Jay, Graph Theory and its applications, CRC Press, 1998, ISBN 0-8493-3982-0
- ^ Gross & Yellen 1998[1], p. 264
- ^ Rosen, Kenneth, Discrete Mathematics and Its Applications 7th, McGraw-Hill, 2011, ISBN 9780073383095
- ^ Rosen 2011[3], p. 664
- Oxley, James, Matroid Theory, Oxford University Press, 1992
- West, Douglas B., Introduction to Graph Theory 2nd, Prentice-Hall, 2001, ISBN 0-13-014400-2