树分解宽度如何分解算法

「爱情、让人受尽委屈。」 2022-09-04 05:46 240阅读 0赞

现实里面的road network是存在着width比较小的tree decomposition的。

*  节点对应城镇，
 *  边对应着城镇间的道路，
 *  边权对应着距离

在road network里面，一个重要的问题就是对于任意给定的两个节点 s 和 t  ，计算它们之间的最短距离 (shortest distance)。

这个问题可以用Dijkstra算法来计算，但在\[1\]中，作者给出了更好的解法：（ n表示图中节点的数量）

定理. 假设我们有关于road network G、width为 w、高度为 h 的一个树分解，那么存在一个大小为 O(n·h)的数据结构 S，使得我们能够在 O(w)时间内计算 G 中任意两个节点的最短距离。

在\[1\]中，作者对于美国的几个road network分别启发式地计算了一个次优（width不一定最小）的tree decomposition，得到的结果如下（第5和第6列）：

## 1. 定义 ##

为了方便讨论，因为题目没给，下面先给出tree decomposition和treewidth的定义。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyODgxOTA_size_16_color_FFFFFF_t_70][]

对于每个节点 v∈V，我们用

*  T(v)表示所有满足v∈Sz的树节点 z 所构成的子树
 *  X(v)表示 T(v) 的根节点。

例如，对于下面这个图，

![2bbb7533e4eb40b0c31739ee349e2730.png][]

存在一个树分解（图2）。

树中的每个节点记录着对应的 Sz。

可以验证这棵树满足定义中的3个条件。

此外，以 v13 为例子， T(v13）为图中黄色背景的那棵子树，X(v13)为这颗子树的根。

![dc702665a63c0a884f73e0205185d8ae.png][]

treewidth的定义与tree decomposition相关，如下：

![20210811154632732.png][]

求treewidth是一个NP-hard的问题。在\[1\]中，作者用Bodlaender的启发式算法，在多项式时间内对一个给定的road network，计算它的一个tree decomposition。对于图1中的图，图2即为该算法的结果。该算法得到的tree decomposition除了定义中的3个性质，还满足另外一个性质：

![20210811154737462.png][]

作者：知乎用户  
链接：https://www.zhihu.com/question/343030840/answer/833066097  
来源：知乎  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

视频

[https://www.youtube.com/watch?v=kEnDGTwSDXY][https_www.youtube.com_watch_v_kEnDGTwSDXY]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyODgxOTA_size_16_color_FFFFFF_t_70]: /images/20220829/fe83b493d2c44b7bb6f138ebff107d1e.png
[2bbb7533e4eb40b0c31739ee349e2730.png]: /images/20220829/b9fea74be8f6414c830d3e92752263ee.png
[dc702665a63c0a884f73e0205185d8ae.png]: /images/20220829/8fb3c2fd9fb249088df0dd278295e7d2.png
[20210811154632732.png]: /images/20220829/1a9277473fa3465d9b4145fb94130fb8.png
[20210811154737462.png]: /images/20220829/96dcd5efffa341949e63b73842493072.png
[https_www.youtube.com_watch_v_kEnDGTwSDXY]: https://www.youtube.com/watch?v=kEnDGTwSDXY