圖同態
数学分支圖論中，圖同態（）是兩幅图之間保結構的映射。具體而言，該映射將某圖的各顶点映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。
同態是若干種圖着色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、問題。同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的预序关系、分配格結構、範疇結構（分為無向圖範疇與有向圖範疇兩種）。欲尋找任意兩圖間的同態，而無額外條件，則現時所知的高得不切實際，但對於某些特定類別的圖，已知有多項式時間算法。此類問題易解與否，兩者的分野，是活躍的研究方向。
本條目中，除非另有聲明，否則「圖」皆為有限無向圖，允許自环，但無重边（兩點間連多於一條邊）。自formula_1至另一圖formula_2的圖同態formula_3，記作 是頂點集formula_5至formula_6的函數，其將formula_7每條邊的兩端分別映至formula_8某邊的兩端。以符號表示：對formula_5中每對頂點formula_10，若formula_11，則formula_12。若存在formula_7至formula_8的同態，則稱formula_7同態於（）formula_8，或可染formula_8色（），常簡記為：
上述定義可引伸至有向圖，此時，formula_19為同態的條件是，formula_7中每條有向邊formula_21的像formula_22，仍是formula_8的有向邊。
自formula_7至formula_8有單同態（將不同頂點映至不同頂點），當且僅當formula_7為formula_8的子圖。若同態formula_19為双射（兩圖頂點集的一一對應），且其逆formula_29亦是圖同態，則formula_3為图同构。
是一類特殊的圖同態，相當於將圖時，拓撲學上的覆疊映射，其定義及性質亦是類似：圖覆疊是滿同態（即作為陪域的圖，其每個頂點皆為定義域某頂點的像），且局部為雙射，即若限制到每個頂點的，則為雙射。舉例，圖的，是將每點formula_31分裂為formula_32兩點，並將原圖每條邊formula_33換成交叉的兩條邊formula_34、formula_35。如此，可以定義函數將formula_36和formula_37皆映至formula_31，既是圖同態，也是覆疊映射。
圖同胚是另一個概念，不一定是同態。粗略而言，同胚要求是單射，但不必將邊映至邊，允許映至路徑。图子式的要求更鬆。
若兩幅圖formula_7和formula_8有同態formula_41及formula_42，則稱兩者同態等價（）。該些映射不必單，也不必滿。例如，完全二部圖formula_43與formula_44同態等價，因為可將formula_43左部兩個頂點映到formula_44左部同一個頂點，其右部的兩個頂點映到formula_44右部一個頂點，同樣有formula_48的同態。
收縮映射（）是自圖formula_7至其子圖formula_8的同態formula_51，且對formula_8中每個頂點formula_31有formula_54。若有此種映射，則formula_8稱為formula_7的收縮核（）。
核圖（）沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。每幅圖formula_7皆同態等價於唯一的核圖（不辨同構之別），稱為formula_7的核（）。此結論對無窮圖不一定成立，但對（有限的）有向圖可以照套用同樣的定義，每幅有向圖同態等價於唯一的的核圖。圖（或有向圖）的核，必為原圖某個收縮核，以及某個导出子图。
舉例，完全圖formula_59及奇環（奇數條邊的循环图）皆屬核圖。若formula_7可染三色，且有三角形（即子圖formula_61），則formula_7同態等價於formula_61，原因是formula_7的三染色，下節將說明相當於同態formula_65，且另一方面，任意子圖皆有同態嵌入到formula_7，故有formula_67。如此，證畢formula_61為所有此種formula_7的核。與之相似，每幅非空二部圖（有至少一條邊）皆等價於formula_70。
對正整數formula_71，圖formula_7的formula_71染色是將每個頂點塗formula_71色之一，使每條邊的兩端都不同色。此種染色，與自formula_7至完全圖formula_76的同態，兩類物件一一對應，因為formula_76的各頂點對應formula_71種色，且若formula_79為顏色，則其於圖formula_76相鄰當且僅當formula_81。於是，某函數是formula_7至formula_76的同態，當且僅當該函數將formula_7中相鄰的頂點映至不同顏色（即formula_71染色的定義）。換言之，formula_7可染formula_71色等價於可染formula_76色。
若有同態formula_89及formula_90，則兩者複合可得同態formula_91。所以，若formula_8可染formula_71色，且有同態formula_89，則formula_7同樣可染formula_71色。因此，formula_89推出formula_98，其中formula_99表示圖的色數。
其他同態亦可視作特殊的染色。給定圖formula_8，其頂點視為可用的顏色，每條邊表示某兩色「可兼容」，則formula_7的formula_8染色就是將相鄰頂點染成相容顏色的方案。此框架可容納許多圖染色的概念，將其表述為射向各類圖的同態。舉例如下：
圖同態與也有關。無向圖formula_7的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖formula_76可定向成「遞移」formula_109，其頂點為formula_110，對所有formula_111有（有向）邊自formula_112指向formula_113。給定formula_7的定向與formula_8的定向之間的同態，忘掉定向即得本來無向圖之間的同態。另一方面，給定無向圖同態formula_89，formula_8任何定向formula_118可以拉回到formula_7的定向formula_120，使原同態亦是formula_121的有向圖同態。綜上，無向圖formula_7可染formula_71色（即有同態至formula_76），當且僅當formula_7有某定向，具有至formula_109的同態。
有定理流傳，對每個formula_71，有向圖formula_7有同態至formula_109，當且僅當formula_130個頂點的有向formula_131無同態至formula_7。
因此，某圖可formula_71染色，當且僅當其有某定向，不容任何自formula_131至該定向的同態。此命題可加強成
：某圖可formula_71染色，當且僅當該圖有某定向，其中無長為formula_71的有向路徑（即formula_131作為子圖）。
與前一命題的分別在於，自formula_131至某圖的同態允許將兩頂點映至同處，但「長為formula_71的有向路徑」不允許重複頂點。
某些排程問題可用圖同態建模。設學校已知各學生所選科目，要編排今學期各專題討論班的時間，使同一學生所選的討論班時間不致太近。考慮圖formula_7以各科為頂點，若兩科有共同學生則連邊，而圖formula_8以各課節為頂點，若兩個時段隔足夠遠則連邊。舉例若限制時間表須每週循環，且每個學生所選的討論班須相隔一日，則對應的formula_8是環formula_143的補圖。如此，formula_89的圖同態，就是討論班對應到課節的合適方案。欲添加額外條件，如禁止學生同時於週五與週一有討論班，衹需從formula_8刪掉相應的邊。
問題簡述如下：无线网络中，有若干發訊機，要為每部機配置一個頻率，供其發訊。為免干擾，地理位置較近的發訊機應選用相差較遠的頻率。若將條件中「地理較近」與「頻率較遠」簡化至非黑即白，則合適的分配方案又可視為圖同態formula_89。圖formula_7的頂點為各發訊機，邊表示兩機地理上接近；圖formula_8以各頻段為頂點，邊則表示兩頻段相隔夠遠。雖然此模型甚為簡化，但是尚有保留一點彈性：若有兩機相隔較遠，但仍因地形導致可能-{}-干擾，則在formula_7中加邊即可。反之，若有兩機永不在同一時段發訊，則不論其地理位置是否靠近，皆可從formula_7中刪去該邊。同樣，或許有某些頻率相差頗遠，但是互為谐波，導致干擾，則將該邊自formula_8移除即可
前述模型經簡化，若要實際應用，許多問題仍待解決。約束滿足問題是圖同態問題的推廣，能表達更多種條件（例如個體偏好，或重複分配次數有上限），從而建立更實際的數學模型。
數理邏輯或泛代數中，圖與有向圖屬關係結構的特例，即集合配備若干關係。有向圖就是基集（頂點集）之上有獨一個二元關係（鄰接關係）。如是觀之，圖作為關係結構的同態，按抽象代數的同態定義，等同於本文的圖同態。一般而言，欲尋找自某關係結構至另一關係結構的同態，屬於約束滿足問題（）。圖的特例可作為第一步，幫助理解更複雜的。許多尋找圖同構的算法，包括回溯、、，通用於各種。
給定圖formula_7、formula_8，問是否有同態formula_89，相當於僅得一類約束的實例：的「變量」是formula_7的頂點，每個變量的「域」（可取值的範圍）是formula_8的頂點集。「賦值」是一個函數，將逐個變量映至域的元素，即函數formula_157。formula_7的每條邊（或有向邊）formula_21對應一個「約束」formula_160，限制賦值函數將邊formula_21映至關係formula_162中，即映至formula_8的某邊。的「解」是滿足全體約束的賦值，故前述的解正是自formula_7至formula_8的同態。
同態的複合仍是同態，故可知圖的formula_166關係具遞移性，又顯然自反，所以其為圖之間的預序。同態等價意義下，記formula_7所屬等价类為formula_168，每個等價類有唯一的核圖為其代表。關係formula_169定義該些等價類之間的偏序，即同態等價類構成一個偏序集。
以formula_170表示formula_7有同態至formula_8，但反之則不然。如此定義的序formula_173，即對任意（無向）圖formula_174，若formula_170，則存在第三幅圖formula_176使formula_177，除非是平凡反例formula_178或formula_179。例如，任意兩幅整數階完全圖（除formula_180外）之間，必有無窮多幅，相當於整階數之間的有理數階數。
同態等價類的偏序集是分配格，併formula_181是互斥併formula_182，而交formula_183是formula_184，其定義不取決於等價類中所選的代表formula_174。此格中，正好是連通圖，證明方式是留意同態衹會將連通圖映到目標的一個連通分支中。正好是（），此種圖formula_176的特性是，若乘積formula_187有同態至formula_8，則formula_7或formula_8兩者之一有同態至formula_8。如何識別積性圖是的關鍵。
圖與同態還組成範疇：圖是物件，而同態是態射。範疇的始物件是空圖formula_192，終物件有一個頂點和一個自环。是範疇論積，是該範疇的。換言之，自formula_193的同態與formula_194的同態自然地一一對應。由於對任意圖formula_174，張量積formula_187與冪formula_197總有定義，圖範疇是笛卡儿闭范畴。同理，同態等價類組成的格實際上是海廷代数：按海廷代數的語言，前述的積稱為交運算formula_198，而前述的指數運算稱為蘊涵formula_199。
對於有向圖，適用同樣的定義。同樣有formula_200是有向圖同態等價類之間的偏序，其與無向圖等價類的偏序formula_200有別，但後者是前者的子序，因為無向圖亦可視為有向圖，衹是其中每條有向邊formula_21皆與其反向formula_203成對出現。換言之，無向圖同態的定義，與雙向有向圖的同態並無區別。有向圖的formula_166序仍是分配格和海延代數，交與併的定義亦同上，但分別在於，該序並不稠密。亦有以有向圖為物件、同態為態射的範疇，照樣笛卡儿闭。
同態預序下，許多圖不可比較。兩幅不可比圖（）之間，並無自任意一幅至另一幅的同態。欲構造此種圖，可考慮圖的奇圍長，即最短的奇環長度。奇圍長可等價地說成最小的奇數formula_205，使formula_205個頂點的循环图formula_207有同態至formula_7。由此定義，若formula_89，則formula_7的奇圍長大於或等於formula_8的奇圍長。
另一方面，前節已證若formula_89，則formula_7的色數小於或等於formula_8的色數。所以，若formula_7的奇圍長及色數皆嚴格大於formula_8，則formula_7和formula_8不可比較。 舉例，色數為formula_219，且無三角形（圍長formula_219，奇圍長formula_221），所以與三角形formula_61不可比。
有幾類圖的奇圍長和色數可取任意大，如與。如此一類圖，若使其兩參數同時遞增，排成一列，則有無窮多幅不可比圖（同態預序下的反鏈）。 同態預序等其他性質，亦可利用此類圖證明。此外，可構造同時具大色數和大圍長（不僅是奇圍長）的圖，但較複雜，見。
有向圖之中，更易找到不可比圖。例如，考慮有向環formula_223，頂點為formula_224，有向邊自formula_112至formula_226（對formula_227各一），及自formula_228至formula_229。對於formula_230，formula_223至formula_232有同態當且僅當formula_228為formula_71的倍數。所以，當formula_235取質數值時，formula_236兩兩不可比。
圖同態問題是給定一對圖formula_237，求自formula_7至formula_8的圖同態。對應的決定性問題問是否存在此種解。一般情況下，即詢問的實例formula_237不受額外限制的情況下，此決定性問題為NP完全。若限制詢問的範圍，衹限從某類圖中選出formula_7或formula_8，則可得多種不同的問題，其中有些較易求解。限制左邊formula_7和限制右邊formula_8相比，適用的方法相去甚遠，但兩者似乎有一共同特點：難易情況之間似乎有明確的分界，此分界或者已獲證，或有論文猜想如此。
圖同態問題若固定右邊的圖formula_8不變，則稱為染formula_8色問題。formula_8為完全圖formula_76時，化成染"k"色問題，在formula_249時，可於多項式時間內求解，但其餘情況則是NP完全。formula_250的情況相當於問圖formula_7可否染formula_70色，即是否二部圖，此問題可在線性時間內求解。更一般地，衹要formula_8是二部圖就有同一結論：可染formula_8色等價於可染formula_70色，即可染二色，故此種情況同樣易判斷。可染formula_192色和可染formula_257色分別等價於無頂點和無邊，亦易判斷。和證明，對無向圖而言，無其他情況可馴順： （黑爾-內舍特日爾定理，1990年）若formula_8為二部圖，則染formula_8色問題屬於P，但其餘情況則為NP完全。 上述定理又稱為無向圖同態的「對分定理」（），因為將染formula_8色問題分成NP完全與P兩類，而無情況。有向圖情況較複雜，此時問題等價於刻畫看似更一般的：有向圖的染formula_8色問題，與允許各種約束條件的相比，同樣多姿多彩，而不失一般性。嚴格而言，定義（有限）約束語言（，或稱模板）formula_262為一個有限的取值域，其上配備有限多種關係，然後以formula_263表示約束衹能選自formula_262的一類約束滿足問題，則有以下定理： （费德、，1998年）對任意約束語言formula_262，必有某幅有向圖formula_8，使formula_263在多项式时间归约意義下等價於染formula_8色問題。 直觀理解，定理意味着任何算法技巧或複雜度結論，若適用於一般有向圖formula_8的染formula_8色問題，則可套用至一般。考慮將黑爾-內舍特日爾定理擴展至有向圖。由上述定理，該推廣等價於有關對分的费德-瓦迪猜想（又稱猜想、對分猜想），即斷言對任意約束語言formula_262，formula_263或屬NP完全，或屬P。此猜想於2017年由德米特里·祖克（）與安德烈·布拉托夫（）分別獨立證出，故有以下推論： （布拉托夫2017年；祖克2017年）給定formula_8時，有向圖的染formula_8色問題或屬P，或屬NP完全。 若左輸入formula_7為給定，則圖同態問題有暴力解法，即窮舉formula_7的各個頂點在formula_8中的像，複雜度僅為formula_278，已是輸入formula_8的多項式函數。換言之，限制formula_7的大小時，問題顯然屬P，但仍可改為研究另一課題：除大小之外，是否其他限制可施加於formula_7，使圖同態問題可於多項式時間內求解？
研究表明，關鍵性質是，此參數衡量一幅圖有多似一棵樹。若formula_7的樹闊至多為formula_71，而formula_8為任意圖，則利用標準的动态规划方法，可於formula_285時間內求解圖同態問題。實際甚至衹需假設formula_7的核的樹闊不逾formula_71，而無需知道其核為何。
該formula_285算法中，複雜度的指數可能無法再壓低太多：若（）為真，則不存在時間複雜度為formula_289的算法。即使限制formula_7衹能取值為某一族圖，衹要該族圖的樹闊無上界，則仍有同樣結論。同樣假設下，幾乎沒有其他性質使問題可於多項式時間內求解，具體含義如下： （）假定，並給定由圖組成的可計算族formula_291。考慮輸入為formula_292，且formula_293的圖同態問題。此問題屬P當且僅當formula_291中各圖之核的樹闊有界。 或考慮有所取捨，允許複雜度高度依賴formula_7，換取複雜度與formula_8的關係僅為固定的多項式。與前段類似，若formula_7的取值範圍中，核的樹闊有界，則此目標可以實現，但若formula_7的取值範圍不滿足該條件，則無法達成。利用術語，上述成果可覆述為：formula_291中的同態問題，以formula_7的邊數為參數，呈現對分現象。若formula_291中各圖之核的樹闊有上界，則該問題為，否則為完全。
同一命題對其他關係結構亦成立。換言之，其適用於一般的約束滿足問題，不過需要限制各項約束涉及的變量數有上界，即關係的元數有上界（以圖為例，僅得元數為2的關係）。此時，關鍵參數為的樹闊。