跳转到内容

团宽

维基百科,自由的百科全书
通过不交并、重标记与标签联接,构建团宽为3的距离遗传图。顶点标签用颜色表示。

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

  1. 创建标签为i的新顶点v,记作
  2. 两有标图GH不交并,记作
  3. 用边连接标i的每个顶点与标j的每个顶点,记作
  4. 将标签i改为标签j,记作

团宽有界图包括余图距离遗传图。在无界时计算团宽是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]

注释

[编辑]

参考文献

[编辑]