边收缩

✍ dations ◷ 2025-12-02 22:48:55 #图论

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

相关

  • 自然自然(英文:Nature),是指不断运行演化的宇宙万物,包括生物界和非生物界两个相辅相成的体系。人类所能理解地自然现象有:生物界的基因模因、共识主动、意识行为、社会活动和生态系统
  • 迷迭香迷迭香(学名:Rosmarinus officinalis)是一种原产于地中海盆地,木本多年生香料植物,野生或种植于白垩土壤中。茎、叶和花都可提取芳香油。多年生常绿小灌木。迷迭香的品种依植株的
  • 米约高架桥米约高架桥(法语:le Viaduc de Millau,国际音标发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Co
  • 阿尔布雷希特·丢勒阿尔布雷希特·丢勒(德语:Albrecht Dürer,1471年5月21日-1528年4月6日)德国中世纪末期、文艺复兴时期著名的油画家、版画家、雕塑家及艺术理论家。他在二十多岁时高水准的木刻版
  • 索布语索布语(serbšćina),又称文德语(Wendisch),是德国东南部少数民族索布人的语言。属于斯拉夫语族。分为两个方言群:上索布语,约55,000人,多居住于德国萨克森州;下索布语,使用者约14,000
  • PDGF血小板衍生生长因子受体(Platelet-derived growth factor receptors,PDGF-R)为血小板衍生生长因子(PDGF)蛋白质家族的受体,位于细胞膜表面,属于酪胺酸激酶受体(英语:receptor tyrosin
  • 三合泥三合泥是一种甜食类小吃,流行于川西地区。其主要原料包括三种:糯米、黑豆、芝麻,而成品为泥状,由此得名三合泥。其特点为酥香油润、味甜不腻。三合泥的制作是将三种主料入沸水中
  • 刘兰芳刘兰芳(1944年1月11日-),辽宁辽阳人,满族,中国评书表演艺术家,曾任中国文联副主席、中国曲艺家协会主席。刘14岁开始学习西河大鼓,次年加入鞍山市曲艺团,1972年开始在电台中播报评书,1
  • 莱昂纳尔·巴里摩尔1954年11月15日(1954-11-15)(76岁)美国加利福尼亚州洛杉矶Van Nuys赖尼尔·巴利摩(英语:Lionel Barrymore,1878年4月28日-1954年11月15日),美国演员,曾获得奥斯卡最佳男主角奖。赖尼尔
  • 十里望镇十里望镇,是中华人民共和国山东省德州市禹城市下辖的一个乡镇级行政单位。十里望镇下辖以下地区:殷曲社区、粉王社区、牛徐社区、十里望社区、宋家河套社区、王楼社区、店张社