边收缩

✍ dations ◷ 2025-10-09 16:20:02 #图论

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

相关

  • 倒睫睫毛倒刺(英语:Trichiasis)是医学上表明睫毛生长方向异常的术语,其症状表现为眼睫毛向眼球生长并接触到角膜或结膜。倒睫可能是由感染、炎症、免疫系统疾病、先天性缺陷(如眼睑发
  • 柴又称为薪,是一种燃料。一般先砍伐树木的主干或枝条,然后把它们劈成适合炉灶大小的条状木材,就是柴。柴是古人日常生活必需品、“开门七件事”“柴米油盐酱醋茶”中排首位;这里
  • 车前草车前草(学名:Plantago asiatica)为车前草科车前草属的物种,是一种多年生草本植物,又名蕮(音同“惜”)、车轮菜子、猪耳朵棵子、五更草、田灌草、牛舌草子、车轱辘草子,诗经中称之为
  • 逆伦命案逆伦命案又名伦常命案、逆伦惨案,逆伦是指违背伦常,杀害自己家族成员的事件,例如弑父母及杀夫、杀妻;谋害子女等。“杀”字无分尊卑,如“杀父”命案。但“弑”在汉语中,指杀害尊长
  • 嘉靖大地震嘉靖大地震,也称华县大地震,是中国明朝嘉靖三十四年腊月十二(1556年1月23日)发生的一次大型地震,震中位于陕西省华县,测算地震震级8.25级,陕西、山西、河南、甘肃等地的101个县受灾
  • 介错人介错是指在日本切腹仪式中为切腹自杀者斩首,以让切腹者更快死亡,免除痛苦折磨的行为过程。而执行介错过程者称为“介错人”。由于切腹过程太过痛苦,所以从早期的独自切腹演变成
  • 哈斯利峡谷哈斯利峡谷(英语:Hasley Canyon)是位于美国加利福尼亚州洛杉矶县的一个人口普查指定地区。哈斯利峡谷的座标为34°28′54″N 118°40′00″W / 34.48167°N 118.66667°W / 34.
  • 银河系列运载火箭银河系列运载火箭(韩语:은하, 銀河)是朝鲜研制的一次性运载火箭系列,是该国大浦洞2号火箭的卫星发射版本,银河2号于2009年4月5日首次发射,银河3号于2012年4月13日首次发射。并于同
  • 辽阳县辽阳县是辽宁省辽阳市下辖的一个县。下辖14个镇、1个乡、2个民族乡:
  • 淄博淄博市,简称淄,是中华人民共和国山东省下辖的地级市,国务院批准的较大的市,位于山东省中部。市境西临济南市,西南邻泰安市,南接临沂市,东毗潍坊市,北界滨州市、东营市。地处山东丘陵