圖同態

圖論中,保持圖結構的映射

数学分支圖論中,圖同態(英語: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]

變式

其他同態亦可視作特殊的染色。給定圖 ,其頂點視為可用的顏色,每條邊表示某兩色「可兼容」,則  染色就是將相鄰頂點染成相容顏色的方案。此框架可容納許多圖染色的概念,將其表述為射向各類圖的同態。舉例如下:

無長路徑的定向

圖同態與圖定向英语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  (英语) 

一般書目、解說

約束滿足、泛代數

格論、範疇論