图的树深度与消去序

图的树深度是衡量图“类似树”程度的结构参数，它通过图的分解树中根到叶子的最长路径来定义。这一概念在算法设计和结构图论中具有重要作用，尤其适用于描述具有层次结构的图性质。

1. 基本定义

   • 给定图G的分解树T（任意树结构），树深度定义为T中从根到任意叶子的最大路径长度（按边数计算）
   • 图G的树深度td(G)是所有可能分解树中的最小树深度值
   • 例如：路径图Pₙ的树深度为⌈log₂(n+1)⌉，星图的树深度为2

2. 消去序刻画

   • 图的消去序是顶点排列v₁,v₂,...,vₙ，每个顶点vᵢ与其在后续顶点集中的邻居构成连通分支
   • 树深度等于最优消去序中任一顶点在剩余图中所在连通分支大小的最大值
   • 该性质与图的搜索策略（如深度优先搜索）密切相关

3. 与树宽的关系

   • 对任意图G满足：td(G) ≤ (tw(G)+1)·log₂(n+1)
   • 树深度上界总不超过树宽加1的对数倍，但对某些图类（如路径）该界是紧的
   • 树深度参数在平面图和有界树宽图中具有更好的结构性

4. 算法应用

   • 在固定树深度的图类上，许多NP难问题（如染色、支配集）存在线性时间算法
   • 模型检验中用于描述有限自动机在分层结构上的行为
   • 与逻辑公式的量化深度存在深刻联系，影响模型检查算法的效率

5. 极值性质

   • 不含长度超过l的路径的图，其树深度不超过l
   • 平面图的树深度与直径呈对数关系
   • 在稀疏图理论中，树深度是定义“浅图分解”的关键参数