团宽

通过不交并、重标记与标签联接，构建团宽为3的距离遗传图。顶点标签用颜色表示。

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

1. 创建标签为i的新顶点v，记作$i(v)$；
2. 两有标图G、H的不交并，记作$G\oplus H$；
3. 用边连接标i的每个顶点与标j的每个顶点，记作$\eta (i,j),i\ne j$；
4. 将标签i改为标签j，记作$\rho (i,j)$

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

Courcelle、Engelfriet、Rozenberg在1990年Template:Sfnp、Template:Harvtxt提出了作为团宽概念基础的构造序列。“团宽”一词始见于Template:Harvtxt，是用于另一个概念。1993年，这个词有了现在的含义。Template:Sfnp

特殊图类

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

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

界

Template:Harvtxt、Template:Harvtxt证明，特定图的团宽有下列边界：

• 若图的团宽不超过k，则所有导出子图也不超过k。
• k团宽图的补图的团宽不大于2k。
• w树宽图的团宽不大于$3\cdot 2^{w-1}$。此约束中的指数依赖是必须的：存在团宽比树宽大指数级的图。换一种说法，团宽有界图可能有无界的树宽，例如n顶点完全图的团宽为2，而树宽为$n-1$。而没有完全二分图$K_{t,t}$为子图的k团宽图，树宽不大于$3k(t-1)-1$。因此，所有稀疏图族，树宽有界等价于团宽有界。Template:Sfnp
• 秩宽的上下界都受团宽约束：$\text{秩宽}\le \text{团宽}\le 2^{\text{秩宽}+1}$。Template:Sfnp}}

另外，若图G的团宽为k，则图的次幂$G^c$的团宽不大于$2k{c}^k$。Template:Sfnp从树宽得出的团宽约束与图幂的团宽约束存在指数级差距，不过约束并不互相复合： 若图G的树宽为w，则$G^c$的团宽不大于$2(c+1{)}^{w+1}-2$，只是树宽的单指数级。Template:Sfnp

计算复杂度

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

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

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

相关宽参数

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

团宽有界图的孪宽（twin-width）也有界。Template:Sfnp

参考文献

• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), Template:MR.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.