边收缩

✍ dations ◷ 2025-06-08 09:28:09 #图论

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

相关

  • 焦炭焦炭是一种低杂质的高碳含量燃料,一般为煤炭破坏蒸馏(英语:Destructive distillation)或焦煤干馏后残存的固态产物。形态呈不规则块状,富含大小不等的气孔结构,质地坚硬,颜色为银灰
  • 电能电能(Electrical energy),是指电以各种形式做功(即产生能量)的能力。电能被广泛应用在动力、照明、冶金、化学、纺织、通信、广播等各个领域,是科学技术发展、国民经济飞跃的主要
  • 陈 旭陈旭(1936年9月17日-),中国古生物与地层学家。出生于江苏南京。籍贯浙江湖州。1959年毕业于北京地质学院。2003年当选为中国科学院院士。 中国科学院南京地质古生物研究所研究员
  • 威格夫威格夫(Khutawyre Wegaf或者Ugaf)是埃及第十二王朝的最后一位法老。Kim Ryholt认为Sekhemre Khutawy是阿蒙涅姆赫特四世之子,约公元前1802年——约公元前1786年在位。
  • cinchonine辛可宁(Cinchonine)是一种提取自正鸡纳树的生物碱。在有机化学中用于不对称合成,例如其衍生物作为不对称迈克尔加成的催化剂。辛可尼定(英语:cinchonidine)是其非对映异构体。
  • 小津安二郎小津安二郎(1903年12月12日-1963年12月12日),日本知名导演,生于东京都深川。1923年进入松竹映画的蒲田摄影所当摄影助理,在1927年正式升格为导演。早期他广泛的拍摄各类影片,其中又
  • 宫城事件宫城事件(日语:宮城事件/きゅうじょうじけん Kyūjō jiken */?)是二战末期发生在日本东京宫城(今皇居在1888年到1948年的通称)的一宗未遂军事政变。发生于日本投降前夕的1945年
  • 阿灵顿县阿灵顿县(Arlington County)是美国维吉尼亚州东北部的一个“县经理计划形式”或“密集城区”县,位于波托马克河西岸,哥伦比亚特区对岸。原来是特区的一部分,但美国国会在1846年7
  • 灰獴(H. edwardsii)灰獴(学名 Herpestes edwardsii) 也叫印度灰獴,是一种产于印度南部的獴。它们会爬树,主要生活在灌木林,有时也会出现在城市中。灰獴一般长约60厘米,小规模群居生活,有杀死毒蛇的本
  • 劳动价值理论劳动价值理论属于经济学中的商品经济理论范围,它起源于英国的亚当·斯密,中经英国的李嘉图及威廉·汤普逊的发展,终于德国的马克思。亚当·斯密之前的学者威廉·配第、约翰·洛