边收缩

✍ dations ◷ 2025-12-08 17:07:31 #图论

在图论中,边收缩是指将一个图的其中一个边移除,并将被移除边的两个顶点合并,同时保持与被移除边之顶点相连的其他顶点之连接关系的一种变换,为图子式理论中的基本算子之一,然而此种变换不一定是图论中的变换,亦可以作用于拓朴结构甚至是几何体,例如边收缩二十面体,即正二十面体经过一次边收缩变换后的像。另一种与边收缩类似的图论变换为点合并(vertex contraction)是边收缩变换的一个广义形式。

边收缩是一种作用于边上的变换,因此其需作用于特定的边,令其计为e,并令e所连接的两个顶点计为u和v,而边收缩会使顶点u和v合并成一个新的顶点w,并使原本与u和v相连的所有边都连到w。通常一系列的边进行边收缩变换的先后顺序不会影响结果,换句话说即边收缩是一个具有交换律的变换。

边收缩变换有时会计为 G / e,类似于 G \ e,但 G \ e 指的是完全将e从G中移除。

根据下述的几个定义,边收缩可能会导致多重边的形成,也就是产生了有至少二个边的二个顶点完全相同、至少有二个顶点可以由二个边相连接的图,即使原本的图是一个简单图,也可能导致变换结果为伪图。

令G=(V,E)是一个图,亦可以是有向图或无向图,并令=(,)是图G中的其中一个边,且≠。 定义是一个图论变换函数,其可以将除了{,}外的所有顶点(V\{,})映射(或变换)到本身,其余情况则映射到新顶点。而针对的边收缩变换函数其变换后的像可以表示为:

其中V′为除了{,}外的所有顶点与{}的联集(V′=(V\{,})∪{})、E′为除了e之外的所有边(E′=E\{})。对所有的∈V,=()∈V′,若边∈E与相连则边∈E′与相连,反之亦然。

边收缩或点合并可以用于图论的数学归纳法,尤其是对于使用图之边或顶点个数的数学归纳法很有帮助,因为我们可以透过先假设某特性在所有较小的图皆成立,并透过将该特性推导到较大的图来证明。

点合并 (Vertex identification)是指将两个不一定落在同一条边上的顶点合并成一个顶点,并将原本与旧顶点相连的顶点改连接到这个合并而成的新顶点。

简化,又称为平滑(smoothing),是边收缩的一个特例,当边收缩选定的边其中一个顶点的度为2,则该变换又可称为简化(或平滑)。其逆变换称为细分。

当一个图套用平滑变换之后,其所产生的新图会与原图同胚。

当一个几何形状是具有点可递性质时,我们可以对该多面体进行边收缩变换,其变换结果至少会少一条边,且必定会少一个顶点,而面和边数量的变化则要看所选的边是哪一种多边形的边,例如三角形面会消失,若边重合则会再多减少一条边。例如正二十面体套用边收缩变换之后少掉了2个三角形面、少掉了3条边(2个三角形退化成边并与原有边重合因此被移除)和一个顶点。

相关

  • 萨摩亚面积以下资讯是以2012年估计国家领袖国内生产总值(购买力平价) 以下资讯是以2016年估计国内生产总值(国际汇率) 以下资讯是以2016年估计人类发展指数 以下资讯是以2018年估计萨
  • 个体发育个体发生学(英语:Ontogeny),或称做形态发生学,是描述一个生命体从受精卵到成体的起源和发育。个体发生学在发育生物学、发展心理学和发展生理学中被研究。更一般的用语,个体发生学
  • 海马回海马体(英语:Hippocampus),是人类及脊椎动物脑中的重要部分。目前在有海马体的动物身上发现的海马体皆成对出现,分别位于左右脑半球。它是组成大脑边缘系统的一部分,位于大脑皮质
  • 三萜类类萜(Terpenoid),是一大类存在于自然界中的有机化合物,属于萜烯的衍生物,有时也归于萜烯的范畴之下。萜类化合物大多由一个或多个异戊二烯单元头尾相连组成,可能为链状,也可能为环
  • 电弱时期电弱时期是宇宙早期演化中的时期,在物理宇宙学中宇宙的温度不够高到能让电磁和弱交互作用合并成单一的电弱交互作用( > 100 GeV)。电弱时期大约开始于大爆炸之后的10-36秒 ,当
  • 大正藏《大正新脩大藏经》(简称大正藏)是大藏经的一个版本。日本大正13年(1924年),高楠顺次郎和渡边海旭组织大正一切经刊行会,小野玄妙等人负责编辑校勘,于1934年印行完成。大正藏是目前
  • 洛洛洛洛国家森林(英语:Lolo National Forest)是美国蒙大拿州西部的一座国家森林,西接爱达荷州边界。该森林面积2 × 106英亩(8,100平方千米),内有四处原野区域。该森林在1906年建立,当
  • 佳里兴震兴宫坐标:23°11′27″N 120°11′19″E / 23.1908706°N 120.1885515°E / 23.1908706; 120.1885515佳里兴震兴宫,初名清水宫,位于台湾台南市佳里区佳里兴,主祀清水祖师、雷府大将
  • Google+Google+(Google Plus,简称:G+或GPlus)是Google公司推出的社交网站与身份服务;除社交网站身份外,Google也将Google+视为其旗下众多服务之间社交层面的补强,与传统社交网站仅能登录单
  • 青岛-石家庄308国道(或“国道308线”、“G308线”)是在中国的一条国道,起点为山东省威海市文登区,终点为石家庄的国道,全程637千米。在国家公路网规划(2013年-2030年)中,起点由原青岛市改为文登