边收缩

✍ dations ◷ 2025-11-07 08:19:31 #图论

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

相关

  • 人类偏肺病毒人类偏肺病毒(hMPV)是副黏液病毒科下的一种单链核糖核酸病毒,于2001年在荷兰被首度发现。病毒主要令儿童受急性呼吸道感染,病征包括发烧、咳嗽、气促及呼吸困难等。抵抗力弱的成
  • 工业工程学工业工程(Industrial Engineering)、运筹学(Operations Research)和系统工程(Systems Engineering)是研究如何分析复杂系统并建立抽象模型从而改进系统的学科。与传统工程学及数理
  • 美国物理学会美国物理学会(英语:American Physical Society,APS)成立于1899年,是世界最大的物理学组织,发表十余种科学期刊,每年举办20多项科学会议,约有四万多会员。该学会亦是美国物理协会成员
  • 伍斯特市伍斯特(英语:Worcester/ˈwʊstər/ WUUSS-tər,本地/ˈwᵻstə/ WISS-tə)位于美国马萨诸塞州中部,是伍斯特县的县治所在,人口约18万(2010年),是新英格兰地区第二大城市,仅次于波士顿
  • 城市蔓延城市蔓延(英语:Urban sprawl),或称郊区蔓延(Suburban sprawl),俗称摊大饼,是指郊区城市化过程中,城市人口大幅向外发展,侵占城市边缘的乡郊地区并形成低密度、单功能,且通常依赖小汽车
  • 大麻成瘾大麻使用障碍(英语:Cannabis use disorder,缩写CUD),又称大麻依赖或大麻成瘾、大麻上瘾、大麻瘾,是指因吸食大麻或使用大麻的主要精神活性物质四氢大麻酚(THC)所产生的以心理依赖(意
  • 系统性风险系统性风险(Systematic risk),又称市场风险或不可分散风险,是影响所有资产的、不能通过资产组合而消除的风险。这部分风险是由那些影响整个市场的风险所引起的,例如:战争、政权更
  • 祖乙祖乙(?-?),又称且乙(“且”是“祖”的本字,实为同一字),姓子,名滕(一作胜),中国商朝第十四任君主,《史记·殷本纪》称他为河亶甲之子,但甲骨文记载他是仲丁之子。他在位时商朝再度兴盛。《太
  • 甲型肝炎疫苗甲型肝炎疫苗是用于预防甲型肝炎的疫苗。 对95%的人都会有效,且能持续至少15年以上的效期,很多人甚至能持续一生。幼儿应接种 2 剂,于出生满 12-15 个月接种第 1 剂,间隔 6 个月
  • 2019冠状病毒病斯洛文尼亚疫情1月1月2月2月3月3月4月4月过去15日过去15日2019冠状病毒病斯洛文尼亚疫情,介绍在2019新型冠状病毒疫情中,在斯洛文尼亚发生的情况。2020年3月4日,斯洛文尼亚确诊首例新冠肺炎病