边收缩

✍ dations ◷ 2025-06-28 21:10:28 #图论

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

相关

  • 矿物矿物是指在地质作用下天然形成的结晶状纯净物(单质或化合物)。绝对的纯净物是不存在的,所以这里的纯净物是指物质化学成分相对单一的物质。矿物是组成岩石的基础(像石英、长石、
  • 瘴气瘴气,亦称瘴毒、瘴疠,中文中瘴气为中医名词,疾病地理学之概念,是指中国南方山林间湿热环境下因某种原因(如动植物腐败等)而产生的一种能致病的有毒气体。由瘴气引起的疾病被称为瘴
  • 灭火飞机空中消防是指运用飞机、直升机或其他航空设备,从空中扑灭火势的行动或技术,通常用于森林大火等大面积火灾。消防飞机搭载用专用的水槽,以盛装灭火剂或水,来源可以是地面装填或是
  • 伦敦西区剧院西区剧院(英语:West End theatre)是指位于英国伦敦西区的主流剧院,有时则是指在伦敦西区上演的戏剧。西区剧院与纽约百老汇剧院经常共同被看作是英语世界中最高水平的商业剧院代
  • Armillaria gallica异养腐生真菌高卢蜜环菌(学名:Armillaria gallica)是一种常见的蕈类,属于蜜环菌属,为生态上重要的腐生和寄生性真菌,可伺机性地腐蚀树木根茎。本种原产于北半球温带,包括欧洲、亚洲
  • 坠饰坠饰(古法语:pendant),亦作垂饰或吊坠,是指一种可以宽松的垂吊在身上的珠宝或首饰。它不一定是作项链般穿戴,现时一些造型夸张的耳环也会用上坠饰,尽管这么可能令耳朵感到很沉重。
  • 狂蝇科狂蝇科(学名:Oestridae),亦作肤蝇科,是家蝇下目有瓣类之下的一个科。肤蝇又名人肤蝇,是得名于其物种的幼虫会寄宿于哺乳动物皮肤上的寄生虫。当它把卵产在宿主身上后,孵出来的蛆会
  • 奥之细道奥之细道是日本俳谐师松尾芭蕉所著之纪行书。于元禄15年(1702年)印行,是松尾芭蕉的最有名的代表作。 书中记述松尾芭蕉与弟子河合曾良于元禄2年(1689年)从江户(东京)出发,游历东北、
  • M25狙击手武器系统XM25/M25是1980年代后期美国陆军特种部队—第10特种小队(10th Special Forces Group)与海军海豹部队以M14自动步枪为基础改进研制的。目前只有美国陆军特种部队—第10特种小队
  • 贵州省本表所列中华人民共和国城市按行政区类型分为直辖市、特别行政区、地级市(包括副省级市)和县级市。中国有很多城市。其中省会、首府用粗体字表明。15 副省级市10 省会城市5 计