边收缩

✍ dations ◷ 2025-11-21 09:17:27 #图论

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

相关

  • 肠吸虫布氏姜片虫(学名:Fasciolopsis buski),简称姜片虫,是一种外观极像薄切姜片的中、大型寄生虫。为完成一代生活,这种虫必须在环境适当的淡水螺体内发育,再以常见的水生植物作第二轮的
  • 罂粟碱罂粟碱(英语:Papaverine)是一种鸦片生物碱解痉药,主要用于治疗内脏痉挛、血管痉挛(特别是涉及到心脏与大脑的血管)并间或用于勃起功能障碍。尽管它存在于罂粟之中,罂粟碱在结构与药
  • 百年理工学院百年理工学院(英语:Centennial College of Applied Arts and Technology)是加拿大安大略省历史最悠久的公立大专院校,在该省多伦多市设有四座校园,主要服务大多伦多地区东部的居
  • Canadian Space Agency加拿大航天局(英语:Canadian Space Agency,CSA,法语:Agence spatiale canadienne,ASC)该组织是由加拿大工业部管理,成立于1989年,总部在魁北克省蒙特利尔。组织的目标是成为开发和利
  • 下奥地利下奥地利(德语:Niederösterreich)是奥地利面积最大的州(19,174平方公里),人口仅次于维也纳州(1,545,804)。其与上奥地利、维也纳州组成奥地利的历史核心地区。首府自1986年经公民表
  • 舞虻科舞虻,又名舞蝇,是舞虻科(Empididae)的昆虫,已发现超过3000种,大部分分布在全北区。它们主要是掠食性的,有多种不同的形态,一般都是细小至中等身型的,非金属色及有刚毛的。一些舞虻,如
  • 卢人语卢人语是贵州省的一种绝迹的汉藏语。卢人语可能于20世纪60年代灭绝。卢人语同蔡家话和龙家语有极近的亲缘关系。然而,这三种语言在汉藏语系中的具体分类仍不确定。郑张尚芳(20
  • 潮州府潮州府,明朝时设置的府,清朝沿用。府城东有广济桥。明朝洪武二年(1369年)改潮州路为府,属广东行省,治所在海阳县(县城、府治属潮州市湘桥区),辖程乡、海阳、揭阳、潮阳四县,范围大约等
  • 争取安哥拉彻底独立全国联盟争取安哥拉彻底独立全国联盟(葡萄牙语:União Nacional Para a Independência Total de Angola),简称安盟(UNITA),安哥拉主要政党之一。安盟成立于1966年3月,主要创始人为若纳斯·
  • CD8受体CD8受体(英语:CD8-receptor)是细胞毒性T细胞的膜上标记(surface marker)之一。当病菌入侵人体,有一部分必定会被广布的抗原呈现细胞(此时主要指非B细胞的巨噬细胞及棘状细胞)给吞噬