图同态

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

J5至C5的同态
花形蛇鲨图英语flower snarkJ5射向环图C5的同态,亦是到J5中央五个顶点所成子图的收缩,所以J5与其英语core (graph theory)C5“同态等价”。

同态是若干种图着色概念的推广,适用于表达一类重要的约束满足问题,如调度频段分配英语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]

变式

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

  • 循环染色英语Circular coloring可定义为至循环完全图英语circular clique[注 2]的同态,从而推广一般的染色,定义“分数”色数。[15]
  • 分数染色英语Fractional coloringb重染色英语Fractional coloring可定义成射向克内泽尔图英语Kneser graph的同态。[16]
  • T染色英语T-coloring的可用色集为自然数集 ,但另有给定某子集 ,禁止相邻顶点所染颜色之差属于 。此种染色对应往某幅无穷图的同态。[17]
  • 有向染色英语oriented coloring除禁止相邻顶点同色外,还限制不同颜色之间的所有边皆同向(例如由蓝至红)。此为映向有向图英语oriented graph的同态。[18]
  • L(2,1)染色英语L(2,1)-coloring以数表示颜色,要求距离为1(相邻)的顶点所染颜色之差至少为2,而距离为2的顶点染色之差至少为1。换言之,此为射向路图 的同态,且要求局部为单射,即在每个顶点的邻域上为单射。[19]

无长路径的定向

图同态与图定向英语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  (英语) 

一般书目、解说

约束满足、泛代数

格论、范畴论