跳至內容

圖同態

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
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可免費查閱 (英語) 

一般書目、解說

約束滿足、泛代數

格論、範疇論