团宽

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

 创建标签为i的新顶点v，记作；
 两有标图G、H的不交并，记作；
 用边连接标i的每个顶点与标j的每个顶点，记作；
 将标签i改为标签j，记作

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

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

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

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

界
、证明，特定图的团宽有下列边界：
若图的团宽不超过k，则所有导出子图也不超过k。, Corollary 3.3.
 k团宽图的补图的团宽不大于2k。, Theorem 4.1.
 w树宽图的团宽不大于。此约束中的指数依赖是必须的：存在团宽比树宽大指数级的图。, strengthening , Theorem 5.5.换一种说法，团宽有界图可能有无界的树宽，例如n顶点完全图的团宽为2，而树宽为。而没有完全二分图为子图的k团宽图，树宽不大于。因此，所有稀疏图族，树宽有界等价于团宽有界。
 秩宽的上下界都受团宽约束：。

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

计算复杂度

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

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

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

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

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

注释

参考文献

.
.
.
.
.
.
.
.
. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), .
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

Category:图常量
Category:图论