边收缩

✍ dations ◷ 2025-12-07 03:28:50 #图论

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

相关

  • 开放经济开放式经济,在经济学意指在经济体中除自我内部的交易外,尚可与其他的经济体进行交易的经济体,与之相对的则是封闭式经济,两者皆属于是经济学中定义经济体行为的概念。开放式经济
  • 芳香烃芳香.mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ruby.large{font-size:250%}.mw-parser-output ruby.larger
  • 血红蛋白S镰刀型红血球疾病(英语:Sickle-cell disease, SCD)是一组通常由双亲遗传而来的血液疾病。其中最常见的一种类型,叫做镰状红血球贫血症(Sickle-cell anemia, SCA)。该疾病会引起红
  • 亚属亚属(拉丁语:subgenera;英语:subgenus)是生物分类法中的一级,位于属和种之间。在分类学中,“亚属”可单独使用或与种名同时使用。但亚属的使用并非必要。
  • CBe有机铍化学是研究含有铍-碳键的化学分支。有机铍化合物中,铍都以+2价的形式出现。有机铍化合物具有很高的毒性,对空气和水敏感。二烃基铍是有机铍化合物的一种,可由格氏试剂或
  • 丹麦-挪威联合丹麦-挪威联合王国(丹麦文/瑞典文:Danmark-Norge),存在于1524年-1814年的北欧国家,由卡尔马联合(1397年-1523年)演变而来。1523年瑞典王国独立后,挪威继续与丹麦联合。此后数百年间,丹麦
  • 西摩岛坐标:64°14′S 56°37′W / 64.233°S 56.617°W / -64.233; -56.617西摩岛(英语:Seymour Island)是南极洲的岛屿,位于南极半岛西北面的威德尔海,长19.2公里、宽8.8公里,面积100平
  • 浆果鹃属浆果鹃属(学名:Arbutus),杜鹃花科植物,阔叶常绿灌木或乔木,至少包括14个品种,源于地中海、西欧及北美的温带地区。叶子互生,有柄;花白色或粉红色,花穗疏散,生于枝顶;果实为浆果,红色或橙
  • 台湾鸟类列表台湾在世界动物地理分区上属于东洋区和旧北区的交会地带,有87科653种鸟类曾被记录,其中有29种为台湾特有种。台澎地区和金马地区的鸟类生态有相当程度的差异,请另见金门鸟类列
  • 银鱼科银鱼科(学名:Salangidae)通称银鱼,古称脍残鱼,属辐鳍鱼纲胡瓜鱼目。以小型甲壳类为食。银鱼可供鲜食用或晒鱼干。银鱼是一种小型鱼类,身体细长、光滑、半透明,头平扁;口大,两颌和口盖