圖同態

數學分支圖論中，圖同態（英語：graph homomorphism）是兩幅圖之間保結構的對映。具體而言，該對映將某圖的各頂點映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。

關於兩幅圖如何算是「完全一樣」，請見「圖同構」。

關於允許將邊映成路徑的對映，請見「圖同胚」。

由花形蛇鯊圖（英語：flower snark）J₅射向環圖C₅的同態，亦是到J₅中央五個頂點所成子圖的收縮，所以J₅與其核（英語：core (graph theory)）C₅「同態等價」。

同態是若干種圖著色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、頻段分配（英語：frequency assignment）問題。^[1]同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的預序關係、分配格結構、範疇結構（分為無向圖範疇與有向圖範疇兩種）。^[2]欲尋找任意兩圖間的同態，而無額外條件，則現時所知的計算複雜度高得不切實際，但對於某些特定類別的圖，已知有多項式時間演算法。此類問題易解與否，兩者的分野，是活躍的研究方向。^[3]

定義

本條目中，除非另有聲明，否則「圖」皆為有限無向圖，允許自環，但無重邊（兩點間連多於一條邊）。自${\displaystyle G=(V(G),E(G))}$至另一圖${\displaystyle H=(V(H),E(H))}$的圖同態^[4]${\displaystyle f}$，記作

${\displaystyle f:G\to H,}$

是頂點集${\displaystyle V(G)}$至${\displaystyle V(H)}$的函式，其將${\displaystyle G}$每條邊的兩端分別映至${\displaystyle H}$某邊的兩端。以符號表示：對${\displaystyle V(G)}$中每對頂點${\displaystyle u,v}$，若${\displaystyle \{u,v\}\in E(G)}$，則${\displaystyle \{f(u),f(v)\}\in E(H)}$。若存在${\displaystyle G}$至${\displaystyle H}$的同態，則稱${\displaystyle G}$同態於（homomorphic to）${\displaystyle H}$，或可染${\displaystyle H}$色（${\displaystyle H}$-colourable），常簡記為：

${\displaystyle G\to H.}$

上述定義可引伸至有向圖，此時，${\displaystyle f:G\to H}$為同態的條件是，${\displaystyle G}$中每條有向邊${\displaystyle (u,v)}$的像${\displaystyle (f(u),f(v))}$，仍是${\displaystyle H}$的有向邊。

自${\displaystyle G}$至${\displaystyle H}$有單同態（將不同頂點映至不同頂點），若且唯若${\displaystyle G}$為${\displaystyle H}$的子圖。若同態${\displaystyle f:G\to H}$為對射（兩圖頂點集的一一對應），且其逆${\displaystyle f^{-1}}$亦是圖同態，則${\displaystyle f}$為圖同構。^[5]

圖的覆疊對映（英語：Covering graph）是一類特殊的圖同態，相當於將圖視為拓撲空間（英語：Graph (topology)）時，拓撲學上的覆疊對映，其定義及性質亦是類似：^[6]圖覆疊是滿同態（即作為對應域的圖，其每個頂點皆為定義域某頂點的像），且局部為對射，即若限制到每個頂點的鄰域（英語：neighbourhood (graph theory)），則為對射。舉例，圖的典範雙重覆疊（英語：bipartite double cover），是將每點${\displaystyle v}$分裂為${\displaystyle v_{0},v_{1}}$兩點，並將原圖每條邊${\displaystyle uv}$換成交叉的兩條邊${\displaystyle u_{0}v_{1}}$、${\displaystyle u_{1}v_{0}}$。如此，可以定義函式將${\displaystyle v_{0}}$和${\displaystyle v_{1}}$皆映至${\displaystyle v}$，既是圖同態，也是覆疊對映。

圖同胚是另一個概念，不一定是同態。粗略而言，同胚要求是單射，但不必將邊映至邊，允許映至路徑。圖子式的要求更鬆。

核與回縮

K₇，七個頂點的完全圖，一種核圖

主條目：核圖（英語：Core (graph theory)）

若兩幅圖${\displaystyle G}$和${\displaystyle H}$有同態${\displaystyle G\to H}$及${\displaystyle H\to G}$，則稱兩者同態等價（homomorphically equivalent）。^[4]該些對映不必單，也不必滿。例如，完全二部圖${\displaystyle K_{2,2}}$與${\displaystyle K_{3,3}}$同態等價，因為可將${\displaystyle K_{2,2}}$左部兩個頂點映到${\displaystyle K_{3,3}}$左部同一個頂點，其右部的兩個頂點映到${\displaystyle K_{3,3}}$右部一個頂點，同樣有${\displaystyle K_{3,3}\to K_{2,2}}$的同態。

收縮對映（retraction）是自圖${\displaystyle G}$至其子圖${\displaystyle H}$的同態${\displaystyle r}$，且對${\displaystyle H}$中每個頂點${\displaystyle v}$有${\displaystyle r(v)=v}$。若有此種對映，則${\displaystyle H}$稱為${\displaystyle G}$的收縮核（retract）。^[7]

核圖（core）沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。^[8]每幅圖${\displaystyle G}$皆同態等價於唯一的核圖（不辨同構之別），稱為${\displaystyle G}$的核（the core of ${\displaystyle G}$）。^[9]此結論對無窮圖不一定成立^[10]，但對（有限的）有向圖可以照套用同樣的定義，每幅有向圖同態等價於唯一的核圖。圖（或有向圖）的核，必為原圖某個收縮核，以及某個匯出子圖。^[7]

舉例，完全圖${\displaystyle K_{n}}$及奇環（奇數條邊的迴圈圖）皆屬核圖。若${\displaystyle G}$可染三色，且有三角形（即子圖${\displaystyle K_{3}}$），則${\displaystyle G}$同態等價於${\displaystyle K_{3}}$，原因是${\displaystyle G}$的三染色，下節將說明相當於同態${\displaystyle G\to K_{3}}$，且另一方面，任意子圖皆有同態嵌入到${\displaystyle G}$，故有${\displaystyle K_{3}\to G}$。如此，證畢${\displaystyle K_{3}}$為所有此種${\displaystyle G}$的核。與之相似，每幅非空二部圖（有至少一條邊）皆等價於${\displaystyle K_{2}}$。^[11]

與染色的關聯

對正整數${\displaystyle k}$，圖${\displaystyle G}$的${\displaystyle k}$染色是將每個頂點塗${\displaystyle k}$色之一，使每條邊的兩端都不同色。此種染色，與自${\displaystyle G}$至完全圖${\displaystyle K_{k}}$的同態，兩類物件一一對應^[12]，因為${\displaystyle K_{k}}$的各頂點對應${\displaystyle k}$種色，且若${\displaystyle c_{1},c_{2}}$為顏色，則其於圖${\displaystyle K_{k}}$相鄰若且唯若${\displaystyle c_{1}\neq c_{2}}$。於是，某函式是${\displaystyle G}$至${\displaystyle K_{k}}$的同態，若且唯若該函式將${\displaystyle G}$中相鄰的頂點映至不同顏色（即${\displaystyle k}$染色的定義）。換言之，${\displaystyle G}$可染${\displaystyle k}$色等價於可染${\displaystyle K_{k}}$色。^[12]

若有同態${\displaystyle G\to H}$及${\displaystyle H\to K_{k}}$，則兩者複合可得同態${\displaystyle G\to K_{k}}$。^[13]所以，若${\displaystyle H}$可染${\displaystyle k}$色，且有同態${\displaystyle G\to H}$，則${\displaystyle G}$同樣可染${\displaystyle k}$色。因此，${\displaystyle G\to H}$推出${\displaystyle \chi (G)\leq \chi (H)}$，其中${\displaystyle \chi }$表示圖的色數^{[註 1]}。^[14]

變式

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

• 迴圈染色（英語：Circular coloring）可定義為至迴圈完全圖（英語：circular clique）^{[註 2]}的同態，從而推廣一般的染色，定義「分數」色數。^[15]
• 分數染色（英語：Fractional coloring）與b重染色（英語：Fractional coloring）可定義成射向克內澤爾圖（英語：Kneser graph）的同態。^[16]
• T染色（英語：T-coloring）的可用色集為自然數集${\displaystyle \mathbb {N} }$，但另有給定某子集${\displaystyle T\subseteq \mathbb {N} }$，禁止相鄰頂點所染顏色之差屬於${\displaystyle T}$。此種染色對應往某幅無窮圖的同態。^[17]
• 有向染色（英語：oriented coloring）除禁止相鄰頂點同色外，還限制不同顏色之間的所有邊皆同向（例如由藍至紅）。此為映向有向圖的同態。^[18]
• L(2,1)染色（英語：L(2,1)-coloring）以數表示顏色，要求距離為1（相鄰）的頂點所染顏色之差至少為2，而距離為2的頂點染色之差至少為1。換言之，此為射向路圖${\displaystyle P_{n}}$之補的同態，且要求局部為單射，即在每個頂點的鄰域上為單射。^[19]

無長路徑的定向

主條目：高洛伊-哈塞-羅伊-維塔韋爾定理（英語：Gallai–Hasse–Roy–Vitaver theorem）

圖同態與圖定向（英語：Orientation (graph theory)）也有關。無向圖${\displaystyle G}$的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖${\displaystyle K_{k}}$可定向成「遞移迴圈賽圖（英語：Tournament (graph theory)）」${\displaystyle {\overrightarrow {T_{k}}}}$，其頂點為${\displaystyle 1,2,\ldots ,k}$，對所有${\displaystyle i<j}$有（有向）邊自${\displaystyle i}$指向${\displaystyle j}$。給定${\displaystyle G}$的定向與${\displaystyle H}$的定向之間的同態，忘掉定向即得本來無向圖之間的同態。另一方面，給定無向圖同態${\displaystyle G\to H}$，${\displaystyle H}$任何定向${\displaystyle {\overrightarrow {H}}}$可以拉回到${\displaystyle G}$的定向${\displaystyle {\overrightarrow {G}}}$，使原同態亦是${\displaystyle {\overrightarrow {G}}\to {\overrightarrow {H}}}$的有向圖同態。綜上，無向圖${\displaystyle G}$可染${\displaystyle k}$色（即有同態至${\displaystyle K_{k}}$），若且唯若${\displaystyle G}$有某定向，具有至${\displaystyle {\overrightarrow {T_{k}}}}$的同態。^[20]

有定理流傳^{[註 3]}，對每個${\displaystyle k}$，有向圖${\displaystyle G}$有同態至${\displaystyle {\overrightarrow {T_{k}}}}$，若且唯若${\displaystyle k+1}$個頂點的有向路徑圖（英語：path graph）${\displaystyle {\overrightarrow {P_{k+1}}}}$^{[註 4]}無同態至${\displaystyle G}$。^[21]

因此，某圖可${\displaystyle k}$染色，若且唯若其有某定向，不容任何自${\displaystyle {\overrightarrow {P_{k+1}}}}$至該定向的同態。此命題可加強成

高洛伊-哈塞-羅伊-維塔韋爾定理（英語：Gallai–Hasse–Roy–Vitaver theorem）：某圖可${\displaystyle k}$染色，若且唯若該圖有某定向，其中無長為${\displaystyle k}$的有向路徑（即${\displaystyle {\overrightarrow {P_{k+1}}}}$作為子圖）。

與前一命題的分別在於，自${\displaystyle {\overrightarrow {P_{k+1}}}}$至某圖的同態允許將兩頂點映至同處，但「長為${\displaystyle k}$的有向路徑」不允許重複頂點。

與約束滿足問題的關聯

範例

圖${\displaystyle H}$，表示一週中不相鄰的日子，同構於環${\displaystyle C_{7}}$的補圖，亦同構於環狀團（英語：circular clique）${\displaystyle K_{7/2}}$

某些排程問題可用圖同態建模。^[22][23]設學校已知各學生所選科目，要編排今學期各專題討論班的時間，使同一學生所選的討論班時間不致太近。考慮圖${\displaystyle G}$以各科為頂點，若兩科有共同學生則連邊，而圖${\displaystyle H}$以各課節為頂點，若兩個時段隔足夠遠則連邊。舉例若限制時間表須每週迴圈，且每個學生所選的討論班須相隔一日，則對應的${\displaystyle H}$是環${\displaystyle C_{7}}$的補圖。如此，${\displaystyle G\to H}$的圖同態，就是討論班對應到課節的合適方案。^[22]欲添加額外條件，如禁止學生同時於週五與週一有討論班，衹需從${\displaystyle H}$刪掉相應的邊。

無線電的頻段分配（英語：frequency allocation）問題簡述如下：無線網路中，有若干發訊機，要為每部機組態一個頻率，供其發訊。為免干擾，地理位置較近的發訊機應選用相差較遠的頻率。若將條件中「地理較近」與「頻率較遠」簡化至非黑即白，則合適的分配方案又可視為圖同態${\displaystyle G\to H}$。圖${\displaystyle G}$的頂點為各發訊機，邊表示兩機地理上接近；圖${\displaystyle H}$以各頻段為頂點，邊則表示兩頻段相隔夠遠。雖然此模型甚為簡化，但是尚有保留一點彈性：若有兩機相隔較遠，但仍因地形導致可能干擾，則在${\displaystyle G}$中加邊即可。反之，若有兩機永不在同一時段發訊，則不論其地理位置是否靠近，皆可從${\displaystyle G}$中刪去該邊。同樣，或許有某些頻率相差頗遠，但是互為諧波，導致干擾，則將該邊自${\displaystyle H}$移除即可^[24]

前述模型經簡化，若要實際應用，許多問題仍待解決。^[25]約束滿足問題是圖同態問題的推廣，能表達更多種條件（例如個體偏好，或重複分配次數有上限），從而建立更實際的數學模型。

抽象觀點

數理邏輯或泛代數中，圖與有向圖屬關係結構的特例，即集合配備若干關係。有向圖就是基集（頂點集）之上有獨一個二元關係（鄰接關係）。^[26][3]如是觀之，圖作為關係結構的同態，按抽象代數的同態定義，等同於本文的圖同態。一般而言，欲尋找自某關係結構至另一關係結構的同態，屬於約束滿足問題（constraint satisfaction problem, CSP）。圖的特例可作為第一步，幫助理解更複雜的CSP。許多尋找圖同構的演算法，包括回溯、約束傳播（英語：constraint propagation）、局部搜尋（英語：Local search (constraint satisfaction)），通用於各種CSP。^[3]

給定圖${\displaystyle G}$、${\displaystyle H}$，問是否有同態${\displaystyle G\to H}$，相當於僅得一類約束的CSP實例^[3]：CSP的「變數」是${\displaystyle G}$的頂點，每個變數的「域」（可取值的範圍）是${\displaystyle H}$的頂點集。「賦值」是一個函式，將逐個變數映至域的元素，即函式${\displaystyle f:V(G)\to V(H)}$。${\displaystyle G}$的每條邊（或有向邊）${\displaystyle (u,v)}$對應一個「約束」${\displaystyle ((u,v),E(H))}$，限制賦值函式將邊${\displaystyle (u,v)}$映至關係${\displaystyle E(H)}$中，即映至${\displaystyle H}$的某邊。CSP的「解」是滿足全體約束的賦值，故前述CSP的解正是自${\displaystyle G}$至${\displaystyle H}$的同態。

同態的結構

同態的複合仍是同態^[13]，故可知圖的${\displaystyle \to }$關係具遞移性，又顯然自反，所以其為圖之間的預序。^[27]同態等價意義下，記${\displaystyle G}$所屬等價類為${\displaystyle [G]}$，每個等價類有唯一的核圖為其代表。關係${\displaystyle \to }$定義該些等價類之間的偏序，即同態等價類構成一個偏序集。^[28]

以${\displaystyle G<H}$表示${\displaystyle G}$有同態至${\displaystyle H}$，但反之則不然。如此定義的序${\displaystyle <}$稠密（英語：dense order），即對任意（無向）圖${\displaystyle G,H}$，若${\displaystyle G<H}$，則存在第三幅圖${\displaystyle K}$使${\displaystyle G<K<H}$，除非是平凡反例${\displaystyle G=K_{0}}$或${\displaystyle G=K_{1}}$。^[29][30]例如，任意兩幅整數階完全圖（除${\displaystyle K_{0},K_{1},K_{2}}$外）之間，必有無窮多幅環狀完全圖（英語：circular clique），相當於整階數之間的有理數階數。^[31]

同態等價類的偏序集是分配格，併${\displaystyle [G]\lor [H]}$是互斥併${\displaystyle [G\sqcup H]}$，而交${\displaystyle [G]\land [H]}$是圖張量積（英語：tensor product of graphs）${\displaystyle [G\times H]}$，其定義不取決於等價類中所選的代表${\displaystyle G,H}$。^[32]此格中，併不可約元（英語：join-irreducible）^{[註 5]}正好是連通圖，證明方式是留意同態衹會將連通圖映到目標的一個連通分支中。^[33][34]交不可約元（英語：meet-irreducible）^{[註 5]}正好是積性圖（英語：Hedetniemi's conjecture）（multiplicative graphs），此種圖${\displaystyle K}$的特性是，若乘積${\displaystyle G\times H}$有同態至${\displaystyle H}$，則${\displaystyle G}$或${\displaystyle H}$兩者之一有同態至${\displaystyle H}$。如何識別積性圖是赫德米猜想（英語：Hedetniemi's conjecture）^[35]的關鍵。^[36][37]

圖與同態還組成範疇：圖是物件，而同態是態射。^[38]範疇的始物件是空圖${\displaystyle K_{0}}$，終物件有一個頂點和一個自環。圖張量積（英語：tensor product of graphs）是範疇論積，指數圖（英語：Hedetniemi's conjecture）^{[註 6]}是該範疇的指數物件（英語：exponential object）。換言之，自${\displaystyle G\times H\to K}$的同態與${\displaystyle H\to K^{G}}$的同態自然地一一對應。^[37][39]由於對任意圖${\displaystyle G,H}$，張量積${\displaystyle G\times H}$與冪${\displaystyle H^{G}}$總有定義，圖範疇是笛卡兒閉範疇。同理，同態等價類組成的格實際上是海廷代數：按海廷代數的語言，前述的積稱為交運算${\displaystyle \land }$，而前述的指數運算稱為蘊涵${\displaystyle \Rightarrow }$。^[37][39]

對於有向圖，適用同樣的定義。同樣有${\displaystyle \to }$是有向圖同態等價類之間的偏序，其與無向圖等價類的偏序${\displaystyle \to }$有別，但後者是前者的子序，因為無向圖亦可視為有向圖，衹是其中每條有向邊${\displaystyle (u,v)}$皆與其反向${\displaystyle (v,u)}$成對出現。換言之，無向圖同態的定義，與雙向有向圖的同態並無區別。有向圖的${\displaystyle \to }$序仍是分配格和海延代數，交與併的定義亦同上，但分別在於，該序並不稠密。亦有以有向圖為物件、同態為態射的範疇，照樣笛卡兒閉。^[40][39]

不可比圖

格勒奇圖（英語：Grötzsch graph），與${\displaystyle K_{3}}$不可比

同態預序下，許多圖不可比較。兩幅不可比圖（incomparable graphs）之間，並無自任意一幅至另一幅的同態。^[41]欲構造此種圖，可考慮圖的奇圍長，即最短的奇環長度。奇圍長可等價地說成最小的奇數${\displaystyle g}$，使${\displaystyle g}$個頂點的迴圈圖${\displaystyle C_{g}}$有同態至${\displaystyle G}$。由此定義，若${\displaystyle G\to H}$，則${\displaystyle G}$的奇圍長大於或等於${\displaystyle H}$的奇圍長。^[42]

另一方面，前節已證若${\displaystyle G\to H}$，則${\displaystyle G}$的色數小於或等於${\displaystyle H}$的色數。所以，若${\displaystyle G}$的奇圍長及色數皆嚴格大於${\displaystyle H}$，則${\displaystyle G}$和${\displaystyle H}$不可比較。^[41] 舉例，格勒奇圖（英語：Grötzsch graph）色數為${\displaystyle 4}$，且無三角形（圍長${\displaystyle 4}$，奇圍長${\displaystyle 5}$）^[43]，所以與三角形${\displaystyle K_{3}}$不可比。

有幾類圖的奇圍長和色數可取任意大，如克內澤爾圖（英語：Kneser graph）^[44]與廣義梅切爾斯基圖（英語：Mycielskian）^[45]。如此一類圖，若使其兩參數同時遞增，排成一列，則有無窮多幅不可比圖（同態預序下的反鏈）。^[46] 同態預序稠密（英語：dense order）等其他性質，亦可利用此類圖證明。^[47]此外，可構造同時具大色數和大圍長（不僅是奇圍長）的圖，但較複雜，見圍長 (圖論) § 圍長與圖染色。

有向圖之中，更易找到不可比圖。例如，考慮有向環${\displaystyle {\overrightarrow {C_{n}}}}$，頂點為${\displaystyle 1,2,\ldots ,n}$，有向邊自${\displaystyle i}$至${\displaystyle i+1}$（對${\displaystyle i=1,2,\ldots ,n-1}$各一），及自${\displaystyle n}$至${\displaystyle 1}$。對於${\displaystyle n,k\geq 3}$，${\displaystyle {\overrightarrow {C_{n}}}}$至${\displaystyle {\overrightarrow {C_{k}}}}$有同態若且唯若${\displaystyle n}$為${\displaystyle k}$的倍數。所以，當${\displaystyle p}$取質數值時，${\displaystyle {\overrightarrow {C_{p}}}}$兩兩不可比。^[48]

計算複雜度

圖同態問題是給定一對圖${\displaystyle (G,H)}$，求自${\displaystyle G}$至${\displaystyle H}$的圖同態。對應的決定性問題問是否存在此種解。一般情況下，即詢問的實例${\displaystyle (G,H)}$不受額外限制的情況下，此決定性問題為NP完全。^[49]若限制詢問的範圍，衹限從某類圖中選出${\displaystyle G}$或${\displaystyle H}$，則可得多種不同的問題，其中有些較易求解。限制左邊${\displaystyle G}$和限制右邊${\displaystyle H}$相比，適用的方法相去甚遠，但兩者似乎有一共同特點：難易情況之間似乎有明確的分界，此分界或者已獲證，或有論文猜想如此。

至給定圖的同態

圖同態問題若固定右邊的圖${\displaystyle H}$不變，則稱為染${\displaystyle H}$色問題。${\displaystyle H}$為完全圖${\displaystyle K_{k}}$時，化成染k色問題，在${\displaystyle k=0,1,2}$時，可於多項式時間內求解，但其餘情況則是NP完全。^[50]${\displaystyle k=2}$的情況相當於問圖${\displaystyle G}$可否染${\displaystyle K_{2}}$色，即是否二部圖，此問題可在線性時間內求解。更一般地，衹要${\displaystyle H}$是二部圖就有同一結論：可染${\displaystyle H}$色等價於可染${\displaystyle K_{2}}$色，即可染二色，故此種情況同樣易判斷。可染${\displaystyle K_{0}}$色和可染${\displaystyle K_{1}}$色分別等價於無頂點和無邊，亦易判斷。^[51]帕沃爾·黑爾（英語：Pavol Hell）和雅羅斯拉夫·內舍特日爾（英語：Jaroslav Nešetřil）證明，對無向圖而言，無其他情況可馴順：

（黑爾-內舍特日爾定理，1990年）若${\displaystyle H}$為二部圖，則染${\displaystyle H}$色問題屬於P，但其餘情況則為NP完全。^[52][53]

上述定理又稱為無向圖同態的「對分定理」（dichotomy theorem），因為將染${\displaystyle H}$色問題分成NP完全與P兩類，而無居中（英語：NP-intermediate）情況。有向圖情況較複雜，此時問題等價於刻畫看似更一般的約束滿足問題的複雜度（英語：Complexity of constraint satisfaction）^[54]：有向圖的染${\displaystyle H}$色問題，與允許各種約束條件的CSP相比，同樣多姿多彩，而不失一般性。^[55][56]嚴格而言，定義（有限）約束語言（constraint language，或稱模板template）${\displaystyle \Gamma }$為一個有限的取值域，其上配備有限多種關係，然後以${\displaystyle {\mathsf {CSP}}(\Gamma )}$表示約束衹能選自${\displaystyle \Gamma }$的一類約束滿足問題，則有以下定理：

（費德、瓦迪（英語：Moshe Y. Vardi），1998年）對任意約束語言${\displaystyle \Gamma }$，必有某幅有向圖${\displaystyle H}$，使${\displaystyle {\mathsf {CSP}}(\Gamma )}$在多項式時間歸約意義下等價於染${\displaystyle H}$色問題。^[56]

直觀理解，定理意味著任何演算法技巧或複雜度結論，若適用於一般有向圖${\displaystyle H}$的染${\displaystyle H}$色問題，則可套用至一般CSP。考慮將黑爾-內舍特日爾定理擴展至有向圖。由上述定理，該推廣等價於有關CSP對分的費德-瓦迪猜想（又稱CSP猜想、對分猜想），即斷言對任意約束語言${\displaystyle \Gamma }$，${\displaystyle {\mathsf {CSP}}(\Gamma )}$或屬NP完全，或屬P。^[49]此猜想於2017年由德米特里·祖克（Dmitry Zhuk）與安德烈·布拉托夫（Andrei Bulatov）分別獨立證出，故有以下推論：

（布拉托夫2017年；祖克2017年）給定${\displaystyle H}$時，有向圖的染${\displaystyle H}$色問題或屬P，或屬NP完全。

自給定族的同態

若左輸入${\displaystyle G}$為給定，則圖同態問題有暴力解法，即窮舉${\displaystyle G}$的各個頂點在${\displaystyle H}$中的像，複雜度僅為${\displaystyle {\mathcal {O}}\left(|V(H)|^{|V(G)|}\right)}$，已是輸入${\displaystyle H}$的多項式函式。^[57]換言之，限制${\displaystyle G}$的大小時，問題顯然屬P，但仍可改為研究另一課題：除大小之外，是否其他限制可施加於${\displaystyle G}$，使圖同態問題可於多項式時間內求解？

研究表明，關鍵性質是樹闊（英語：treewidth），此參數衡量一幅圖有多似一棵樹。若${\displaystyle G}$的樹闊至多為${\displaystyle k}$，而${\displaystyle H}$為任意圖，則利用標準的動態規劃方法，可於${\displaystyle |V(H)|^{{\mathcal {O}}(k)}}$時間內求解圖同態問題。實際甚至衹需假設${\displaystyle G}$的核的樹闊不逾${\displaystyle k}$，而無需知道其核為何。^[58][59]

該${\displaystyle |V(H)|^{{\mathcal {O}}(k)}}$演算法中，複雜度的指數可能無法再壓低太多：若指數時間假設（英語：exponential time hypothesis）^{[註 7]}（ETH）為真，則不存在時間複雜度為${\displaystyle |V(H)|^{o(\mathrm {tw} (G)/\log \mathrm {tw} (G))}}$的演算法。即使限制${\displaystyle G}$衹能取值為某一族圖，衹要該族圖的樹闊無上界，則仍有同樣結論。^[60]同樣假設下，幾乎沒有其他性質使問題可於多項式時間內求解，具體含義如下：

（格羅厄（英語：Martin Grohe））假定ETH，並給定由圖組成的可計算族${\displaystyle {\mathcal {G}}}$。考慮輸入為${\displaystyle (G,H)}$，且${\displaystyle G\in {\mathcal {G}}}$的圖同態問題。此問題屬P若且唯若${\displaystyle {\mathcal {G}}}$中各圖之核的樹闊有界。^[59]

或考慮有所取捨，允許複雜度高度依賴${\displaystyle G}$，換取複雜度與${\displaystyle H}$的關係僅為固定的多項式。與前段類似，若${\displaystyle G}$的取值範圍中，核的樹闊有界，則此目標可以實現，但若${\displaystyle G}$的取值範圍不滿足該條件，則無法達成。^[59]利用帶參數複雜度（英語：parameterized complexity）術語，上述成果可覆述為：${\displaystyle {\mathcal {G}}}$中的同態問題，以${\displaystyle G}$的邊數為參數，呈現對分現象。若${\displaystyle {\mathcal {G}}}$中各圖之核的樹闊有上界，則該問題為固定參數可馴順（英語：fixed-parameter tractable），否則為W[1]（英語：Parameterized complexity）完全。

同一命題對其他關係結構亦成立。換言之，其適用於一般的約束滿足問題，不過需要限制各項約束涉及的變數數有上界，即關係的元數有上界（以圖為例，僅得元數為2的關係）。此時，關鍵參數為原始約束圖（英語：primal constraint graph）^{[註 8]}的樹闊。^[60]

參見

• 圖論術語
• 同態，其他代數結構的同一概念
• 圖重寫（英語：Graph rewriting）
• 中位圖（英語：Median graph），可定義成超立方圖（英語：hypercube graph）的收縮核
• 西多連科猜想（英語：Sidorenko's conjecture）