You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于顶点对应的袋子子图均为路径的树分解的若干技术问题

关于顶点对应的袋子子图均为路径的树分解的若干技术问题

先给不熟悉的朋友快速梳理下基础概念:图$G$的树分解是一棵树$T$,$T$里的每个顶点被称为「袋子」,每个袋子会包含$G$的若干顶点,同时必须满足三个核心性质:

  • $G$的每个顶点都至少出现在$T$的一个袋子中;
  • $G$的每条边$vw$,至少存在一个袋子同时包含顶点$v$和$w$;
  • 对于$G$的任意顶点$v$,所有包含$v$的袋子在$T$中构成的子图是连通的。

树分解衍生出一个非常实用的图参数——树宽,它的定义是:在所有可能的树分解中,最大袋子的顶点数的最小值。

我的核心疑问是给树分解加一个额外限制:正常情况下,每个顶点对应的袋子子图(也就是$T$中包含该顶点的所有袋子构成的子图)必然是树(因为连通且$T$本身是树),但如果要求所有顶点对应的袋子子图都必须是路径,我有三个具体问题:

  • 是否存在一些图,根本不存在满足这个限制的树分解?
  • 对于存在这类分解的图,这种受限分解下的最小最大袋子大小(类似树宽的参数),会不会严格大于原图的正常树宽?
  • 这种树分解的子类型有没有专门的名称?有没有学者对它做过研究?

目前收到的一个初步回答:

No, throw everything into the same bag.

备注:内容来源于stack exchange,提问作者V. Jackson

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.22 08:28:01