圖同態
圖論中,保持圖結構的映射 / 維基百科,自由的 encyclopedia
數學分支圖論中,圖同態(英語: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),是將每點分裂為兩點,並將原圖每條邊換成交叉的兩條邊、。如此,可以定義函數將和皆映至,既是圖同態,也是覆疊對映。
圖同胚是另一個概念,不一定是同態。粗略而言,同胚要求是單射,但不必將邊映至邊,允許映至路徑。圖子式的要求更鬆。
核與回縮
若兩幅圖和有同態及,則稱兩者同態等價(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 coloring)與b重染色(英語: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):某圖可染色,若且唯若該圖有某定向,其中無長為的有向路徑(即作為子圖)。
與前一命題的分別在於,自至某圖的同態允許將兩頂點映至同處,但「長為的有向路徑」不允許重複頂點。
與約束滿足問題的關聯
範例
某些排程問題可用圖同態建模。[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 conjecture)(multiplicative graphs),此種圖的特性是,若乘積有同態至,則或兩者之一有同態至。如何識別積性圖是赫德米猜想(英語:Hedetniemi's conjecture)[35]的關鍵。[36][37]
圖與同態還組成範疇:圖是物件,而同態是態射。[38]範疇的始物件是空圖,終物件有一個頂點和一個自環。圖張量積(英語:tensor product of graphs)是範疇論積,指數圖(英語:Hedetniemi's conjecture)[註 6]是該範疇的指數物件(英語:exponential object)。換言之,自的同態與的同態自然地一一對應。[37][39]由於對任意圖,張量積與冪總有定義,圖範疇是笛卡兒閉範疇。同理,同態等價類組成的格實際上是海廷代數:按海廷代數的語言,前述的積稱為交運算,而前述的指數運算稱為蘊涵。[37][39]
對於有向圖,適用同樣的定義。同樣有是有向圖同態等價類之間的偏序,其與無向圖等價類的偏序有別,但後者是前者的子序,因為無向圖亦可視為有向圖,衹是其中每條有向邊皆與其反向成對出現。換言之,無向圖同態的定義,與雙向有向圖的同態並無區別。有向圖的序仍是分配格和海延代數,交與併的定義亦同上,但分別在於,該序並不稠密。亦有以有向圖為物件、同態為態射的範疇,照樣笛卡兒閉。[40][39]
不可比圖
同態預序下,許多圖不可比較。兩幅不可比圖(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)證明,對無向圖而言,無其他情況可馴順:
上述定理又稱為無向圖同態的「對分定理」(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]
參見
- 圖論術語
- 同態,其他代數結構的同一概念
- 圖重寫(英語:Graph rewriting)
- 中位圖(英語:Median graph),可定義成超立方圖(英語:hypercube graph)的收縮核
- 西多連科猜想(英語:Sidorenko's conjecture)
註
- 使該圖可染色的最小值。
- 取至為個頂點,相異兩點間有連邊若且唯若模運算時,大於某定值。
- 數學流傳(英語:Mathematical folklore),謂難以溯源或原創者並無正式投稿出版,但廣為研究者熟知的定理。
- 的頂點為,且對每個有一條邊自至。
- 為併不可約,意即推出或。對偶概念為交不可約。
- 指數圖(exponential graph)的頂點是函數,兩頂點連邊若且唯若對中任意兩個相鄰頂點,有與在中相鄰。
- 約束滿足問題中,以變數為頂點,兩變數有出現在同一個約束中則連邊,可得「原始約束圖」。此即以各約束為邊的超圖的原始圖(英語:primal graph)。
參考資料
- Hell & Nešetřil 2004,第27頁.
- Hell & Nešetřil 2004,第109頁.
- 引論見諸:Cameron (2006); Hahn & Tardif (1997); Hell & Nešetřil (2004). 由短至長排。
- Hahn & Tardif 1997,Observation 2.3.
- Godsil & Royle 2001,第115頁.
- Hell & Nešetřil 2004,第19頁.
- Hell & Nešetřil 2004,Proposition 1.31.
- Cameron 2006,Proposition 2.3;Hell & Nešetřil 2004,Corollary 1.32.
- Hell & Nešetřil 2004,第34頁.
- Cameron 2006,第4頁,Proposition 2.5.
- Cameron 2006,第1頁;Hell & Nešetřil 2004,Proposition 1.7.
- Hell & Nešetřil 2004,§1.7.
- Hell & Nešetřil 2004,Corollary 1.8.
- Hell & Nešetřil 2004,§6.1;Hahn & Tardif 1997,§4.4.
- Hell & Nešetřil 2004,§6.2;Hahn & Tardif 1997,§4.5.
- Hell & Nešetřil 2004,§6.3.
- Hell & Nešetřil 2004,§6.4.
- 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 (英語)
- Hell & Nešetřil 2004,第13–14頁.
- Hell & Nešetřil 2004,Proposition 1.20.
- Cameron 2006,第1頁.
- Hell & Nešetřil 2004,§1.8.
- Hell & Nešetřil 2004,第30–31頁.
- Hell & Nešetřil 2004,第31–32頁.
- Hell & Nešetřil 2004,第28頁,該書稱關係結構(relational structures)為「關係系統」(relational systems)。
- Hell & Nešetřil 2004,§3.1.
- Hell & Nešetřil 2004,Theorem 3.1.
- Hell & Nešetřil 2004,Theorem 3.30;Hahn & Tardif 1997,Theorem 2.33.
- 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 (英語)
- Hell & Nešetřil 2004,第192頁;Hahn & Tardif 1997,第127頁.
- Hell & Nešetřil 2004,Proposition 3.2,分配律載於Proposition 2.4;又見Hahn & Tardif 1997,Theorem 2.37.
- 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 (英語)
- 譯名見 陳宏賓. 捉住黑暗中的微光,年輕數學家希多夫擊破[赫德米猜想]. UniMath. 2020-02-22 [2021-12-21]. (原始內容存檔於2021-12-21).
- 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) (英語).
- 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 (英語)
- Hell & Nešetřil 2004,第125頁.
- Hahn & Tardif 1997,Observation 2.6.
- Weisstein, Eric W. (編). Grötzsch Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語).
- Hahn & Tardif 1997,Proposition 3.14.
- 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
- Hell & Nešetřil 2004,Proposition 3.4.
- Hell & Nešetřil 2004,第96頁.
- Hell & Nešetřil 2004,第35頁.
- Bodirsky 2007,§1.3.
- Hell & Nešetřil 2004,§5.1.
- Hell & Nešetřil 2004,Proposition 5.1.
- Hell & Nešetřil 2004,§5.2.
- 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 (英語).
- Hell & Nešetřil 2004,§5.3.
- Hell & Nešetřil 2004,Theorem 5.14.
- 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) (英語).
- 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 (英語).
- 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 (英語).
- 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 (英語)
- Marx, Dániel, Can You Beat Treewidth? [可以勝過樹闊乎?], Theory of Computing, 2010, 6: 85–112, doi:10.4086/toc.2010.v006a005 (英語)
一般書目、解說
- Cameron, P. Graph Homomorphisms, Combinatorics Study Group Notes [圖同態,組合研習小組講義] (PDF). 2006 [2022-02-12]. (原始內容 (PDF)存檔於2021-05-07) (英語).
- Hell, Pavol; Nešetřil, Jaroslav. Graphs and Homomorphisms [圖與同態]. Oxford Lecture Series in Mathematics and Its Applications 28. Oxford University Press. 2004 [2022-02-12]. ISBN 0-19-852817-5. (原始內容存檔於2021-05-06) (英語).
- Hahn, G.; Tardif, C. Graph homomorphisms: structure and symmetry [圖同態:結構與對稱]. Graph Symmetry: Algebraic Methods and Applications [圖對稱:代數方法及應用] (PDF). Springer. 1997: 107–166 [2022-02-12]. doi:10.1007/978-94-015-8937-6_4. (原始內容 (PDF)存檔於2021-07-11) (英語).
- Godsil, C.; Royle, G. 6. Homomorphisms [6、同態]. Algebraic Graph Theory [代數圖論]. Graduate Texts in Mathematics 207. Springer–Verlag New York. 2001. ISBN 978-1-4613-0163-9. doi:10.1007/978-1-4613-0163-9 (英語).
約束滿足、泛代數
- Bodirsky, M. Graph Homomorphisms and Universal Algebra, Course Notes [圖同態與泛代數,講義] (PDF). 2007 [2022-02-12]. (原始內容 (PDF)存檔於2022-05-01) (英語).
- Hell, Pavol; Nešetřil, Jaroslav. Colouring, constraint satisfaction, and complexity [染色、約束滿足、複雜度] (PDF). Computer Science Review. 2008, 2 (3): 143–163 [2022-02-12]. doi:10.1016/j.cosrev.2008.10.003. (原始內容 (PDF)存檔於2017-07-06) (英語).
格論、範疇論
- Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. Graphs of morphisms of graphs [圖態射之圖]. Electronic Journal of Combinatorics(英語:Electronic Journal of Combinatorics). 2008, 15 (1): A1 [2022-02-12]. doi:10.37236/919 . (原始內容存檔於2021-07-11) (英語).
- Gray, C. T. The Digraph Lattice [有向圖之格] (PDF). 2014 [2022-02-12]. (原始內容 (PDF)存檔於2022-01-20) (英語).