圖同態

由Template:Link-enJ₅射向環圖C₅的同態，亦是到J₅中央五個頂點所成子圖的收縮，所以J₅與其Template:LeC₅「同態等價」。

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

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

定義

本條目中，除非另有聲明，否則「圖」皆為有限無向圖，允許自环，但無重边（兩點間連多於一條邊）。自$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$同態於（Template:Lang）$H$，或可染$H$色（Template:Lang），常簡記為：

$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$為图同构。Template:Sfn

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

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

核與回縮

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

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

收縮映射（Template:Lang）是自圖$G$至其子圖$H$的同態$r$，且對$H$中每個頂點$v$有$r(v)=v$。若有此種映射，則$H$稱為$G$的收縮核（Template:Lang）。Template:Sfn

核圖（Template:Lang）沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。Template:Sfn每幅圖$G$皆同態等價於唯一的核圖（不辨同構之別），稱為$G$的核（Template:Lang）。Template:Sfnm此結論對無窮圖不一定成立Template:Sfn，但對（有限的）有向圖可以照套用同樣的定義，每幅有向圖同態等價於唯一的核圖。圖（或有向圖）的核，必為原圖某個收縮核，以及某個导出子图。Template:Sfn

舉例，完全圖$K_n$及奇環（奇數條邊的循环图）皆屬核圖。若$G$可染三色，且有三角形（即子圖$K_3$），則$G$同態等價於$K_3$，原因是$G$的三染色，下節將說明相當於同態$G\to K_3$，且另一方面，任意子圖皆有同態嵌入到$G$，故有$K_3\to G$。如此，證畢$K_3$為所有此種$G$的核。與之相似，每幅非空二部圖（有至少一條邊）皆等價於$K_2$。Template:Sfn

與染色的關聯

對正整數$k$，圖$G$的$k$染色是將每個頂點塗$k$色之一，使每條邊的兩端都不同色。此種染色，與自$G$至完全圖$K_k$的同態，兩類物件一一對應Template:Sfnm，因為$K_k$的各頂點對應$k$種色，且若$c_1,c_2$為顏色，則其於圖$K_k$相鄰當且僅當$c_1\ne c_2$。於是，某函數是$G$至$K_k$的同態，當且僅當該函數將$G$中相鄰的頂點映至不同顏色（即$k$染色的定義）。換言之，$G$可染$k$色等價於可染$K_k$色。Template:Sfnm

若有同態$G\to H$及$H\to K_k$，則兩者複合可得同態$G\to K_k$。Template:Sfn所以，若$H$可染$k$色，且有同態$G\to H$，則$G$同樣可染$k$色。因此，$G\to H$推出$\chi (G)\le \chi (H)$，其中$\chi$表示圖的色數Template:註。Template:Sfn

變式

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

• Template:Le可定義為至Template:LeTemplate:註的同態，從而推廣一般的染色，定義「分數」色數。Template:Sfnm
• Template:Link-en與Template:Link-en可定義成射向Template:Link-en的同態。Template:Sfnm
• Template:Link-en的可用色集為自然數集$\mathbb{N}$，但另有給定某子集$T\subseteq \mathbb{N}$，禁止相鄰頂點所染顏色之差屬於$T$。此種染色對應往某幅無窮圖的同態。Template:Sfn
• Template:Link-en除禁止相鄰頂點同色外，還限制不同顏色之間的所有邊皆同向（例如由藍至紅）。此為映向Template:Link-en的同態。Template:Sfn
• Template:Link-en以數表示顏色，要求距離為1（相鄰）的頂點所染顏色之差至少為2，而距離為2的頂點染色之差至少為1。換言之，此為射向路圖$P_n$之補的同態，且要求局部為單射，即在每個頂點的鄰域上為單射。

無長路徑的定向

Template:Main 圖同態與Template:Link-en也有關。無向圖$G$的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖$K_k$可定向成「遞移Template:Le」$\overrightarrow{T_k}$，其頂點為$1,2,\dots ,k$，對所有$i<j$有（有向）邊自$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}$的同態。Template:Sfn

有定理流傳Template:註，對每個$k$，有向圖$G$有同態至$\overrightarrow{T_k}$，當且僅當$k+1$個頂點的有向Template:Le$\overrightarrow{P_{k+1}}$Template:註無同態至$G$。Template:Sfn

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

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

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

與約束滿足問題的關聯

範例

圖$H$，表示一週中不相鄰的日子，同構於環$C_7$的補圖，亦同構於Template:Link-en$K_{7/2}$

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

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

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

抽象觀點

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

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

同態的結構

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

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

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

圖與同態還組成範疇：圖是物件，而同態是態射。Template:Sfn範疇的始物件是空圖$K_0$，終物件有一個頂點和一個自环。Template:Link-en是範疇論積，Template:Link-enTemplate:註是該範疇的Template:Link-en。換言之，自$G\times H\to K$的同態與$H\to K^G$的同態自然地一一對應。Template:Sfn由於對任意圖$G,H$，張量積$G\times H$與冪$H^G$總有定義，圖範疇是笛卡儿闭范畴。同理，同態等價類組成的格實際上是海廷代数：按海廷代數的語言，前述的積稱為交運算$\wedge$，而前述的指數運算稱為蘊涵$\Rightarrow$。Template:Sfn

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

不可比圖

Template:Le，與$K_3$不可比

同態預序下，許多圖不可比較。兩幅不可比圖（Template:Lang）之間，並無自任意一幅至另一幅的同態。Template:Sfn欲構造此種圖，可考慮圖的奇圍長，即最短的奇環長度。奇圍長可等價地說成最小的奇數$g$，使$g$個頂點的循环图$C_g$有同態至$G$。由此定義，若$G\to H$，則$G$的奇圍長大於或等於$H$的奇圍長。Template:Sfn

另一方面，前節已證若$G\to H$，則$G$的色數小於或等於$H$的色數。所以，若$G$的奇圍長及色數皆嚴格大於$H$，則$G$和$H$不可比較。Template:Sfn 舉例，Template:Link-en色數為$4$，且無三角形（圍長$4$，奇圍長$5$），所以與三角形$K_3$不可比。

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

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

計算複雜度

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

至給定圖的同態

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

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

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

（费德、Template:Link-en，1998年）對任意約束語言$\mathrm{\Gamma }$，必有某幅有向圖$H$，使$𝖢𝖲𝖯(\mathrm{\Gamma })$在多项式时间归约意義下等價於染$H$色問題。

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

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

自給定族的同態

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

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

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

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

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

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

參見

• 图论术语
• 同态，其他代數結構的同一概念
• Template:Link-en
• Template:Link-en，可定義成Template:Link-en的收縮核
• Template:Link-en

參考資料

一般書目、解說

• Template:Cite web
• Template:Cite book
• Template:Cite chapter
• Template:Cite chapter

約束滿足、泛代數

• Template:Cite web
• Template:Cite journal

格論、範疇論

• Template:Cite journal
• Template:Cite web