细分 (图论)

✍ dations ◷ 2025-11-26 13:51:10 #图论

在图论中,细分(subdivision)或分割是指在一个图的其中一条边加入新的顶点,使这条边转变成由多个顶点构成之路径的变换,又称为扩展(expansion),为图子式理论中的基本算子之一,而变换完的像称为细分图。

在图论的一般情况下,细分通常是指对边的细分,而在一些领域中会有对面或其他结构的细分(如高维度的标记),例如重心细分(英语:Barycentric subdivision),有时会称为剖分及剖分图。

细分是一种作用于边上的变换,因此其需作用于特定的边,令其计为e,并令e所连接的两个顶点计为u和v,而细分会在顶点u和v之间加入一个新的顶点w,并使原本的边uv改成路径uwv则完成一次细分变换,换句话说,即先在uv边之间加入顶点w,移除uv边后将u和v连到w。

例如现在有一条边,计作,其由顶点和组成,计为{,}:

透过细分变换,产生了新的顶点w,将分割成两条边,分别计为12,皆连到新顶点w:

而细分变换存在逆变换,称为平滑(smoothing)变换。

细分变换的结果套用平滑变换会形成原像:

这两种变换的共通点是,其原像与变换像互为同胚。

更广义的,细分变换不一定只加入一个顶点,只要在边上有加入顶点的动作,都是一种细分,更精确地说,细分变换可以定义为将图G中的某一条边e替换为具有相同端点之路径,且构成该路径的顶点皆不在原本属于图G的顶点之中,且此路径也不会跟其他现有的顶点相连。

假设有二图G和H,若图H可以透过反复对图G套用细分变换而得,则图H可以称为图G的细分图。

扩展变换是指在一张图的某个边上,加入新的度为2之顶点,而产生的图可以称为原图的扩展。

当G'是G的细分时,则G'称为G的细分图,亦可以将G'称为G的扩展,计为TG,其中T表示扩展变换。G的原有的顶点若其位于细分作用的边上时,称为TG的分支顶点(branch vertex),在细分作用的边上加入之新的顶点称为TG的细分顶点(subdivision vertex),细分后产生的边称为细分边(subdivision edge),并且细分顶点具有度为2的特性。

细分的概念应用于图论,最早出现在1930年波兰数学家卡齐米日·库拉托夫斯基提出的一类禁用准则(指满足某种条件的图就一定无法具有某个性质)中,其所提出的库拉托夫斯基定理使用了细分图的概念。

细分可以用于几个与图论相关的证明和定理,例如判断两图是否同胚以及库拉托夫斯基定理中,对于简单图是否为平面图的准则,该定理为:如果一个简单图并不包含一个是 K5 或 K3,3 之细分图的子图,则该简单图是平面图,反之亦然,上述两条件为当且仅当关系。其中, K5 代表有 5 个点的完全图,K3,3 代表两部分各 3 个点的完全二分图,特别地,若一图的子图是K5或 K3,3之细分图,则该子图又称为库拉托夫斯基子图 。

此外,细分也可以用于将一般的图转换成简单图。

细分变换在图论中有一些不同的定义,例如重心细分(英语:Barycentric subdivision)在图论中就不是将多边形分割成三角形。

在图论中,重心细分(Barycentric subdivision)是指将图的所有边进行细分的变换,为一种特殊的细分变换,其变换的像总会是二分图,且是一个无回路(英语:Loop (graph theory))图,而任何无回路图的重心细分结果皆会是简单图。

重心细分可以被重复套用,任何图只要重复套用2次重心细分后结果总是简单图。

相关

  • 杨氏模量杨氏模量,也称杨氏模数(英语:Young's modulus),一般将杨氏模量习惯称为弹性模量,是材料力学中的名词。弹性材料承受正向应力时会产生正向应变,在形变量没有超过对应材料的一定弹性
  • 腋下腋窝(Axilla)是一个解剖构造,又称腋下、胳肢窝。腋窝位于肩关节下方,是描述躯干与手臂连接并接触的部位,腋窝内具有许多血管及神经经过,并具有许多汗腺。在人体中,腋臭最常发生于腋
  • 丙酮酸羧化酶结构 / ECOD丙酮酸羧化酶,属于连接酶类的酶,催化(根据不同的物种)丙酮酸的可逆羧基化,形成草酰乙酸。丙酮酸草酰乙酸EC 1.1/2/3/4/5/6/7/8/9/10/11/12/13/14/15/16/17/18/19/20/2
  • 冬季奥运冬季奥林匹克运动会,简称冬季奥运会、冬奥,每隔4年举行一届,赛事的主要特征是在冰上和雪地举行的冬季运动,如滑冰、滑雪等适合在冬季举行的项目。第一届冬季奥林匹克运动会于192
  • 紫堇属等。紫堇属(学名:Corydalis)是荷包牡丹科的一个属,共有300多个种,广泛分布于北温带和非洲南部地区。该属植物多含有生物碱,故而多又被当地居民用作草药者。紫堇属植物是一年或多年
  • 擦鞋童擦鞋工,因从前多数是童工担任而又名 擦鞋童、擦鞋仔,是替别人擦鞋为职业的人,生产工具是鞋油、鞋擦、干毛巾等。擦鞋可能是专门的,或者是补鞋业的附加服务。由于擦鞋员在工作时
  • 五帝之年五帝之年是指在公元193年时,罗马帝国在一年内出现了5位皇位的争夺者,他们分别是佩蒂纳克斯、尤利安努斯、奈哲尔、阿尔拜努斯和塞普蒂米乌斯·塞维鲁。192年最后一日,康茂德被
  • 滑铁卢车站滑铁卢站(英语:Waterloo station,/ˌwɔːtərˈluː/)是英国国营铁路公司的中央伦敦终点站(英语:London station group)之一,位于兰贝斯区的滑铁卢地区、邻近泰晤士河的南岸。此站
  • 莱昂纳尔·巴里摩尔1954年11月15日(1954-11-15)(76岁)美国加利福尼亚州洛杉矶Van Nuys赖尼尔·巴利摩(英语:Lionel Barrymore,1878年4月28日-1954年11月15日),美国演员,曾获得奥斯卡最佳男主角奖。赖尼尔
  • 大兵和平期间罕见军事强国有实力编制普通国家有实力编制士兵,最基层的军人,由高至低可分为:上等兵、一等兵、二等兵等。依照年资与表现晋升。普通国家的军队体制,军人分为军官、士官