边收缩

✍ dations ◷ 2025-02-01 15:49:05 #图论

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

相关

  • 危险因子风险因子(Risk Factor),在流行病学中是与疾病或感染风险增加相关的变量。风险因子或决是因数是相关的,由相关不蕴涵因果可知,它们不一定是因果关系。例如,“年轻不能说是引起麻疹
  • 伦敦大瘟疫伦敦大瘟疫是一场1665年至1666年间发生在英国的大规模传染病爆发,超过10万人死于这次瘟疫之中,足足相当于当时伦敦人口的五分之一。该次的疾病后来被确认为是淋巴腺鼠疫,一种由
  • 拉尼尔县拉尼尔县(Lanier County, Georgia)是美国乔治亚州南部的一个县。面积518方公里。根据美国2000年人口普查,共有人口7,241人。县治莱克兰 (Lakeland)。成立于1919年8月11日。县名
  • 油电混合公车混合动力车辆是使用两种或以上能量来源驱动的车辆,而驱动系统可以有一套或多套。常用的能量来源有燃油、电池、燃料电池、太阳能电池、压缩气体等,而常用的驱动系统包含内燃机
  • 皮层大脑皮质(英语:cerebral cortex),又称为大脑灰质,或简称为皮质或皮层,是大脑的一个解剖结构。大脑皮层是端脑的一部分,属于脑和整个神经系统演化史上最为晚出现、功能上最为高阶的
  • span class=nowrapAc(NOsub3/sub)sub3/sub/span硝酸锕是一种无机化合物,化学式为Ac(NO3)3,有放射性。硝酸锕可通过氢氧化锕和硝酸的中和反应得到:
  • 库页岛朝鲜人库页岛朝鲜族(俄语:Сахали́нские коре́йцы;韩语:사할린 한인)多是日韩合并后至三十年代被日本三井招募至库页岛桦太厅当劳工的朝鲜族。他们多数来自全罗道与
  • 第二次刚果战争第二次刚果战争,是主要发生在刚果民主共和国境内的一场战争。在第一次刚果战争中被卢旺达扶植上台的卡比拉对迟迟不肯撤离的卢旺达驻军渐生猜忌,在试图强制其撤出后,卢旺达势力
  • 坑梓街道坑梓街道是中国广东省深圳市坪山区下辖的街道,西和南接龙田街道、东及北接惠州市惠阳区秋长街道,面积 24.07 平方公里,常住总人口约 9.1 万人,实际管理人口约 13.63 万人,其中户
  • 天津中医药大学中国老校区:天津市南开区鞍山西道312号/玉泉路88号 新校区:天津中医药大学始建于1958年,原名天津中医学院,2006年正式更名为天津中医药大学。1992年经国家教委批准,