边收缩

✍ dations ◷ 2025-09-19 11:12:38 #图论

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

相关

  • 研究机构研究中心,或称研究所、研究院、研究机构,是指以研究或研发为目的之设施、组织或机构。所做的研究通常都会聚焦于一个特定的领域。一个研究中心可能同时具有不同的学科或专业,同
  • α-鹅膏蕈碱α-鹅膏蕈碱(α-amanitin)是一种八氨基酸的环肽,它可能是毒伞肽中毒性最强的化合物。包括α-鹅膏蕈碱的毒伞肽类物质主要存在于鹅膏菌属的物种,例如毒鹅膏。α-鹅膏蕈碱的口服半
  • 洪灾洪水是一种自然灾害,指河流、湖泊、海洋所含的水体上涨,超过常规水位的水流现象。洪水常威胁沿河、湖滨、近海地区的安全,甚至造成淹没灾害。洪灾是因自然降水过量或排水不及时
  • 哈普托数哈普托数(英文:hapticity)是说明在配体中一群相连的原子如何和中心原子配位。配体的hapticity会用希腊字母η来表示,η上标的数字表示配体中有几个相连的原子和中心原子配位。一
  • 1,2-丙二醇1,2-丙二醇,也称作丙二醇,是一种有机化合物(二醇),其化学式为C3H8O2。丙二醇通常是略有甜味、无臭、无色透明的稠状液体。化学上,丙二醇属于二元醇的一种,可与水、丙酮及氯仿等多种
  • 浊口溪浊口溪,位于台湾南部,属于高屏溪水系,为荖浓溪第二大支流,河长55公里,流域面积529平方公里。水系最远源流为马里山溪,发源于卑南主山西侧,先向西南后转南流,与源自大鬼湖的山花奴奴
  • 简上仁简上仁(1948年3月5日-),是一位出生于台湾嘉义大林的民族音乐研究者。他长期致力于台湾本土音乐之采集、整理、创作及推展工作,于1983年成立“田园乐府”乐团并担任团长至今。1948
  • 尿液检验试纸尿液检验试纸(英语:Urine test strip)是一种基本的诊断工具,用于确定分析患者中尿液的病理学变化。
  • 士官士官,又称军士。一般国家的军队体制里,军人分为军官、士官及士兵三大体系,各有其任务执掌。大部分士官通常由士兵考试或选拔出来 也有经过专业士官军校兵科专属极为专业加上各
  • 黎东方黎东方(1907年-1998年12月30日),原名智廉,法文名Orient Lee,是一个中国历史学者。1907年出生于江苏省扬州府东台县(今盐城市东台市),祖籍河南汝宁府正阳县皮店人。父黎淦,清朝举人,仕于