圖同態

数学分支圖論中，圖同態（）是兩幅图之間保結構的映射。具體而言，該映射將某圖的各顶点映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。

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

定義
本條目中，除非另有聲明，否則「圖」皆為有限無向圖，允許自环，但無重边（兩點間連多於一條邊）。自G = (V(G), E(G))至另一圖H = (V(H), E(H))的圖同態f，記作
: f : G \to H,
是頂點集V(G)至V(H)的函數，其將G每條邊的兩端分別映至H某邊的兩端。以符號表示：對V(G)中每對頂點u, v，若\{u, v\} \in E(G)，則\{f(u), f(v)\} \in E(H)。若存在G至H的同態，則稱G同態於（）H，或可染H色（），常簡記為：
: G \to H.

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

自G至H有單同態（將不同頂點映至不同頂點），當且僅當G為H的子圖。若同態f:G \to H為双射（兩圖頂點集的一一對應），且其逆f^{-1}亦是圖同態，則f為图同构。

是一類特殊的圖同態，相當於將圖時，拓撲學上的覆疊映射，其定義及性質亦是類似：圖覆疊是滿同態（即作為陪域的圖，其每個頂點皆為定義域某頂點的像），且局部為雙射，即若限制到每個頂點的，則為雙射。舉例，圖的，是將每點v分裂為v_0, v_1兩點，並將原圖每條邊uv換成交叉的兩條邊u_0v_1、u_1 v_0。如此，可以定義函數將v_0和v_1皆映至v，既是圖同態，也是覆疊映射。

圖同胚是另一個概念，不一定是同態。粗略而言，同胚要求是單射，但不必將邊映至邊，允許映至路徑。图子式的要求更鬆。
核與回縮
若兩幅圖G和H有同態G\to H及H \to G，則稱兩者同態等價（）。

無長路徑的定向
圖同態與也有關。無向圖G的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖K_k可定向成「遞移」\overrightarrow{T_k}，其頂點為1, 2, \ldots, k，對所有i 有（有向）邊自i指向j。給定G的定向與H的定向之間的同態，忘掉定向即得本來無向圖之間的同態。另一方面，給定無向圖同態G \to H，H任何定向\overrightarrow{H}可以拉回到G的定向\overrightarrow{G}，使原同態亦是\overrightarrow{G} \to \overrightarrow{H}的有向圖同態。綜上，無向圖G可染k色（即有同態至K_k），當且僅當G有某定向，具有至\overrightarrow{T_k}的同態。

有定理流傳，對每個k，有向圖G有同態至\overrightarrow{T_k}，當且僅當k+1個頂點的有向\overrightarrow{P_{k+1}}{{註|\overrightarrow{P_n}的頂點為1, 2, \ldots, n，且對每個i = 1, 2, \ldots, n-1有一條邊自i至i+1。}}無同態至G。

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

：某圖可k染色，當且僅當該圖有某定向，其中無長為k的有向路徑（即\overrightarrow{P_{k+1}}作為子圖）。

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

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

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

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

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

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

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

以G 表示G有同態至H，但反之則不然。如此定義的序 ，即對任意（無向）圖G, H，若G ，則存在第三幅圖K使G ，除非是平凡反例G = K_0或G = K_1。例如，任意兩幅整數階完全圖（除K_0, K_1, K_2外）之間，必有無窮多幅，相當於整階數之間的有理數階數。

同態等價類的偏序集是分配格，併[G]\lor[H]是互斥併[G \sqcup H]，而交[G] \land [H]是[G\times H]，其定義不取決於等價類中所選的代表G, H。此格中，正好是連通圖，證明方式是留意同態衹會將連通圖映到目標的一個連通分支中。正好是（），此種圖K的特性是，若乘積G \times H有同態至H，則G或H兩者之一有同態至H。如何識別積性圖是的關鍵。

圖與同態還組成範疇：圖是物件，而同態是態射。範疇的始物件是空圖K_0，終物件有一個頂點和一個自环。是範疇論積，是該範疇的。換言之，自G \times H\to K的同態與H \to K^G的同態自然地一一對應。，所以與三角形K_3不可比。

有幾類圖的奇圍長和色數可取任意大，如與。如此一類圖，若使其兩參數同時遞增，排成一列，則有無窮多幅不可比圖（同態預序下的反鏈）。
同態預序等其他性質，亦可利用此類圖證明。此外，可構造同時具大色數和大圍長（不僅是奇圍長）的圖，但較複雜，見。

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

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

至給定圖的同態
圖同態問題若固定右邊的圖H不變，則稱為染H色問題。H為完全圖K_k時，化成染k色問題，在k = 0, 1, 2時，可於多項式時間內求解，但其餘情況則是NP完全。k = 2的情況相當於問圖G可否染K_2色，即是否二部圖，此問題可在線性時間內求解。更一般地，衹要H是二部圖就有同一結論：可染H色等價於可染K_2色，即可染二色，故此種情況同樣易判斷。可染K_0色和可染K_1色分別等價於無頂點和無邊，亦易判斷。和證明，對無向圖而言，無其他情況可馴順：

（黑爾-內舍特日爾定理，1990年）若H為二部圖，則染H色問題屬於P，但其餘情況則為NP完全。

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

（费德、，1998年）對任意約束語言\Gamma，必有某幅有向圖H，使\mathsf{CSP}(\Gamma)在多项式时间归约意義下等價於染H色問題。換言之，限制G的大小時，問題顯然屬P，但仍可改為研究另一課題：除大小之外，是否其他限制可施加於G，使圖同態問題可於多項式時間內求解？

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

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

（）假定，並給定由圖組成的可計算族\mathcal{G}。考慮輸入為(G,H)，且G \in \mathcal{G}的圖同態問題。此問題屬P當且僅當\mathcal{G}中各圖之核的樹闊有界。

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

同一命題對其他關係結構亦成立。換言之，其適用於一般的約束滿足問題，不過需要限制各項約束涉及的變量數有上界，即關係的元數有上界（以圖為例，僅得元數為2的關係）。此時，關鍵參數為的樹闊。

參見

• 图论术语
• 同态，其他代數結構的同一概念

*

• ，可定義成的收縮核

*

註
參考資料
一般書目、解說
*
*
*
*

約束滿足、泛代數
*
*

格論、範疇論
*
*