树宽（Treewidth）

树宽是图论中的一个结构参数,用来刻画一个图与树的接近程度。它通过树分解来定义,树分解把图的顶点组织成若干个袋子并挂在一棵树上,树宽等于最小的最大袋子尺寸减一。

概述

树本身的树宽为一,循环的树宽为二,而完全图的树宽最大。当图的树宽较小时,它可以被一棵树良好地近似组织,这种类树结构使得原本困难的组合问题得以沿树自底向上地高效求解。

核心原理

• 树分解要求每个顶点至少出现在一个袋子里,每条边的两个端点同时出现在某个袋子里。
• 包含任一顶点的所有袋子在树上构成连通子树。
• 树宽是所有合法树分解中最大袋子大小减一的最小值。
• 库尔塞勒定理指出,任何可用一元二阶逻辑表达的图性质在树宽有界的图上都能线性时间判定。

应用场景

树宽是参数化算法设计的核心工具。以树宽为参数,顶点覆盖、独立集、着色、哈密顿回路等在一般图上NP难的问题都能通过袋子上的动态规划在多项式甚至线性时间内求解。它还应用于概率图模型的推断、约束满足求解和数据库查询优化,许多实际网络恰好具有较小的树宽,因而这一参数在工程中颇具实用价值。

常见问题

问:计算一个图的树宽容易吗?答:一般情况下判定树宽是否不超过给定值是NP难的,但当树宽本身有界时,存在以树宽为参数的固定参数可解算法能在线性时间内构造树分解。

问:为什么树宽小的图问题就变容易?答:小树宽意味着可以沿树分解做动态规划,每个袋子只涉及少量顶点,状态空间随树宽指数增长却与图规模无关,从而把全局难题拆成局部可控的小子问题。