关于顶点对应的袋子子图均为路径的树分解的若干技术问题
关于顶点对应的袋子子图均为路径的树分解的若干技术问题
先给不熟悉的朋友快速梳理下基础概念:图$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
相关产品推荐
相关产品推荐

