AI tools

图论中，图G的团宽（clique-width）是描述图的结构复杂性的参数，与树宽密切相关，但对稠密图来说可以很小。 团宽的定义是通过以下4种操作，构造G所需的最少标号数：

  1. 创建标签为i的新顶点v，记作；
  2. 两有标图G、H的不交并，记作；
  3. 用边连接标i的每个顶点与标j的每个顶点，记作；
  4. 将标签i改为标签j，记作
Thumb
通过不交并、重标记与标签联接，构建团宽为3的距离遗传图。顶点标签用颜色表示。

团宽有界图包括余图与距离遗传图。在无界时计算团宽是NP困难的，而有界时能否在多项式时间内计算团宽也是未知的，不过已经有一些高效的团宽近似算法。 基于这些算法与古赛尔定理，很多对任意图来说NP难的图优化问题都可在团宽有界图上快速求解或逼近。

Courcelle、Engelfriet、Rozenberg在1990年[1]、Wanke (1994)提出了作为团宽概念基础的构造序列。“团宽”一词始见于Chlebíková (1992)，是用于另一个概念。1993年，这个词有了现在的含义。[2]

特殊图类

余图是团宽不大于2的图。[3]距离遗传图的团宽不大于3。单位区间图的团宽无界（基于网格结构）。[4] 相似地，二分置换图团宽无界（基于相似的网格结构）。[5] 余图是没有任何导出子图与4顶点路径同构的图，根据这特征，对许多由禁导出子图定义的图类的团宽进行了分类。[6]

其他团宽有界图如k值有界的k叶幂，它们是树T的叶在幂中的导出子图。然而，指数无界的叶幂不具有有界团宽。[7]

界

Courcelle & Olariu (2000)、Corneil & Rotics (2005)证明，特定图的团宽有下列边界：

  • 若图的团宽不超过k，则所有导出子图也不超过k。[8]
  • k团宽图的补图的团宽不大于2k。[9]
  • w树宽图的团宽不大于。此约束中的指数依赖是必须的：存在团宽比树宽大指数级的图。[10]换一种说法，团宽有界图可能有无界的树宽，例如n顶点完全图的团宽为2，而树宽为。而没有完全二分图为子图的k团宽图，树宽不大于。因此，所有稀疏图族，树宽有界等价于团宽有界。[11]
  • 秩宽的上下界都受团宽约束：。[12]}}

另外，若图G的团宽为k，则图的次幂的团宽不大于。[13]从树宽得出的团宽约束与图幂的团宽约束存在指数级差距，不过约束并不互相复合： 若图G的树宽为w，则的团宽不大于，只是树宽的单指数级。[14]

计算复杂度

未解决的数学问题：能否在多项式时间内识别团宽有界图？

很多对一般图来说NP困难的优化问题，限定了团宽有界、已知图的构造序列的条件后可用动态规划高效解决。[15][16]特别是，根据古赛尔定理的一种形式，可用MSO1一元二阶逻辑（允许量化顶点集的逻辑形式）表达的图属性，对团宽有界图都有线性时间算法。[16]

已知构造序列时，也有可能在多项式时间内为团宽有界图找到最优图着色或哈密顿环，但多项式的指数随团宽增加，计算复杂度理论的证据表明这种依赖可能是必要的。[17] 团宽有界图是χ-有界的，这是说它们的色数最多是其最大团大小的函数。[18]

运用基于裂分解的算法，可在多项式时间内识别出团宽为3的图，并找到构造序列。[19] 对团宽无界图，精确计算团宽是NP困难的，获得亚线性加性误差的近似也是NP困难的。[20]而团宽有界时，就可能在多项式时间内[21]（特别是在顶点数的平方时间内[22]）获得宽度（比实际团宽大指数级）有界的构造序列。能否在固定参数可解时间内算得确切团宽或更优的近似值、能否在多项式时间内算得团宽的每个固定边界、能否在多项式时间内识别团宽为4的图，目前仍是未知的。[20]

相关宽参数

有界团宽图理论类似于有界树宽图，不同的是，团宽有界图可以稠密。若图族的团宽有界，则要么其树宽也有界，要么每个完全二分图都是图族中某个图的子图。[11]树宽与团宽还通过线图理论联系在一起：当且仅当图族的线图团宽都有界，图族的树宽有界。[23]

团宽有界图的孪宽（twin-width）也有界。[24]

注释

参考文献

Wikiwand - on

Seamless Wikipedia browsing. On steroids.