图的弦分解与弦宽 弦分解与弦宽是图论中描述图结构、衡量其“树相似性”的重要工具。它们与树宽概念紧密相关，但侧重于不同的分解方式。我将从基础概念开始，循序渐进地解释。 第一步：从树宽到弦分解的动机 您已了解“树的树分解”：将图分解为一系列顶点子集（称为袋子），并组织成树形结构，要求每条边和每个连通分量在袋子中体现良好性质。树的宽度定义为最大的袋子大小减1。寻找树宽较小的树分解对许多NP难问题有多项式时间算法至关重要。树的弦分解是另一种分解范式，它不直接使用树结构，而是利用图的“弦补”来定义宽度，这为研究图的结构和算法提供了另一种等价的视角。 第二步：弦、弦图和弦补图 这是理解弦分解的基础。 弦 ：在一个环（长度至少为4的简单环）中，连接环上两个非连续顶点的边称为弦。 弦图 ：如果一个图中，每个长度至少为4的环都含有一条弦，则该图称为弦图。弦图也被称为三角化图。树是弦图的一个简单例子。 弦补图 ：对于任意一个图G，可以通过添加边使其变成一个弦图。将边添加到G，使得得到的图H是一个弦图，且H是在此意义下的最小弦图（即任何H的真子图不再是弦图），则称H是G的一个弦补图。一个图的弦补图可能不唯一。 第三步：弦分解的正式定义 图的弦分解由两个要素构成： 弦补 ：首先，为原图G构造一个弦补图H。这意味着H包含G的所有顶点和边，并可能添加了一些新边（“弦”），使得H成为弦图。 最大团树 ：对于弦图H，存在一个非常好的性质：它可以表示为一棵树T，T的每个节点对应H的一个极大团，并且对于H中的每个顶点v，包含v的极大团在T中诱导出一个连通子树。这棵树T称为H（也是G）的一个团树或极大团树。 这个二元组 (H, T) 就构成了原图G的一个 弦分解 。其中，T是分解树，T的每个节点（对应H的一个极大团）可以看作是分解中的一个“袋子”。 第四步：弦宽的定义 对于一个弦分解 (H, T)： 分解的 宽度 定义为T中所有节点（即H的所有极大团）所包含的顶点数的最大值减1。即 width = max{|C| : C 是 H 的极大团} - 1。 图G的 弦宽 定义为所有可能的弦分解中最小的宽度，记作 cw(G)。 直观上，弦宽衡量了将图“铺开”成树状结构时，任意一个“片段”（极大团）中最多需要同时处理多少个顶点。弦宽越小，图的结构越接近树。 第五步：弦宽与树宽的等价关系 这是一个关键定理：对于任意图G，其弦宽 cw(G) 等于其树宽 tw(G)。 从弦分解得到树分解 ：给定一个弦分解 (H, T)，其中T的节点对应极大团Ci。那么，简单地以T为树，以Ci为袋子，就构成了G的一个树分解。宽度满足 tw(G) ≤ cw(G)。 从树分解得到弦分解 ：给定G的一个树分解，可以按照特定规则（通常是通过考虑树分解的节点排序，并模拟顶点消除过程）添加边，构造一个弦补图H，并为H找到一个团树T，使得其宽度不大于原树分解的宽度。这证明 cw(G) ≤ tw(G)。 因此，弦宽和树宽是同一个图参数的不同定义方式。弦分解的视角更代数化/组合化，而树分解的视角更结构化/分解化。 第六步：计算弦宽与寻找弦分解 由于弦宽等于树宽： 精确计算图的弦宽（树宽）是NP难的。 对于固定整数k，判断 cw(G) ≤ k 是可以在线性时间内解决的（存在线性时间固定参数可解算法）。这类算法通常基于寻找一个“安全”的顶点消除序（完美消除序的推广），或直接搜索树分解。 在实践中，常使用启发式或近似算法来为大型图寻找宽度较小的树分解/弦分解。 第七步：弦分解的应用 弦分解（等价于树分解）的主要应用是为树宽有界的图设计高效算法（通常为固定参数可解算法）： 动态规划 ：在分解树T上进行动态规划是标准方法。由于每个袋子的宽度小（顶点数有限），可以对袋子内顶点所有可能的状态组合（如着色、选择与否等）进行枚举和转移。图的许多NP难问题（如独立集、顶点覆盖、染色、哈密顿回路等）在树宽有界时可以在多项式时间内求解。 图的语法分析 ：弦图和弦分解的概念起源于对语义网络和数据库查询优化的研究。 计算生物学 ：在系统发育树、序列比对等问题的模型中可以应用。 图形绘制与可视化 ：弦宽小的图具有更简单的层次化结构，便于可视化布局。 总结， 弦分解 通过为图寻找一个弦补图及其团树，提供了一种衡量图“树相似性”的方法。其宽度参数 弦宽 与树宽等价，是图结构复杂性的一个重要度量，为一大类组合优化问题在结构受限的图上设计高效算法提供了理论基础。