查看“︁团宽”︁的源代码

[[File:Clique-width construction.svg|thumb|upright=1.35|通过不交并、重标记与标签联接，构建团宽为3的[[距离遗传图]]。顶点标签用颜色表示。]]
[[图论]]中，[[图 (数学)|图]]''G''的'''团宽'''（clique-width）是描述图的结构复杂性的参数，与[[树宽]]密切相关，但对[[稠密图]]来说可以很小。
团宽的定义是通过以下4种操作，构造''G''所需的最少[[图标号|标号]]数：

# 创建标签为''i''的新顶点''v''，记作<math>i(v)</math>；
# 两有标图''G''、''H''的[[图的不交并|不交并]]，记作<math>G \oplus H</math>；
# 用边连接标''i''的每个顶点与标''j''的每个顶点，记作<math>\eta(i,\ j),\ i\ne j</math>；
# 将标签''i''改为标签''j''，记作<math>\rho(i,\ j)</math>

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

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

==特殊图类==
[[余图]]是团宽不大于2的图。{{sfnp|Courcelle|Olariu|2000}}[[距离遗传图]]的团宽不大于3。单位区间图的团宽无界（基于网格结构）。{{sfnp|Golumbic|Rotics|2000}}
相似地，二分置换图团宽无界（基于相似的网格结构）。{{sfnp|Brandstädt|Lozin|2003}}   
余图是没有任何导出子图与4顶点路径同构的图，根据这特征，对许多由禁导出子图定义的图类的团宽进行了分类。<ref>{{harvtxt|Brandstädt|Dragan|Le|Mosca|2005}}; {{harvtxt|Brandstädt|Engelfriet|Le|Lozin|2006}}.</ref>

其他团宽有界图如''k''值有界的[[叶幂|''k''叶幂]]，它们是树''T''的叶在[[图的次幂|幂]]<math>T^k</math>中的[[导出子图]]。然而，指数无界的叶幂不具有有界团宽。<ref>{{harvtxt|Brandstädt|Hundt|2008}}; {{harvtxt|Gurski|Wanke|2009}}.</ref>

==界==
{{harvtxt|Courcelle|Olariu|2000}}、{{harvtxt|Corneil|Rotics|2005}}证明，特定图的团宽有下列边界：
*若图的团宽不超过''k''，则所有[[导出子图]]也不超过''k''。<ref>{{harvtxt|Courcelle|Olariu|2000}}, Corollary&nbsp;3.3.</ref>
* ''k''团宽图的[[补图]]的团宽不大于2''k''。<ref>{{harvtxt|Courcelle|Olariu|2000}}, Theorem&nbsp;4.1.</ref>
* ''w''[[树宽]]图的团宽不大于<math>3\cdot 2^{w-1}</math>。此约束中的指数依赖是必须的：存在团宽比树宽大指数级的图。<ref>{{harvtxt|Corneil|Rotics|2005}}, strengthening {{harvtxt|Courcelle|Olariu|2000}}, Theorem&nbsp;5.5.</ref>换一种说法，团宽有界图可能有无界的树宽，例如''n''顶点[[完全图]]的团宽为2，而树宽为<math>n-1</math>。而没有[[完全二分图]]<math>K_{t,\ t}</math>为子图的''k''团宽图，树宽不大于<math>3k(t-1)-1</math>。因此，所有[[稠密图|稀疏图]]族，树宽有界等价于团宽有界。{{sfnp|Gurski|Wanke|2000}}
* [[秩宽]]的上下界都受团宽约束：<math>\text{秩宽}\le \text{团宽}\le 2^{\text{秩宽}+1}</math>。{{sfnp|Oum|Seymour|2006}}}}

另外，若图''G''的团宽为''k''，则[[图的次幂]]<math>G^c</math>的团宽不大于<math>2kc^k</math>。{{sfnp|Todinca|2003}}从树宽得出的团宽约束与图幂的团宽约束存在指数级差距，不过约束并不互相复合：
若图''G''的树宽为''w''，则<math>G^c</math>的团宽不大于<math>2(c+1)^{w+1}-2</math>，只是树宽的单指数级。{{sfnp|Gurski|Wanke|2009}}

==计算复杂度==
{{unsolved|数学|能否在多项式时间内识别团宽有界图？}}
很多对一般图来说[[NP困难]]的优化问题，限定了团宽有界、已知图的构造序列的条件后可用[[动态规划]]高效解决。{{sfnp|Cogis|Thierry|2005}}{{sfnp|Courcelle|Makowsky|Rotics|2000}}特别是，根据[[古赛尔定理]]的一种形式，可用MSO<sub>1</sub>[[一元二阶逻辑]]（允许量化顶点集的逻辑形式）表达的[[图属性]]，对团宽有界图都有线性时间算法。{{sfnp|Courcelle|Makowsky|Rotics|2000}}

已知构造序列时，也有可能在多项式时间内为团宽有界图找到最优[[图着色]]或[[哈密顿路径|哈密顿环]]，但多项式的指数随团宽增加，计算复杂度理论的证据表明这种依赖可能是必要的。{{sfnp|Fomin|Golovach|Lokshtanov|Saurabh|2010}}
团宽有界图是[[χ-有界]]的，这是说它们的色数最多是其最大团大小的函数。{{sfnp|Dvořák|Král'|2012}}

运用基于[[裂 (图论)|裂分解]]的算法，可在多项式时间内识别出团宽为3的图，并找到构造序列。{{sfnp|Corneil|Habib|Lanlignel|Reed|2012}}
对团宽无界图，精确计算团宽是[[NP困难]]的，获得亚线性加性误差的近似也是NP困难的。{{sfnp|Fellows|Rosamond|Rotics|Szeider|2009}}而团宽有界时，就可能在多项式时间内<ref>{{harvtxt|Oum|Seymour|2006}}; {{harvtxt|Hliněný|Oum|2008}}; {{harvtxt|Oum|2008}}; {{harvtxt|Fomin|Korhonen|2022}}.</ref>（特别是在顶点数的平方时间内{{sfnp|Fomin|Korhonen|2022}}）获得宽度（比实际团宽大指数级）有界的构造序列。能否在[[固定参数可解]]时间内算得确切团宽或更优的近似值、能否在多项式时间内算得团宽的每个固定边界、能否在多项式时间内识别团宽为4的图，目前仍是未知的。{{sfnp|Fellows|Rosamond|Rotics|Szeider|2009}}

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

团宽有界图的[[孪宽]]（twin-width）也有界。{{sfnp|Bonnet|Kim|Thomassé|Watrigant|2022}}

==注释==
{{reflist|30em}}

==参考文献==
{{refbegin|30em}}
*{{citation
 | last1 = Bonnet | first1 = Édouard
 | last2 = Kim | first2 = Eun Jung
 | last3 = Thomassé | first3 = Stéphan
 | last4 = Watrigant | first4 = Rémi
 | arxiv = 2004.14789
 | doi = 10.1145/3486655
 | issue = 1
 | journal = [[Journal of the ACM]]
 | mr = 4402362
 | page = A3:1–A3:46
 | title = Twin-width I: Tractable FO model checking
 | volume = 69
 | year = 2022}}
*{{citation
 | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt
 | last2 = Dragan | first2 = F.F.
 | last3 = Le | first3 = H.-O.
 | last4 = Mosca | first4 = R.
 | title = New graph classes of bounded clique-width
 | journal = Theory of Computing Systems
 | volume = 38 | year = 2005 | issue = 5 | pages = 623–645
 | doi = 10.1007/s00224-004-1154-6
 | citeseerx = 10.1.1.3.5994| s2cid = 2309695 }}.
*{{citation
 | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt
 | last2 = Engelfriet | first2 = J.
 | last3 = Le | first3 = H.-O.
 | last4 = Lozin | first4 = V.V.
 | title = Clique-width for 4-vertex forbidden subgraphs
 | journal = Theory of Computing Systems
 | volume = 39 | year = 2006 | issue = 4 | pages = 561–590
 | doi = 10.1007/s00224-005-1199-1
 | s2cid = 20050455 }}.
*{{citation
 | last1 = Brandstädt | first1 = Andreas
 | last2 = Hundt | first2 = Christian
 | contribution = Ptolemaic graphs and interval graphs are leaf powers
 | doi = 10.1007/978-3-540-78773-0_42
 | mr = 2472761
 | pages = 479–491
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = LATIN 2008: Theoretical informatics
 | volume = 4957
 | year = 2008}}.
*{{citation
 | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt
 | last2 = Lozin | first2 = V.V.
 | title = On the linear structure and clique-width of bipartite permutation graphs
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | volume = 67 | year = 2003 | pages = 273–281
 | citeseerx = 10.1.1.16.2000}}.
*{{citation
 | last = Chlebíková | first = J. | author-link = Janka Chlebíková
 | issue = 2
 | journal = Acta Mathematica Universitatis Comenianae
 | mr = 1205875
 | pages = 225–236
 | series = New Series
 | title = On the tree-width of a graph
 | volume = 61
 | year = 1992| citeseerx = 10.1.1.30.3900
 }}.
*{{citation
 | last1 = Cogis | first1 = O.
 | last2 = Thierry | first2 = E.
 | title = Computing maximum stable sets for distance-hereditary graphs
 | journal = Discrete Optimization
 | volume = 2 | issue = 2 | year = 2005 | pages = 185–188
 | mr = 2155518
 | doi = 10.1016/j.disopt.2005.03.004| doi-access = free}}.
*{{citation
 | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil
 | last2 = Habib | first2 = Michel
 | last3 = Lanlignel | first3 = Jean-Marc
 | last4 = Reed | first4 = Bruce | author4-link = Bruce Reed (mathematician)
 | last5 = Rotics | first5 = Udi
 | doi = 10.1016/j.dam.2011.03.020
 | issue = 6
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2901093
 | pages = 834–865
 | title = Polynomial-time recognition of clique-width {{math|≤ 3}} graphs
 | volume = 160
 | year = 2012| doi-access = free
 }}.
*{{citation
 | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil
 | last2 = Rotics | first2 = Udi
 | doi = 10.1137/S0097539701385351
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 2148860
 | pages = 825–847
 | title = On the relationship between clique-width and treewidth
 | volume = 34
 | year = 2005}}.
*{{citation
 | last1 = Courcelle | first1 = Bruno | author1-link = Bruno Courcelle
 | last2 = Engelfriet | first2 = Joost
 | last3 = Rozenberg | first3 = Grzegorz
 | doi = 10.1016/0022-0000(93)90004-G
 | issue = 2
 | journal = Journal of Computer and System Sciences
 | mr = 1217156
 | pages = 218–270
 | title = Handle-rewriting hypergraph grammars
 | volume = 46
 | year = 1993| doi-access = free
 }}. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), {{MR|1431281}}.
*{{citation
 | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle
 | contribution = Monadic second-order logic and hypergraph orientation
 | doi = 10.1109/LICS.1993.287589
 | pages = 179–190
 | title = Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93)
 | year = 1993| s2cid = 39254668 }}.
*{{citation
 | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle
 | last2 = Makowsky | first2 = J. A. | author2-link = Johann Makowsky
 | last3 = Rotics | first3 = U.
 | title = Linear time solvable optimization problems on graphs on bounded clique width
 | journal = Theory of Computing Systems
 | volume = 33 | issue = 2 | year = 2000 | pages = 125–150
 | doi = 10.1007/s002249910009| citeseerx = 10.1.1.414.1845| s2cid = 15402031 }}.
*{{citation | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle | last2 = Olariu | first2 = S. | title = Upper bounds to the clique width of graphs | journal = [[Discrete Applied Mathematics]] | volume = 101 | issue = 1–3 | year = 2000 | pages = 77–144 | doi = 10.1016/S0166-218X(99)00184-5 | url = https://digitalcommons.odu.edu/computerscience_fac_pubs/122 | doi-access = free | accessdate = 2024-02-01 | archive-date = 2024-04-20 | archive-url = https://web.archive.org/web/20240420101639/https://digitalcommons.odu.edu/computerscience_fac_pubs/122/ | dead-url = no }}.
*{{citation
 | last1 = Dvořák | first1 = Zdeněk
 | last2 = Král' | first2 = Daniel
 | arxiv = 1107.2161
 | doi = 10.1016/j.ejc.2011.12.005
 | issue = 4
 | journal = Electronic Journal of Combinatorics
 | pages = 679–683
 | title = Classes of graphs with small rank decompositions are χ-bounded
 | volume = 33
 | year = 2012| s2cid = 5530520
 }}
*{{citation
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond
 | last3 = Rotics | first3 = Udi
 | last4 = Szeider | first4 = Stefan | author4-link = Stefan Szeider
 | doi = 10.1137/070687256
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2519936
 | pages = 909–939
 | title = Clique-width is NP-complete
 | volume = 23
 | year = 2009}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Golovach | first2 = Petr A.
 | last3 = Lokshtanov | first3 = Daniel
 | last4 = Saurabh | first4 = Saket
 | doi = 10.1137/080742270
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | mr = 2592039
 | pages = 1941–1956
 | title = Intractability of clique-width parameterizations
 | volume = 39
 | year = 2010| citeseerx = 10.1.1.220.1712}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Korhonen | first2 = Tuukka
 | contribution = Fast FPT-approximation of branchwidth
 | doi = 10.1145/3519935.3519996
 | pages = 886–899
 | publisher = ACM
 | title = Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
 | arxiv = 2111.03492
 | year = 2022| s2cid = 243832882
 }}.
*{{citation
 | last1 = Golumbic | first1 = Martin Charles | authorlink = Martin Charles Golumbic
 | last2 = Rotics | first2 = Udi
 | title = On the clique-width of some perfect graph classes
 | journal = International Journal of Foundations of Computer Science
 | volume = 11 | issue = 3 | year = 2000 | pages = 423–443
 | mr = 1792124
 | doi = 10.1142/S0129054100000260}}.
*{{citation
 | last1 = Gurski | first1 = Frank
 | last2 = Wanke | first2 = Egon
 | editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes
 | editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner
 | contribution = The tree-width of clique-width bounded graphs without {{math|''K<sub>n,n</sub>''}}
 | doi = 10.1007/3-540-40064-8_19
 | location = Berlin
 | mr = 1850348
 | pages = 196–205
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings
 | volume = 1928
 | year = 2000}}.
*{{citation
 | last1 = Gurski | first1 = Frank
 | last2 = Wanke | first2 = Egon
 | title = Line graphs of bounded clique-width
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 307
 | issue = 22
 | year = 2007
 | pages = 2734–2754
 | doi = 10.1016/j.disc.2007.01.020| doi-access = free
 }}.
*{{citation
 | last1 = Gurski | first1 = Frank
 | last2 = Wanke | first2 = Egon
 | doi = 10.1016/j.dam.2008.08.031
 | issue = 4
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2499471
 | pages = 583–595
 | title = The NLC-width and clique-width for powers of graphs of bounded tree-width
 | volume = 157
 | year = 2009| doi-access = free
 }}.
*{{citation
 | last1 = Hliněný | first1 = Petr
 | last2 = Oum | first2 = Sang-il |author-link2= Oum Sang-il
 | doi = 10.1137/070685920
 | issue = 3
 | journal = [[SIAM Journal on Computing]]
 | mr = 2421076
 | pages = 1012–1032
 | title = Finding branch-decompositions and rank-decompositions
 | volume = 38
 | year = 2008| citeseerx = 10.1.1.94.2272
 }}.
*{{citation
 | last1 = Oum | first1 = Sang-il |author-link1= Oum Sang-il
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/j.jctb.2005.10.006
 | issue = 4
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2232389
 | pages = 514–528
 | series = Series B
 | title = Approximating clique-width and branch-width
 | volume = 96
 | year = 2006| doi-access = free
 }}.
*{{citation
 | last = Oum | first = Sang-il |author-link= Oum Sang-il
 | doi = 10.1145/1435375.1435385
 | issue = 1
 | journal = [[ACM Transactions on Algorithms]]
 | mr = 2479181
 | page = Art. 10, 20
 | title = Approximating rank-width and clique-width quickly
 | volume = 5
 | year = 2008 | citeseerx = 10.1.1.574.8156
 }}.
*{{citation
 | last = Todinca | first = Ioan
 | contribution = Coloring powers of graphs of bounded clique-width
 | doi = 10.1007/978-3-540-39890-5_32
 | mr = 2080095
 | pages = 370–382
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Graph-theoretic concepts in computer science
 | volume = 2880
 | year = 2003}}.
*{{citation
 | last = Wanke | first = Egon
 | doi = 10.1016/0166-218X(94)90026-4
 | issue = 2–3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 1300250
 | pages = 251–266
 | title = {{mvar|k}}-NLC graphs and polynomial algorithms
 | volume = 54
 | year = 1994| doi-access = free
 }}.
{{refend}}

[[Category:图常量]]
[[Category:图论]]