边收缩

✍ dations ◷ 2025-07-21 13:58:35 #图论

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

相关

  • 萤光显微镜荧光显微镜是一种使用荧光或磷光物质的光学显微镜,或除此之外使用反射和吸收用于研究的有机或无机物质的特性。“荧光显微镜”是指使用荧光来产生一个图像的任何显微镜,无论是
  • 尘螨尘螨(学名:Dermatophagoides spp.)是一种8只脚的微小的蛛形纲节肢动物,长170-500微米,宽250-322微米,雌雄个体均为乳白色,肉眼是几乎看不到的,最喜欢生长在温暖潮湿的环境中,适合生长的
  • 艮部,为汉字索引中的部首之一,康熙字典214个部首中的第一百三十八个(六划的则为第二十一个)。就繁体和简体中文中,艮部归于六划部首。艮部只以右、下方为部字。且无其他部首可用
  • 加拿大公司加拿大公司是英国一家大型的特许私营土地开发公司,于1825年7月27日由英国议会批准成立,旨在协助接管上加拿大。加拿大公司通过提供更好的船只、更低的船费、各种工具以及廉价
  • 渥太华渥太华(英语:Ottawa)是加拿大的首都,全国第四大城市,面积2,779平方公里,位于安大略省东南部,渥太华河南岸,多伦多以东400公里,蒙特利尔以西190公里。在2011年人口统计中,渥太华城市有8
  • 塞斯纳172塞斯纳172型天鹰(Cessna 172 Skyhawk)是一个单引擎四座位的小型飞机,是受欢迎的教练机。1956年至今生产已超过42,500架。塞斯纳C-172是历史上最成功生产量最多的小型飞机。首架
  • 抚养未成年儿童家庭援助抚养未成年儿童家庭援助(Aid to Families with Dependent Children,简称AFDC)是1935年到1996年美国的一项联邦补助项目,由美国卫生及公共服务部所管理。该项目对于贫穷家庭的子
  • 乙醘辅酶A乙酰辅酶A(英语:acetyl-CoA)是激活了的乙酸,由乙酰基(CH3CO-)与辅酶A的巯基以高能的硫酯键相连。乙酰辅酶A是脂肪酸的β-氧化及糖酵解后产生的丙酮酸脱羧后的产物。在三羧酸循环的
  • 普查局美国普查局(英语:United States Census Bureau,按《美国法典第13卷 § 11》官方称呼为Bureau of the Census)是美国商务部经济和统计管理局下属的一个机关。它的任务由美国宪
  • 磷酸酯中毒磷酸酯中毒或有机磷中毒(英语:Organophosphate poisoning),指由磷酸酯(英文简称为 OP)所导致的中毒。磷酸酯可用于杀虫剂、药物及神经性毒剂。中毒症状有唾液及泪液分泌增加、腹泻