边收缩

✍ dations ◷ 2025-09-06 21:55:16 #图论

在图论中,边收缩是指将一个图的其中一个边移除,并将被移除边的两个顶点合并,同时保持与被移除边之顶点相连的其他顶点之连接关系的一种变换,为图子式理论中的基本算子之一,然而此种变换不一定是图论中的变换,亦可以作用于拓朴结构甚至是几何体,例如边收缩二十面体,即正二十面体经过一次边收缩变换后的像。另一种与边收缩类似的图论变换为点合并(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个三角形退化成边并与原有边重合因此被移除)和一个顶点。

相关

  • 氧化还原反应氧化还原反应(英语:Reduction-oxidation reaction,简称Redox)是在反应前后元素的氧化数具有相应的升降变化的化学反应。这种反应可以理解成由两个半反应构成,即氧化反应和还原反
  • 感受态细胞活化(Competence)又称为感受态,是一个在微生物学、遗传学、分子生物学和细胞生物学里很常见的名词,用来指一种能令细胞有能力从细胞以外的环境接纳DNA的方法。无论是在自然条件
  • 交尾交配是指的是生物的生殖细胞进行交换,导致受精和繁殖的活动。家畜之间的交配活动通常也可称为配种。昆虫、鸟类和卵胎生鱼类的交配活动可以称为交尾。雄性的精子会进入雌性体
  • 首字母缩略词首字母缩略字(英语:Acronym)是将相关词句的第一个字母缩写而组合成一个新字。 “首字母缩略字”又称为“头字语”。 而这个新字的发音则是依据这个新字书写的方式。例如“英语:l
  • 上党郡上党郡,是中国古代设立的一个郡级行政区划,其最广大时的范围,大致包括了今天的山西省长治市全境,晋城市大部,全境及晋中市东部的榆社县、和顺县、昔阳县、左权县(辽县)等地。上党的
  • 两亲分子两亲分子(英语:amphiphile)是一个描述一类同时具有亲水性以及亲脂性这两种性质的化合物的术语。这类物质被称为是“两亲性”的。这成为了众多化学与生物化学研究领域的理论基石
  • 体域网身体感测网络(英文:Body Area Network,缩写:BAN)是由可穿戴或可嵌入设备组成的网络。由于这些设备通过无线技术进行通信,所以体域网也叫无线体域网(WBAN)。体域网最新的国际标准是IE
  • 711年前9世纪 | 前8世纪 | 前7世纪前730年代 前720年代 | 前710年代 | 前700年代 前690年代前716年 前715年 前714年 前713年 前712年 | 前711年 | 前710年 前709年 前708年 前
  • 修道士修士(英语:friar,或fray),也称修道士、隐修士,是天主教以及东正教对于男性修行者的称呼,但并不属于神职人员。除了以担任神职人员为目标的一般修士之外,另有终身不做神父、专事修道
  • 即期券即期券是美国纸币的一种,发行于1861年8月至1862年4月美国南北战争期间,面额有5美元、10美元、20美元。即期券是美国发行的第一种纸币,在某种意义上,广泛流传到今天的一系列的货