边收缩

✍ dations ◷ 2025-04-25 05:39:53 #图论

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

相关

  • 酒精搓手液酒精搓手液,又名搓手液、免冲水洗手液、免洗洗手液等,是一种用作洗手的液体。酒精搓手液的主要成分为酒精,用作杀菌。由于酒精搓手液无需用水冲洗,所以可以用于外出时清洁双手之
  • 核裂变核裂变(德语:Kernspaltung;英语:nuclear fission),在港台称作核分裂,是指由较重的(原子序数较大的)原子,主要是指铀或钚,裂变成较轻的(原子序数较小的)原子的一种核反应或放射性衰变形式
  • 南部联邦管区南部联邦管区(俄语:Южный федеральный округ,罗马化:Yuzhny federalny okrug)位于俄罗斯西南部,是目前俄罗斯的联邦管区之一。介乎格鲁吉亚、乌克兰和哈萨克
  • 单因谬误单因谬误(fallacy of the single cause),是一种非形式谬误,系认定某事由一个单独原因造成,而未考虑可能是由许多原因共同导致,即复合原因(complex cause)。考试成绩差除了可能天天玩
  • Chicory菊苣(学名:Cichorium intybus),又称苦苣、苦菜,是一种灌木丛生的多年生草本植物,长出蓝色或薰衣草色的小花。原生于欧洲,但现时已自然生长于北美等地而成为路边物种。经烘焙及磨碎
  • 年轮年轮又称生长轮。年轮指的是树木由于周期性季节生长速度不同,而在木质部横切面上形成肉眼可分辨的层层同心轮状结构。当我们把树干打横锯开,露出一个横切面,会看到面上满布一个
  • 赞颂赞颂(英语:praise)是一种表达对某人的认可的社交互动。在操作制约中,这个可以是正向增强,用来令目标增加更多想要的行为。在学校理境中,老师用称赞方法可以提升学生的学业表现。这
  • 一加一加(全称:深圳市万普拉斯科技有限公司,英语:OnePlus)是中国一家移动通信终端设备研制与软件开发的企业,于2013年12月7日由刘作虎和裴宇主导成立,其产品于全球多国市场销售。2013年
  • 伊瑟阔伊瑟阔(Issaquah) (发音: /ˈɪsəkwɑː/ 美国字典发音: ĭs′·ə·kwâ)位于美国华盛顿州金郡。2010年美国人口普查时人口为30,434人。根据华盛顿州地区人均所得伊瑟阔在522
  • 光明节灯台光明节灯台(希伯来语:.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram Tsova","Taam