跳转到内容

图同态

本页使用了标题或全文手工转换
维基百科,自由的百科全书
J5至C5的同态
花形蛇鲨图英语flower snarkJ5射向环图C5的同态,亦是到J5中央五个顶点所成子图的收缩,所以J5与其英语core (graph theory)C5“同态等价”。

数学分支图论中,图同态(英语:graph homomorphism)是两幅之间保结构的映射。具体而言,该映射将某图的各顶点映至另一图的顶点,且若两顶点相邻,则其仍然相邻。

同态是若干种图着色概念的推广,适用于表达一类重要的约束满足问题,如排程频段分配英语frequency assignment问题。[1]同态可以复合,为全体图组成的赋予丰富的代数结构:其上的预序关系分配格结构范畴结构(分为无向图范畴与有向图范畴两种)。[2]欲寻找任意两图间的同态,而无额外条件,则现时所知的计算复杂度英语computational complexity高得不切实际,但对于某些特定类别的图,已知有多项式时间算法。此类问题易解与否,两者的分野,是活跃的研究方向。[3]

定义

[编辑]

本条目中,除非另有声明,否则“图”皆为有限无向图,允许自环,但无重边(两点间连多于一条边)。自至另一图图同态[4],记作

是顶点集的函数,其将每条边的两端分别映至某边的两端。以符号表示:对中每对顶点,若,则。若存在的同态,则称同态于homomorphic to,或可染-colourable),常简记为:

上述定义可引伸至有向图,此时,为同态的条件是,中每条有向边的像,仍是的有向边。

同态(将不同顶点映至不同顶点),当且仅当子图。若同态双射(两图顶点集的一一对应),且其亦是图同态,则图同构[5]

图的覆叠映射英语Covering graph是一类特殊的图同态,相当于将图视为拓扑空间英语Graph (topology)时,拓扑学上的覆叠映射,其定义及性质亦是类似:[6]图覆叠是同态(即作为陪域的图,其每个顶点皆为定义域某顶点的像),且局部为双射,即若限制到每个顶点的邻域英语neighbourhood (graph theory),则为双射。举例,图的典范双重复叠英语bipartite double cover,是将每点分裂为两点,并将原图每条边换成交叉的两条边。如此,可以定义函数将皆映至,既是图同态,也是覆叠映射。

图同胚是另一个概念,不一定是同态。粗略而言,同胚要求是单射,但不必将边映至边,允许映至路径图子式的要求更松。

核与回缩

[编辑]
K7,七个顶点的完全图,一种核图

若两幅图有同态,则称两者同态等价homomorphically equivalent)。[4]该些映射不必单,也不必满。例如,完全二部图同态等价,因为可将左部两个顶点映到左部同一个顶点,其右部的两个顶点映到右部一个顶点,同样有的同态。

收缩映射retraction)是自图至其子图的同态,且对中每个顶点。若有此种映射,则称为收缩核retract)。[7]

核图core)没有到任何真子图的同态。亦可等价定义成无法收缩到任何真子图的图。[8]每幅图皆同态等价于唯一的核图(不辨同构之别),称为的核the core of )。[9]此结论对无穷图不一定成立[10],但对(有限的)有向图可以照套用同样的定义,每幅有向图同态等价于唯一的核图。图(或有向图)的核,必为原图某个收缩核,以及某个导出子图[7]

举例,完全图及奇环(奇数条边的循环图)皆属核图。若可染三色,且有三角形(即子图),则同态等价于,原因是的三染色,下节将说明相当于同态,且另一方面,任意子图皆有同态嵌入,故有。如此,证毕为所有此种的核。与之相似,每幅非空二部图(有至少一条边)皆等价于[11]

与染色的关联

[编辑]

对正整数,图染色是将每个顶点涂色之一,使每条边的两端都不同色。此种染色,与自完全图的同态,两类物件一一对应[12],因为的各顶点对应种色,且若为颜色,则其于图相邻当且仅当。于是,某函数是的同态,当且仅当该函数将中相邻的顶点映至不同颜色(即染色的定义)。换言之,可染色等价于可染色。[12]

若有同态,则两者复合可得同态[13]所以,若可染色,且有同态,则同样可染色。因此,推出,其中表示图的色数[注 1][14]

变式

[编辑]

其他同态亦可视作特殊的染色。给定图,其顶点视为可用的颜色,每条边表示某两色“可兼容”,则染色就是将相邻顶点染成相容颜色的方案。此框架可容纳许多图染色的概念,将其表述为射向各类图的同态。举例如下:

无长路径的定向

[编辑]

图同态与图定向英语Orientation (graph theory)也有关。无向图的定向是赋予每边一个方向(二选一),所得的有向图。同一幅无向图可以有多种不同的定向。举例,完全图可定向成“递移循环赛图英语Tournament (graph theory),其顶点为,对所有有(有向)边自指向。给定的定向与的定向之间的同态,忘掉定向即得本来无向图之间的同态。另一方面,给定无向图同态任何定向可以拉回的定向,使原同态亦是的有向图同态。综上,无向图可染色(即有同态至),当且仅当有某定向,具有至的同态。[20]

有定理流传[注 3],对每个,有向图有同态至,当且仅当个顶点的有向路径图英语path graph[注 4]无同态至[21]

因此,某图可染色,当且仅当其有某定向,不容任何自至该定向的同态。此命题可加强成

高洛伊-哈塞-罗伊-维塔韦尔定理英语Gallai–Hasse–Roy–Vitaver theorem:某图可染色,当且仅当该图有某定向,其中无长为的有向路径(即作为子图)。

与前一命题的分别在于,自至某图的同态允许将两顶点映至同处,但“长为的有向路径”不允许重复顶点。

与约束满足问题的关联

[编辑]

范例

[编辑]
,表示一周中不相邻的日子,同构于环补图,亦同构于环状团英语circular clique

某些排程问题可用图同态建模。[22][23]设学校已知各学生所选科目,要编排今学期各专题讨论班的时间,使同一学生所选的讨论班时间不致太近。考虑图以各科为顶点,若两科有共同学生则连边,而图以各课节为顶点,若两个时段隔足够远则连边。举例若限制时间表须每周循环,且每个学生所选的讨论班须相隔一日,则对应的是环补图。如此,的图同态,就是讨论班对应到课节的合适方案。[22]欲添加额外条件,如禁止学生同时于周五与周一有讨论班,衹需从删掉相应的边。

无线电的频段分配英语frequency allocation问题简述如下:无线网络中,有若干发讯机,要为每部机配置一个频率,供其发讯。为免干扰,地理位置较近的发讯机应选用相差较远的频率。若将条件中“地理较近”与“频率较远”简化至非黑即白,则合适的分配方案又可视为图同态。图的顶点为各发讯机,边表示两机地理上接近;图以各频段为顶点,边则表示两频段相隔够远。虽然此模型甚为简化,但是尚有保留一点弹性:若有两机相隔较远,但仍因地形导致可能干扰,则在中加边即可。反之,若有两机永不在同一时段发讯,则不论其地理位置是否靠近,皆可从中删去该边。同样,或许有某些频率相差颇远,但是互为谐波,导致干扰,则将该边自移除即可[24]

前述模型经简化,若要实际应用,许多问题仍待解决。[25]约束满足问题是图同态问题的推广,能表达更多种条件(例如个体偏好,或重复分配次数有上限),从而建立更实际的数学模型。

抽象观点

[编辑]

数理逻辑或泛代数中,图与有向图属关系结构的特例,即集合配备若干关系。有向图就是基集(顶点集)之上有独一个二元关系(邻接关系)。[26][3]如是观之,图作为关系结构的同态,按抽象代数的同态定义,等同于本文的图同态。一般而言,欲寻找自某关系结构至另一关系结构的同态,属于约束满足问题constraint satisfaction problem, CSP)。图的特例可作为第一步,帮助理解更复杂的CSP。许多寻找图同构的算法,包括回溯约束传播英语constraint propagation局部搜索英语Local search (constraint satisfaction),通用于各种CSP[3]

给定图,问是否有同态,相当于仅得一类约束的CSP实例[3]CSP的“变量”是的顶点,每个变量的“域”(可取值的范围)是的顶点集。“赋值”是一个函数,将逐个变量映至域的元素,即函数的每条边(或有向边)对应一个“约束”,限制赋值函数将边映至关系中,即映至的某边。CSP的“解”是满足全体约束的赋值,故前述CSP的解正是自的同态。

同态的结构

[编辑]

同态的复合仍是同态[13],故可知图的关系具递移性,又显然自反,所以其为图之间的预序[27]同态等价意义下,记所属等价类,每个等价类有唯一的核图为其代表。关系定义该些等价类之间的偏序,即同态等价类构成一个偏序集[28]

表示有同态至,但反之则不然。如此定义的序稠密英语dense order,即对任意(无向)图,若,则存在第三幅图使,除非是平凡反例[29][30]例如,任意两幅整数阶完全图(除外)之间,必有无穷多幅环状完全图英语circular clique,相当于整阶数之间的有理数阶数。[31]

同态等价类的偏序集是分配格是互斥并,而图张量积英语tensor product of graphs,其定义不取决于等价类中所选的代表[32]此格中,并不可约元英语join-irreducible[注 5]正好是连通图,证明方式是留意同态衹会将连通图映到目标的一个连通分支中。[33][34]交不可约元英语meet-irreducible[注 5]正好是积性图英语Hedetniemi's conjecturemultiplicative graphs),此种图的特性是,若乘积有同态至,则两者之一有同态至。如何识别积性图是赫德米猜想英语Hedetniemi's conjecture[35]的关键。[36][37]

图与同态还组成范畴:图是物件,而同态是态射。[38]范畴的始物件是空图终物件有一个顶点和一个自环图张量积英语tensor product of graphs范畴论积指数图英语Hedetniemi's conjecture[注 6]是该范畴的指数物件英语exponential object。换言之,自的同态与的同态自然地一一对应。[37][39]由于对任意图,张量积与幂总有定义,图范畴是笛卡儿闭范畴。同理,同态等价类组成的格实际上是海廷代数:按海廷代数的语言,前述的积称为交运算,而前述的指数运算称为蕴涵[37][39]

对于有向图,适用同样的定义。同样有是有向图同态等价类之间的偏序,其与无向图等价类的偏序有别,但后者是前者的子序,因为无向图亦可视为有向图,衹是其中每条有向边皆与其反向成对出现。换言之,无向图同态的定义,与双向有向图的同态并无区别。有向图的序仍是分配格和海延代数,交与并的定义亦同上,但分别在于,该序并不稠密。亦有以有向图为物件、同态为态射的范畴,照样笛卡儿闭[40][39]

不可比图

[编辑]
格勒奇图英语Grötzsch graph,与不可比

同态预序下,许多图不可比较。两幅不可比图(incomparable graphs)之间,并无自任意一幅至另一幅的同态。[41]欲构造此种图,可考虑图的奇围长,即最短的奇环长度。奇围长可等价地说成最小的奇数,使个顶点的循环图有同态至。由此定义,若,则的奇围长大于或等于的奇围长。[42]

另一方面,前节已证若,则的色数小于或等于的色数。所以,若的奇围长及色数皆严格大于,则不可比较。[41] 举例,格勒奇图英语Grötzsch graph色数为,且无三角形(围长,奇围长[43],所以与三角形不可比。

有几类图的奇围长和色数可取任意大,如克内泽尔图英语Kneser graph[44]广义梅切尔斯基图英语Mycielskian[45]。如此一类图,若使其两参数同时递增,排成一列,则有无穷多幅不可比图(同态预序下的反链)。[46] 同态预序稠密英语dense order等其他性质,亦可利用此类图证明。[47]此外,可构造同时具大色数和大围长(不仅是奇围长)的图,但较复杂,见围长 (图论) § 围长与图染色

有向图之中,更易找到不可比图。例如,考虑有向环,顶点为,有向边自(对各一),及自。对于有同态当且仅当的倍数。所以,当取质数值时,两两不可比。[48]

计算复杂度

[编辑]

图同态问题是给定一对图,求自的图同态。对应的决定性问题问是否存在此种解。一般情况下,即询问的实例不受额外限制的情况下,此决定性问题为NP完全[49]若限制询问的范围,衹限从某类图中选出,则可得多种不同的问题,其中有些较易求解。限制左边和限制右边相比,适用的方法相去甚远,但两者似乎有一共同特点:难易情况之间似乎有明确的分界,此分界或者已获证,或有论文猜想如此。

至给定图的同态

[编辑]

图同态问题若固定右边的图不变,则称为染色问题。为完全图时,化成k色问题,在时,可于多项式时间内求解,但其馀情况则是NP完全[50]的情况相当于问图可否染色,即是否二部图,此问题可在线性时间内求解。更一般地,衹要是二部图就有同一结论:可染色等价于可染色,即可染二色,故此种情况同样易判断。可染色和可染色分别等价于无顶点和无边,亦易判断。[51]帕沃尔·黑尔英语Pavol Hell雅罗斯拉夫·内舍特日尔英语Jaroslav Nešetřil证明,对无向图而言,无其他情况可驯顺:

(黑尔-内舍特日尔定理,1990年)若为二部图,则染色问题属于P,但其馀情况则为NP完全。[52][53]

上述定理又称为无向图同态的“对分定理”(dichotomy theorem),因为将染色问题分成NP完全与P两类,而无居中英语NP-intermediate情况。有向图情况较复杂,此时问题等价于刻画看似更一般的约束满足问题的复杂度英语Complexity of constraint satisfaction[54]:有向图的染色问题,与允许各种约束条件的CSP相比,同样多姿多彩,而不失一般性。[55][56]严格而言,定义(有限)约束语言(constraint language,或称模板template为一个有限的取值域,其上配备有限多种关系,然后以表示约束衹能选自的一类约束满足问题,则有以下定理:

(费德、瓦迪英语Moshe Y. Vardi,1998年)对任意约束语言,必有某幅有向图,使多项式时间归约意义下等价于染色问题。[56]

直观理解,定理意味着任何算法技巧或复杂度结论,若适用于一般有向图的染色问题,则可套用至一般CSP。考虑将黑尔-内舍特日尔定理扩展至有向图。由上述定理,该推广等价于有关CSP对分的费德-瓦迪猜想(又称CSP猜想、对分猜想),即断言对任意约束语言或属NP完全,或属P。[49]此猜想于2017年由德米特里·祖克(Dmitry Zhuk)与安德烈·布拉托夫(Andrei Bulatov)分别独立证出,故有以下推论:

(布拉托夫2017年;祖克2017年)给定时,有向图的染色问题或属P,或属NP完全。

自给定族的同态

[编辑]

若左输入为给定,则图同态问题有暴力解法,即穷举的各个顶点在中的像,复杂度仅为,已是输入的多项式函数。[57]换言之,限制的大小时,问题显然属P,但仍可改为研究另一课题:除大小之外,是否其他限制可施加于,使图同态问题可于多项式时间内求解?

研究表明,关键性质是树阔英语treewidth,此参数衡量一幅图有多似一棵树。若的树阔至多为,而为任意图,则利用标准的动态规划方法,可于时间内求解图同态问题。实际甚至衹需假设的核的树阔不逾,而无需知道其核为何。[58][59]

算法中,复杂度的指数可能无法再压低太多:若指数时间假设英语exponential time hypothesis[注 7]ETH)为真,则不存在时间复杂度为的算法。即使限制衹能取值为某一族图,衹要该族图的树阔无上界,则仍有同样结论。[60]同样假设下,几乎没有其他性质使问题可于多项式时间内求解,具体含义如下:

格罗厄英语Martin Grohe)假定ETH,并给定由图组成的可计算。考虑输入为,且的图同态问题。此问题属P当且仅当中各图之核的树阔有界。[59]

或考虑有所取舍,允许复杂度高度依赖,换取复杂度与的关系仅为固定的多项式。与前段类似,若的取值范围中,核的树阔有界,则此目标可以实现,但若的取值范围不满足该条件,则无法达成。[59]利用带参数复杂度英语parameterized complexity术语,上述成果可覆述为:中的同态问题,以的边数为参数,呈现对分现象。若中各图之核的树阔有上界,则该问题为固定参数可驯顺英语fixed-parameter tractable,否则为W[1]英语Parameterized complexity完全。

同一命题对其他关系结构亦成立。换言之,其适用于一般的约束满足问题,不过需要限制各项约束涉及的变量数有上界,即关系的元数有上界(以图为例,仅得元数为2的关系)。此时,关键参数为原始约束图英语primal constraint graph[注 8]的树阔。[60]

参见

[编辑]

[编辑]
  1. ^ 使该图可染色的最小值。
  2. ^ 个顶点,相异两点间有连边当且仅当模运算时,大于某定值。
  3. ^ 数学流传英语Mathematical folklore,谓难以溯源或原创者并无正式投稿出版,但广为研究者熟知的定理。
  4. ^ 的顶点为,且对每个有一条边自
  5. ^ 5.0 5.1 为并不可约,意即推出。对偶概念为交不可约。
  6. ^ 指数图(exponential graph的顶点是函数,两顶点连边当且仅当对中任意两个相邻顶点,有中相邻。
  7. ^ 指数时间假设与P ≠ NP类似,皆是未获证的复杂度假设,但前者更强。
  8. ^ 约束满足问题中,以变数为顶点,两变数有出现在同一个约束中则连边,可得“原始约束图”。此即以各约束为边的超图原始图英语primal graph

参考资料

[编辑]
  1. ^ Hell & Nešetřil 2004,第27页.
  2. ^ Hell & Nešetřil 2004,第109页.
  3. ^ 3.0 3.1 3.2 3.3 Hell & Nešetřil 2008.
  4. ^ 4.0 4.1 引论见诸:Cameron (2006); Hahn & Tardif (1997); Hell & Nešetřil (2004). 由短至长排。
  5. ^ Hahn & Tardif 1997,Observation 2.3.
  6. ^ Godsil & Royle 2001,第115页.
  7. ^ 7.0 7.1 Hell & Nešetřil 2004,第19页.
  8. ^ Hell & Nešetřil 2004,Proposition 1.31.
  9. ^ Cameron 2006,Proposition 2.3; Hell & Nešetřil 2004,Corollary 1.32.
  10. ^ Hell & Nešetřil 2004,第34页.
  11. ^ Cameron 2006,第4页,Proposition 2.5.
  12. ^ 12.0 12.1 Cameron 2006,第1页; Hell & Nešetřil 2004,Proposition 1.7.
  13. ^ 13.0 13.1 Hell & Nešetřil 2004,§1.7.
  14. ^ Hell & Nešetřil 2004,Corollary 1.8.
  15. ^ Hell & Nešetřil 2004,§6.1; Hahn & Tardif 1997,§4.4.
  16. ^ Hell & Nešetřil 2004,§6.2; Hahn & Tardif 1997,§4.5.
  17. ^ Hell & Nešetřil 2004,§6.3.
  18. ^ Hell & Nešetřil 2004,§6.4.
  19. ^ Fiala, J.; Kratochvíl, J., Partial covers of graphs [图之部分覆盖], Discussiones Mathematicae Graph Theory, 2002, 22 (1): 89–99, S2CID 17507393, doi:10.7151/dmgt.1159 (英语) 
  20. ^ Hell & Nešetřil 2004,第13–14页.
  21. ^ Hell & Nešetřil 2004,Proposition 1.20.
  22. ^ 22.0 22.1 Cameron 2006,第1页.
  23. ^ Hell & Nešetřil 2004,§1.8.
  24. ^ Hell & Nešetřil 2004,第30–31页.
  25. ^ Hell & Nešetřil 2004,第31–32页.
  26. ^ Hell & Nešetřil 2004,第28页,该书称关系结构(relational structures)为“关系系统”(relational systems)。
  27. ^ Hell & Nešetřil 2004,§3.1.
  28. ^ Hell & Nešetřil 2004,Theorem 3.1.
  29. ^ Hell & Nešetřil 2004,Theorem 3.30; Hahn & Tardif 1997,Theorem 2.33.
  30. ^ Welzl, E., Color-families are dense [染色族稠密], Theoretical Computer Science英语Theoretical Computer Science (journal), 1982, 17: 29–41, doi:10.1016/0304-3975(82)90129-3可免费查阅 (英语) 
  31. ^ Hell & Nešetřil 2004,第192页; Hahn & Tardif 1997,第127页.
  32. ^ Hell & Nešetřil 2004,Proposition 3.2,分配律载于Proposition 2.4;又见Hahn & Tardif 1997,Theorem 2.37.
  33. ^ Kwuida, Léonard; Lehtonen, Erkko, On the Homomorphism Order of Labeled Posets [论标号偏序集之同态序], Order英语Order (journal), 2011, 28 (2): 251–265, S2CID 14920600, arXiv:0911.0200可免费查阅, doi:10.1007/s11083-010-9169-x (英语) 
  34. ^ Gray 2014,Lemma 3.7.
  35. ^ 译名见 陈宏宾. 捉住黑暗中的微光,年輕數學家希多夫擊破[赫德米猜想]. UniMath. 2020-02-22 [2021-12-21]. (原始内容存档于2021-12-21). 
  36. ^ Tardif, C., Hedetniemi's conjecture, 40 years later [赫德米猜想四十年] (PDF), Graph Theory Notes of New York, 2008, 54: 46–57 [2021-12-21], MR 2445666, (原始内容 (PDF)存档于2021-07-12) (英语) .
  37. ^ 37.0 37.1 37.2 Dwight, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi's conjecture [以范畴论研究赫德米猜想所得的格], Discrete Mathematics英语Discrete Mathematics (journal), 1996, 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W可免费查阅 (英语) 
  38. ^ Hell & Nešetřil 2004,第125页.
  39. ^ 39.0 39.1 39.2 Gray 2014.
  40. ^ Brown et al. 2008.
  41. ^ 41.0 41.1 Hell & Nešetřil 2004,第7页.
  42. ^ Hahn & Tardif 1997,Observation 2.6.
  43. ^ Weisstein, Eric W. (编). Grötzsch Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  44. ^ Hahn & Tardif 1997,Proposition 3.14.
  45. ^ Gyárfás, A.; Jensen, T.; Stiebitz, M., On Graphs With Strongly Independent Color-Classes [论色类强独立之图], Journal of Graph Theory英语Journal of Graph Theory, 2004, 46 (1): 1–14, doi:10.1002/jgt.10165 
  46. ^ Hell & Nešetřil 2004,Proposition 3.4.
  47. ^ Hell & Nešetřil 2004,第96页.
  48. ^ Hell & Nešetřil 2004,第35页.
  49. ^ 49.0 49.1 Bodirsky 2007,§1.3.
  50. ^ Hell & Nešetřil 2004,§5.1.
  51. ^ Hell & Nešetřil 2004,Proposition 5.1.
  52. ^ Hell & Nešetřil 2004,§5.2.
  53. ^ Hell, Pavol; Nešetřil, Jaroslav. On the complexity of H-coloring [论染H色之复杂度]. Journal of Combinatorial Theory, Series B英语Journal of Combinatorial Theory, Series B. 1990, 48 (1): 92–110. doi:10.1016/0095-8956(90)90132-J可免费查阅 (英语). 
  54. ^ Hell & Nešetřil 2004,§5.3.
  55. ^ Hell & Nešetřil 2004,Theorem 5.14.
  56. ^ 56.0 56.1 Feder, Tomás; Vardi, Moshe Y. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory [单调单子SNP与约束满足之计算结构:藉Datalog与群论研究]. SIAM Journal on Computing英语SIAM Journal on Computing. 1998, 28 (1): 57–104 [2022-02-06]. doi:10.1137/S0097539794266766. (原始内容存档于2022-02-06) (英语). 
  57. ^ Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A. Tight bounds for graph homomorphism and subgraph isomorphism [图同态与子图同构之紧限界]. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM英语Society for Industrial and Applied Mathematics: 1643–1649. 2016. Bibcode:2015arXiv150703738F. ISBN 978-1-611974-33-1. arXiv:1507.03738可免费查阅 (英语). 
  58. ^ Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics [约束满足、有界树阔、有限变数逻辑]. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002): 310–326. 2002. doi:10.1007/3-540-46135-3_21 (英语). 
  59. ^ 59.0 59.1 59.2 Grohe, Martin, The complexity of homomorphism and constraint satisfaction problems seen from the other side [同态与约束满足之复杂度,自另一方面观之], Journal of the ACM, 2007, 54 (1): 1–es, S2CID 11797906, doi:10.1145/1206035.1206036 (英语) 
  60. ^ 60.0 60.1 Marx, Dániel, Can You Beat Treewidth? [可以胜过树阔乎?], Theory of Computing, 2010, 6: 85–112, doi:10.4086/toc.2010.v006a005可免费查阅 (英语) 

一般书目、解说

[编辑]

约束满足、泛代数

[编辑]

格论、范畴论

[编辑]