查看“︁圖同態”︁的源代码

{{NoteTA
|G1=math
|G2=IT
}}
{{for|兩幅圖如何算是「完全一樣」|圖同構}}
{{for|允許將邊映成路徑的映射|圖同胚}}
[[File:Graph homomorphism into C5.svg|upright=1.2|thumb|alt= J5至C5的同態|由{{link-en|花形蛇鯊圖|flower snark}}<!--snark語出[[獵鯊記]]-->''J''<sub>5</sub>射向環圖''C''<sub>5</sub>的同態，亦是到''J''<sub>5</sub>中央五個頂點所成子圖的收縮，所以''J''<sub>5</sub>與其{{le|核圖|core (graph theory)|核}}''C''<sub>5</sub>「同態等價」。]]
[[数学]]分支[[圖論]]中，'''圖同態'''（{{lang-en|graph homomorphism}}）是兩幅[[图 (数学)|图]]之間保結構的[[映射]]。具體而言，該映射將某圖的各[[顶点 (图论)|顶点]]映至另一圖的頂點，且若兩頂點相鄰，則其[[像 (數學)|像]]仍然相鄰。

同態是若干種[[图着色问题|圖着色]]概念的推廣，適用於表達一類重要的[[約束滿足問題]]，如[[排程]]、{{link-en|頻段分配|frequency assignment}}問題。{{sfn|Hell|Nešetřil|2004|p=27}}同態可以[[複合函數|複合]]，為全體圖組成的[[類 (數學)|類]]賦予豐富的代數結構：其上的[[预序关系]]、[[分配格|分配格結構]]、[[範疇 (數學)|範疇結構]]（分為無向[[圖範疇]]與有向圖範疇兩種）。{{sfn|Hell|Nešetřil|2004|p=109}}欲尋找任意兩圖間的同態，而無額外條件，則現時所知的{{link-en|計算複雜度|computational complexity}}高得不切實際，但對於某些特定類別的圖，已知有[[多項式時間]]算法。此類問題易解與否，兩者的分野，是活躍的研究方向。{{sfn|Hell|Nešetřil|2008}}

== 定義 ==
本條目中，除非另有聲明，否則「圖」皆為有限[[無向圖]]，允許[[自环]]，但無[[重边]]（兩點間連多於一條邊）。自<math>G = (V(G), E(G))</math>至另一圖<math>H = (V(H), E(H))</math>的'''圖同態'''<ref name="intros">引論見諸：{{harvtxt|Cameron|2006}}; {{harvtxt|Hahn|Tardif|1997}}; {{harvtxt|Hell|Nešetřil|2004}}. 由短至長排。</ref><math>f</math>，記作
: <math> f : G \to H,</math>
是頂點集<math>V(G)</math>至<math>V(H)</math>的函數，其將<math>G</math>每條邊的兩端分別映至<math>H</math>某邊的兩端。以符號表示：對<math>V(G)</math>中每對頂點<math>u, v</math>，若<math>\{u, v\} \in E(G)</math>，則<math>\{f(u), f(v)\} \in E(H)</math>。若存在<math>G</math>至<math>H</math>的同態，則稱<math>G</math>'''同態於'''（{{lang|en|homomorphic to}}）<math>H</math>，或'''可染<math>H</math>色'''（{{lang|en|<math>H</math>-colourable}}），常簡記為：
: <math>G \to H.</math>

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

自<math>G</math>至<math>H</math>有[[单射|單]]同態（將不同頂點映至不同頂點），當且僅當<math>G</math>為<math>H</math>的[[子圖]]。若同態<math>f:G \to H</math>為[[双射]]（兩圖頂點集的[[一一對應]]），且其[[反函數|逆]]<math>f^{-1}</math>亦是圖同態，則<math>f</math>為[[图同构]]。{{sfn|Hahn|Tardif|1997|loc=Observation 2.3}}

{{link-en|圖覆疊|Covering graph|圖的覆疊映射}}是一類特殊的圖同態，相當於將圖{{le|圖 (拓撲學)|Graph (topology)|視為拓撲空間}}時，[[拓撲學]]上的[[覆疊空間|覆疊映射]]，其定義及性質亦是類似：{{sfn|Godsil|Royle|2001|p=115}}圖覆疊是[[满射|滿]]同態（即作為[[陪域]]的圖，其每個頂點皆為[[定義域]]某頂點的像），且[[局部性質|局部]]為雙射，即若限制到每個頂點的{{link-en|鄰域 (圖論)|neighbourhood (graph theory)|鄰域}}，則為雙射。舉例，圖的{{link-en|典範雙重覆疊|bipartite double cover}}，是將每點<math>v</math>分裂為<math>v_0, v_1</math>兩點，並將原圖每條邊<math>uv</math>換成交叉的兩條邊<math>u_0v_1</math>、<math>u_1 v_0</math>。如此，可以定義函數將<math>v_0</math>和<math>v_1</math>皆映至<math>v</math>，既是圖同態，也是覆疊映射。

[[圖同胚]]是另一個概念，不一定是同態。粗略而言，同胚要求是單射，但不必將邊映至邊，允許映至[[路徑 (圖論)|路徑]]。[[图子式]]的要求更鬆。
=== 核與回縮 ===
[[File:Complete graph K7.svg|thumb|upright=0.8|right|alt = 正七邊形的七個頂點，兩兩之間有線段相連|''K''<sub>7</sub>，七個頂點的完全圖，一種核圖]]
{{main|{{le|核圖|Core (graph theory)}}}}

若兩幅圖<math>G</math>和<math>H</math>有同態<math>G\to H</math>及<math>H \to G</math>，則稱兩者'''同態等價'''（{{lang|en|homomorphically equivalent}}）。<ref name="intros" />該些映射不必單，也不必滿。例如，[[完全二分图|完全二部圖]]<math>K_{2, 2}</math>與<math>K_{3, 3}</math>同態等價，因為可將<math>K_{2, 2}</math>左部兩個頂點映到<math>K_{3, 3}</math>左部同一個頂點，其右部的兩個頂點映到<math>K_{3, 3}</math>右部一個頂點，同樣有<math>K_{3, 3} \to K_{2, 2}</math>的同態。

'''收縮映射'''（{{lang|en|retraction}}）是自圖<math>G</math>至其[[子圖]]<math>H</math>的同態<math>r</math>，且對<math>H</math>中每個頂點<math>v</math>有<math>r(v) = v</math>。若有此種映射，則<math>H</math>稱為<math>G</math>的'''收縮核'''（{{lang|en|retract}}）<!--譯名按 https://www.google.co.uk/books/edition/%E8%8B%B1%E6%B1%89%E6%95%B0%E5%AD%A6%E8%AF%8D%E6%B1%87/nduYtmyywcUC?hl=en&gbpv=1&pg=PP1&printsec=frontcover&bsq=retract -->。{{sfn|Hell|Nešetřil|2004|p=19}}

'''核圖'''（{{lang|en|core}}）沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。{{sfn|Hell|Nešetřil|2004|loc=Proposition 1.31}}每幅圖<math>G</math>皆同態等價於唯一的核圖（[[Up to|不辨]]同構之別），稱為'''<math>G</math>的核'''（{{lang|en|the core of <math>G</math>}}）。{{sfnm|1a1=Cameron|1y=2006|1loc=Proposition 2.3|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Corollary 1.32}}此結論對無窮圖不一定成立{{sfn|Hell|Nešetřil|2004|p=34}}，但對（有限的）有向圖可以照套用同樣的定義，每幅有向圖同態等價於唯一的核圖。圖（或有向圖）的核，必為原圖某個收縮核，以及某個[[导出子图]]。{{sfn|Hell|Nešetřil|2004|p=19}}

舉例，[[完全圖]]<math>K_n</math>及奇環（奇數條邊的[[循环图]]）皆屬核圖。若<math>G</math>[[图着色问题|可染三色]]，且有三角形（即子圖<math>K_3</math>），則<math>G</math>同態等價於<math>K_3</math>，原因是<math>G</math>的三染色，[[#與染色的關聯|下節]]將說明相當於同態<math>G \to K_3</math>，且另一方面，任意子圖皆有同態[[嵌入 (數學)|嵌入]]到<math>G</math>，故有<math>K_3 \to G</math>。如此，證畢<math>K_3</math>為所有此種<math>G</math>的核。與之相似，每幅非空[[二分图|二部圖]]（有至少一條邊）皆等價於<math>K_2</math>。{{sfn|Cameron|2006|loc=Proposition 2.5|p=4}}

== 與染色的關聯 ==
對正整數<math>k</math>，圖<math>G</math>的<math>k</math>[[图着色问题|染色]]是將每個頂點塗<math>k</math>色之一，使每條邊的兩端都不同色。此種染色，與自<math>G</math>至[[完全圖]]<math>K_k</math>的同態，兩類物件一一對應{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}}，因為<math>K_k</math>的各頂點對應<math>k</math>種色，且若<math>c_1, c_2</math>為顏色，則其於圖<math>K_k</math>相鄰當且僅當<math>c_1 \neq c_2</math>。於是，某函數是<math>G</math>至<math>K_k</math>的同態，當且僅當該函數將<math>G</math>中相鄰的頂點映至不同顏色（即<math>k</math>染色的定義）。換言之，<math>G</math>可染<math>k</math>色等價於可染<math>K_k</math>色。{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}}

若有同態<math>G \to H</math>及<math>H \to K_k</math>，則兩者複合可得同態<math>G \to K_k</math>。{{sfn|Hell|Nešetřil|2004|loc=§1.7}}所以，若<math>H</math>可染<math>k</math>色，且有同態<math>G \to H</math>，則<math>G</math>同樣可染<math>k</math>色。因此，<math>G \to H</math>推出<math>\chi(G) \le \chi(H)</math>，其中<math>\chi</math>表示圖的[[图着色问题|色數]]{{註|使該圖可染<math>k</math>色的最小<math>k</math>值。}}。{{sfn|Hell|Nešetřil|2004|loc=Corollary 1.8}}

=== 變式 ===
其他同態亦可視作特殊的染色。給定圖<math>H</math>，其頂點視為可用的顏色，每條邊表示某兩色「可兼容」，則<math>G</math>的<math>H</math>染色就是將相鄰頂點染成相容顏色的方案。此框架可容納許多圖染色的概念，將其表述為射向各類圖的同態。舉例如下：
*{{le|循環染色|Circular coloring}}可定義為至{{le|循環完全圖|circular clique}}{{註|取<math>0</math>至<math>n-1</math>為<math>n</math>個頂點，相異兩點<math>u, v</math>間有連邊當且僅當模<math>n</math>運算時，<math>|u - v|</math>大於某定值。}}的同態，從而推廣一般的染色，定義「分數」色數。{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.1|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.4}}
*{{link-en|分數染色|Fractional coloring}}與{{link-en|分數染色|Fractional coloring|''b''重染色}}可定義成射向{{link-en|克內澤爾圖|Kneser graph}}<!--得名自Martin Kneser，沿用另一德國數學家[[赫爾穆特·克內澤爾]]的譯名-->的同態。{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.2|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.5}}
*{{link-en|T染色|T-coloring|''T''染色}}的可用色集為自然數集<math>\mathbb N</math>，但另有給定某子集<math>T \subseteq \mathbb N</math>，禁止相鄰頂點所染顏色之差屬於<math>T</math>。此種染色對應往某幅無窮圖的同態。{{sfn|Hell|Nešetřil|2004|loc=§6.3}}
*{{link-en|有向染色|oriented coloring}}除禁止相鄰頂點同色外，還限制不同顏色之間的所有邊皆同向（例如由藍至紅）。此為映向{{link-en|有向圖|oriented graph}}的同態。{{sfn|Hell|Nešetřil|2004|loc=§6.4}}
*{{link-en|L(2,1)染色|L(2,1)-coloring}}以數表示顏色，要求距離為1（相鄰）的頂點所染顏色之差至少為2，而距離為2的頂點染色之差至少為1。換言之，此為射向[[道路 (图论)|路圖]]<math>P_n</math>之[[補圖|補]]的同態，且要求局部為單射，即在每個頂點的鄰域上為單射。<ref>{{citation|first1=J.|last1=Fiala|first2=J.|author2-link=Jan Kratochvíl|last2=Kratochvíl|s2cid=17507393|title=Partial covers of graphs|trans-title = 圖之部分覆蓋|year=2002|journal=Discussiones Mathematicae Graph Theory|volume=22|issue=1|pages=89–99|doi=10.7151/dmgt.1159|language = en}}</ref>

=== 無長路徑的定向 ===
{{main|{{le|高洛伊-哈塞-羅伊-維塔韋爾定理|Gallai–Hasse–Roy–Vitaver theorem}}}}
圖同態與{{link-en|定向 (圖論)|Orientation (graph theory)|圖定向}}也有關。無向圖<math>G</math>的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖<math>K_k</math>可定向成「遞移{{le|循環賽圖|Tournament (graph theory)}}」<math>\overrightarrow{T_k}</math>，其頂點為<math>1, 2, \ldots, k</math>，對所有<math>i < j</math>有（有向）邊自<math>i</math>指向<math>j</math>。給定<math>G</math>的定向與<math>H</math>的定向之間的同態，忘掉定向即得本來無向圖之間的同態。另一方面，給定無向圖同態<math>G \to H</math>，<math>H</math>任何定向<math>\overrightarrow{H}</math>可以[[拉回#预复合|拉回]]<!--消歧義頁但相關資訊載於該頁-->到<math>G</math>的定向<math>\overrightarrow{G}</math>，使原同態亦是<math>\overrightarrow{G} \to \overrightarrow{H}</math>的有向圖同態。綜上，無向圖<math>G</math>可染<math>k</math>色（即有同態至<math>K_k</math>），當且僅當<math>G</math>有某定向，具有至<math>\overrightarrow{T_k}</math>的同態。{{sfn|Hell|Nešetřil|2004|pp=13–14}}

有定理流傳{{註|{{le|數學流傳|Mathematical folklore}}，謂難以溯源或原創者並無正式投稿出版，但廣為研究者熟知的定理。}}，對每個<math>k</math>，有向圖<math>G</math>有同態至<math>\overrightarrow{T_k}</math>，當且僅當<math>k+1</math>個頂點的有向{{le|路徑圖|path graph}}<math>\overrightarrow{P_{k+1}}</math>{{註|<math>\overrightarrow{P_n}</math>的頂點為<math>1, 2, \ldots, n</math>，且對每個<math>i = 1, 2, \ldots, n-1</math>有一條邊自<math>i</math>至<math>i+1</math>。}}無同態至<math>G</math>。{{sfn|Hell|Nešetřil|2004|loc=Proposition 1.20}}

因此，某圖可<math>k</math>染色，當且僅當其有某定向，不容任何自<math>\overrightarrow{P_{k+1}}</math>至該定向的同態。此命題可加強成
<blockquote>
{{link-en|高洛伊-哈塞-羅伊-維塔韋爾定理|Gallai–Hasse–Roy–Vitaver theorem}}：某圖可<math>k</math>染色，當且僅當該圖有某定向，其中無長為<math>k</math>的有向路徑（即<math>\overrightarrow{P_{k+1}}</math>作為子圖）。
</blockquote>
與前一命題的分別在於，自<math>\overrightarrow{P_{k+1}}</math>至某圖的同態允許將兩頂點映至同處，但「長為<math>k</math>的有向路徑」不允許重複頂點。

== 與約束滿足問題的關聯 ==
=== 範例 ===
[[File:Graph of non-adjacent weekdays_zh.svg|thumb|300px|圖<math>H</math>，表示一週中不相鄰的日子，同構於環<math>C_7</math>的[[補圖]]，亦同構於{{link-en|環狀團|circular clique}}<math>K_{7/2}</math>]]
某些排程問題可用圖同態建模。{{sfn|Cameron|2006|p=1}}{{sfn|Hell|Nešetřil|2004|loc=§1.8}}設學校已知各學生所選科目，要編排今學期各專題討論班的時間，使同一學生所選的討論班時間不致太近。考慮圖<math>G</math>以各科為頂點，若兩科有共同學生則連邊，而圖<math>H</math>以各課節為頂點，若兩個時段隔足夠遠則連邊。舉例若限制時間表須每週循環，且每個學生所選的討論班須相隔一日，則對應的<math>H</math>是環<math>C_7</math>的[[補圖]]。如此，<math>G \to H</math>的圖同態，就是討論班對應到課節的合適方案。{{sfn|Cameron|2006|p=1}}欲添加額外條件，如禁止學生同時於週五與週一有討論班，衹需從<math>H</math>刪掉相應的邊。

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

前述模型經簡化，若要實際應用，許多問題仍待解決。{{sfn|Hell|Nešetřil|2004|pp=31–32}}[[約束滿足問題]]是圖同態問題的推廣，能表達更多種條件（例如個體偏好，或重複分配次數有上限），從而建立更實際的數學模型。

=== 抽象觀點 ===
數理邏輯或[[泛代數]]中，圖與有向圖屬[[结构 (数理逻辑)|關係結構]]的特例，即集合配備若干[[關係 (數學)|關係]]。有向圖就是基集（頂點集）之上有獨一個二元關係（鄰接關係）。<ref name="HN-csp">{{harvnb|Hell|Nešetřil|2004|p=28}}，該書稱關係結構（{{lang|en|relational structures}}）為「關係系統」（{{lang|en|relational systems}}）。</ref>{{sfn|Hell|Nešetřil|2008}}如是觀之，圖作為關係結構的[[结构 (数理逻辑)|同態]]，按抽象代數的同態定義，等同於本文的圖同態。一般而言，欲尋找自某關係結構至另一關係結構的同態，屬於[[约束补偿问题|約束滿足問題]]（{{lang|en|constraint satisfaction problem, CSP}}）。圖的特例可作為第一步，幫助理解更複雜的{{lang|en|CSP}}。許多尋找圖同構的算法，包括[[回溯法|回溯]]、{{link-en|約束傳播|constraint propagation}}<!--譯名見https://terms.naer.edu.tw/detail/16968652/?index=3 -->、{{link-en|局部搜索 (約束滿足)|Local search (constraint satisfaction)|局部搜索}}，通用於各種{{lang|en|CSP}}。{{sfn|Hell|Nešetřil|2008}}

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

== 同態的結構 ==
同態的複合仍是同態{{sfn|Hell|Nešetřil|2004|loc=§1.7}}，故可知圖的<math>\to</math>關係具[[遞移關係|遞移性]]，又顯然[[自反關係|自反]]，所以其為圖之間的[[预序关系|預序]]。{{sfn|Hell|Nešetřil|2004|loc=§3.1}}同態等價意義下，記<math>G</math>所屬[[等价类]]為<math>[G]</math>，每個等價類有唯一的核圖為其代表。關係<math> \to </math>定義該些等價類之間的[[偏序]]，即同態等價類構成一個[[偏序集]]。{{sfn|Hell|Nešetřil|2004|loc=Theorem 3.1}}

以<math>G < H</math>表示<math>G</math>有同態至<math>H</math>，但反之則不然。如此定義的序<math> < </math>{{link-en|稠密序|dense order|稠密}}，即對任意（無向）圖<math>G, H</math>，若<math>G < H</math>，則存在第三幅圖<math>K</math>使<math>G < K < H</math>，除非是平凡反例<math>G = K_0</math>或<math>G = K_1</math>。{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=Theorem 3.30|2a1=Hahn|2a2=Tardif|2y=1997|2loc=Theorem 2.33}}<ref>{{citation|first=E.|last=Welzl|title=Color-families are dense|trans-title = 染色族稠密|year=1982|journal={{link-en|理論電腦科學 (期刊)|Theoretical Computer Science (journal)|Theoretical Computer Science}}|volume=17|pages=29–41|doi=10.1016/0304-3975(82)90129-3|doi-access=free|language = en}}</ref>例如，任意兩幅整數階[[完全圖]]（除<math>K_0, K_1, K_2</math>外）之間，必有無窮多幅{{link-en|環狀團|circular clique|環狀完全圖}}，相當於整階數之間的有理數階數。{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1p=192|2a1=Hahn|2a2=Tardif|2y=1997|2p=127}}

同態等價類的偏序集是[[分配格]]，[[并运算|併]]<math>[G]\lor[H]</math>是互斥併<math>[G \sqcup H]</math>，而[[交运算|交]]<math>[G] \land [H]</math>是{{link-en|圖張量積|tensor product of graphs}}<math>[G\times H]</math>，其定義不取決於等價類中所選的代表<math>G, H</math>。<ref>{{harvnb|Hell|Nešetřil|2004|loc=Proposition 3.2}}，分配律載於Proposition 2.4；又見{{harvnb|Hahn|Tardif|1997|loc=Theorem 2.37}}.</ref>此格中，{{le|併不可約|join-irreducible|併不可約元}}<!--譯名見 https://www.google.co.uk/books/edition/%E8%8B%B1%E6%B1%89%E6%95%B0%E5%AD%A6%E8%AF%8D%E6%B1%87/nduYtmyywcUC?hl=en&gbpv=1&pg=PA372&printsec=frontcover&bsq=join-irreducible -->{{註|name = "irred"|<math>x</math>為併不可約，意即<math> x= a \lor b </math>推出<math> x = a</math>或<math>x = b</math>。對偶概念為交不可約。}}正好是[[連通圖]]，證明方式是留意同態衹會將連通圖映到目標的一個[[連通分支]]中。<ref>{{citation
 | last1 = Kwuida | first1 = Léonard
 | last2 = Lehtonen | first2 = Erkko
 | title = On the Homomorphism Order of Labeled Posets 
 | trans-title = 論標號偏序集之同態序
 | doi = 10.1007/s11083-010-9169-x
 | year = 2011
 | arxiv = 0911.0200
 | journal = {{link-en|序 (期刊)|Order (journal)|Order}}
 | volume = 28
 | issue = 2
 | pages = 251–265
 | s2cid = 14920600
 | language = en
 }}</ref>{{sfn|Gray|2014|loc=Lemma 3.7}}{{le|交不可約|meet-irreducible|交不可約元}}{{註|name = "irred"}}正好是{{link-en|赫德米猜想|Hedetniemi's conjecture|積性圖}}（{{lang|en|multiplicative graphs}}），此種圖<math>K</math>的特性是，若乘積<math>G \times H</math>有同態至<math>H</math>，則<math>G</math>或<math>H</math>兩者之一有同態至<math>H</math>。如何識別積性圖是{{link-en|赫德米猜想|Hedetniemi's conjecture}}<ref>譯名見 {{cite journal |author = 陳宏賓 |url = https://sites.google.com/a/g2.nctu.edu.tw/unimath/2020-02/Hedetniemi_conjecture |title = 捉住黑暗中的微光，年輕數學家希多夫擊破［赫德米猜想］ |journal = UniMath |date = 2020-02-22 |access-date = 2021-12-21 |archive-date = 2021-12-21 |archive-url = https://web.archive.org/web/20211221214620/https://sites.google.com/a/g2.nctu.edu.tw/unimath/2020-02/Hedetniemi_conjecture }}</ref>的關鍵。<ref>{{citation
 | last = Tardif
 | first = C.
 | title = Hedetniemi's conjecture, 40 years later
 | trans-title = 赫德米猜想四十年
 | url = http://www.mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 | pages = 46–57
 | volume = 54
 | journal = Graph Theory Notes of New York
 | mr = 2445666
 | year = 2008
 | language = en
 | accessdate = 2021-12-21
 | archive-date = 2021-07-12
 | archive-url = https://web.archive.org/web/20210712104609/https://mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 }}.</ref><ref name="lattices">{{citation|first1=D.|last1=Dwight|first2=N.|last2=Sauer|title=Lattices arising in categorial investigations of Hedetniemi's conjecture|trans-title = 以範疇論研究赫德米猜想所得的格 |journal={{link-en|離散數學 (期刊)|Discrete Mathematics (journal)|Discrete Mathematics}}|volume=152|issue=1–3|year=1996|pages=125–139|doi=10.1016/0012-365X(94)00298-W|doi-access=free |language = en}}</ref>

圖與同態還組成[[範疇 (數學)|範疇]]：圖是物件，而同態是態射。{{sfn|Hell|Nešetřil|2004|p=125}}範疇的[[始对象和终对象|始物件]]是空圖<math>K_0</math>，[[始对象和终对象|終物件]]有一個頂點和一個[[自环]]。{{link-en|圖張量積|tensor product of graphs|圖張量積}}是[[积 (范畴论)|範疇論積]]，{{link-en|赫德米猜想|Hedetniemi's conjecture|指數圖}}{{註|指數圖（{{lang|en|exponential graph}}）<math>H^G</math>的頂點是函數<math>f:V(G) \to V(H)</math>，兩頂點<math>f, g: V(G) \to V(H)</math>連邊當且僅當對<math>G</math>中任意兩個相鄰頂點<math>v, v'</math>，有<math>f(v)</math>與<math>g(v')</math>在<math>H</math>中相鄰。}}是該範疇的{{link-en|指數物件|exponential object}}。換言之，自<math>G \times H\to K</math>的同態與<math>H \to K^G</math>的同態[[自然變換|自然地]]一一對應。<ref name="lattices"/>{{sfn|Gray|2014}}由於對任意圖<math>G, H</math>，張量積<math>G \times H</math>與冪<math>H^G</math>總有定義，圖範疇是[[笛卡儿闭范畴]]。同理，同態等價類組成的格實際上是[[海廷代数]]：按海廷代數的語言，前述的積稱為[[交運算]]<math>\land</math>，而前述的指數運算稱為蘊涵<math>\Rightarrow</math>。<ref name="lattices"/>{{sfn|Gray|2014}}

對於有向圖，適用同樣的定義。同樣有<math>\to </math>是有向圖同態等價類之間的[[偏序关系|偏序]]，其與無向圖等價類的偏序<math>\to </math>有別，但後者是前者的子序，因為無向圖亦可視為有向圖，衹是其中每條有向邊<math>(u, v)</math>皆與其反向<math>(v, u)</math>成對出現。換言之，無向圖同態的定義，與雙向有向圖的同態並無區別。有向圖的<math>\to</math>序仍是分配格和海延代數，交與併的定義亦同上，但分別在於，該序並不稠密。亦有以有向圖為物件、同態為態射的範疇，照樣[[笛卡儿闭范畴|笛卡儿闭]]。{{sfn|Brown|Morris|Shrimpton|Wensley|2008}}{{sfn|Gray|2014}}
=== 不可比圖 ===
[[File:Groetzsch-graph.svg|thumb|upright=0.8|right|{{le|格勒奇圖|Grötzsch graph}}<!--按[[WP:外語譯音表/德語]]-->，與<math>K_3</math>不可比]]
同態預序下，許多圖不可比較。兩幅不可比圖（{{lang|en|incomparable graphs}}）之間，並無自任意一幅至另一幅的同態。{{sfn|Hell|Nešetřil|2004|p=7}}欲構造此種圖，可考慮圖的[[圍長 (圖論)|奇圍長]]，即最短的奇環長度。奇圍長可等價地說成最小的[[奇偶性 (数学)|奇數]]<math>g</math>，使<math>g</math>個頂點的[[循环图]]<math>C_g</math>有同態至<math>G</math>。由此定義，若<math>G \to H</math>，則<math>G</math>的奇圍長大於或等於<math>H</math>的奇圍長。{{sfn|Hahn|Tardif|1997|loc=Observation 2.6}}

另一方面，[[圖同態#與染色的關聯|前節]]已證若<math>G \to H</math>，則<math>G</math>的色數小於或等於<math>H</math>的色數。所以，若<math>G</math>的奇圍長及色數皆嚴格大於<math>H</math>，則<math>G</math>和<math>H</math>不可比較。{{sfn|Hell|Nešetřil|2004|p=7}}
舉例，{{link-en|格勒奇圖|Grötzsch graph}}色數為<math>4</math>，且無三角形（圍長<math>4</math>，奇圍長<math>5</math>）<ref>{{cite mathworld| title = Grötzsch Graph | urlname = GroetzschGraph}}</ref>，所以與三角形<math>K_3</math>不可比。

有幾類圖的奇圍長和色數可取任意大，如{{link-en|克內澤爾圖|Kneser graph}}{{sfn|Hahn|Tardif|1997|loc=Proposition 3.14}}與{{link-en|梅切爾斯基圖|Mycielskian|廣義梅切爾斯基圖}}<!--數學家{{le|Jan Mycielski}}，按[[WP:外語譯音表/波蘭語]]--><ref>{{citation|
title=On Graphs With Strongly Independent Color-Classes|trans-title = 論色類強獨立之圖|
first1=A.|last1=Gyárfás|first2=T.|last2=Jensen|first3=M.|last3=Stiebitz|
year=2004|doi=10.1002/jgt.10165|journal={{link-en|圖論期刊|Journal of Graph Theory|Journal of Graph Theory}}|volume=46|issue=1|pages=1–14}}</ref>。如此一類圖，若使其兩參數同時遞增，排成一列，則有無窮多幅不可比圖（同態預序下的[[反鏈]]）。{{sfn|Hell|Nešetřil|2004|loc=Proposition 3.4}}
同態預序{{link-en|稠密序|dense order|稠密}}等其他性質，亦可利用此類圖證明。{{sfn|Hell|Nešetřil|2004|p=96}}此外，可構造同時具大色數和大圍長（不僅是奇圍長）的圖，但較複雜，見{{section link|圍長 (圖論)#圍長與圖染色}}。

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

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

=== 至給定圖的同態 ===
圖同態問題若固定右邊的圖<math>H</math>不變，則稱為染<math>H</math>色問題。<math>H</math>為完全圖<math>K_k</math>時，化成[[图着色问题|染''k''色問題]]，在<math>k = 0, 1, 2</math>時，可於[[多項式時間]]內求解，但其餘情況則是[[NP完全]]。{{sfn|Hell|Nešetřil|2004|loc=§5.1}}<math>k = 2</math>的情況相當於問圖<math>G</math>可否染<math>K_2</math>色，即是否[[二分图|二部圖]]，此問題可在[[線性時間]]內求解。更一般地，衹要<math>H</math>是二部圖就有同一結論：可染<math>H</math>色等價於可染<math>K_2</math>色，即可染二色，故此種情況同樣易判斷。可染<math>K_0</math>色和可染<math>K_1</math>色分別等價於無頂點和無邊，亦易判斷。{{sfn|Hell|Nešetřil|2004|loc=Proposition 5.1}}{{link-en|帕沃爾·黑爾|Pavol Hell}}<!--《世界人名翻译大辞典》捷克語-->和{{link-en|雅羅斯拉夫·內舍特日爾|Jaroslav Nešetřil}}<!--沿用[[羅賓·托馬斯]]一文的譯法-->證明，對無向圖而言，無其他情況可馴順：

<blockquote>
（黑爾-內舍特日爾定理，1990年）若<math>H</math>為二部圖，則染<math>H</math>色問題屬於[[P (複雜度)|P]]，但其餘情況則為NP完全。{{sfn|Hell|Nešetřil|2004|loc=§5.2}}<ref>{{cite journal|first1=Pavol|last1=Hell|first2=Jaroslav|last2=Nešetřil|title=On the complexity of H-coloring|trans-title = 論染H色之複雜度|year=1990|journal={{link-en|Journal of Combinatorial Theory, Series B}}|volume=48|issue=1|pages=92–110|doi=10.1016/0095-8956(90)90132-J|doi-access=free|language = en}}</ref>
</blockquote>

上述定理又稱為無向圖同態的「對分定理」（{{lang|en|dichotomy theorem}}），因為將染<math>H</math>色問題分成NP完全與P兩類，而無{{link-en|NP中間|NP-intermediate|居中}}情況。有向圖情況較複雜，此時問題等價於刻畫看似更一般的{{link-en|約束滿足問題的複雜度|Complexity of constraint satisfaction}}{{sfn|Hell|Nešetřil|2004|loc=§5.3}}：有向圖的染<math>H</math>色問題，與允許各種約束條件的{{lang|en|CSP}}相比，同樣多姿多彩，而不失一般性。{{sfn|Hell|Nešetřil|2004|loc=Theorem 5.14}}<ref name="FederVardi">{{cite journal|first1=Tomás|last1=Feder|first2=Moshe Y.|last2=Vardi|title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory|trans-title=單調單子SNP與約束滿足之計算結構：藉Datalog與群論研究|year=1998|journal={{link-en|SIAM Journal on Computing}}|volume=28|issue=1|pages=57–104|doi=10.1137/S0097539794266766|url=http://theory.stanford.edu/~tomas/constraint.ps|language=en|access-date=2022-02-06|archive-date=2022-02-06|archive-url=https://web.archive.org/web/20220206173456/http://theory.stanford.edu/~tomas/constraint.ps}}</ref>嚴格而言，定義（有限）約束語言（{{lang|en|constraint language}}，或稱模板{{lang|en|template}}）<math>\Gamma</math>為一個有限的取值域，其上配備有限多種[[關係 (數學)|關係]]，然後以<math>\mathsf{CSP}(\Gamma)</math>表示約束衹能選自<math>\Gamma</math>的一類約束滿足問題，則有以下定理：

<blockquote>
（费德、{{link-en|摩西·瓦迪|Moshe Y. Vardi|瓦迪}}<!--沿用[[哈里·H·古德紀念獎]]一文的譯法-->，1998年）對任意約束語言<math>\Gamma</math>，必有某幅有向圖<math>H</math>，使<math>\mathsf{CSP}(\Gamma)</math>在[[多项式时间归约]]意義下等價於染<math>H</math>色問題。<ref name="FederVardi"/>
</blockquote>

直觀理解，定理意味着任何算法技巧或複雜度結論，若適用於一般有向圖<math>H</math>的染<math>H</math>色問題，則可套用至一般{{lang|en|CSP}}。考慮將黑爾-內舍特日爾定理擴展至有向圖。由上述定理，該推廣等價於有關{{lang|en|CSP}}對分的费德-瓦迪猜想（又稱{{lang|en|CSP}}猜想、對分猜想），即斷言對任意約束語言<math>\Gamma</math>，<math>\mathsf{CSP}(\Gamma)</math>或屬NP完全，或屬P。{{sfn|Bodirsky|2007|loc=§1.3}}此猜想於2017年由德米特里·祖克（{{lang|en|Dmitry Zhuk}}）<!--沿用[[亞歷山大·扎伊采夫]]文中Stanislav Zhuk的姓-->與安德烈·布拉托夫（{{lang|en|Andrei Bulatov}}）<!--《世界人名翻译大辞典》-->分別獨立證出，故有以下推論：

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

=== 自給定族的同態 ===
若左輸入<math>G</math>為給定，則圖同態問題有[[暴力搜索|暴力解法]]，即窮舉<math>G</math>的各個頂點在<math>H</math>中的像，複雜度僅為<math>\mathcal O\left(|V(H)|^{|V(G)|}\right)</math>，已是輸入<math>H</math>的多項式函數。<ref>{{cite conference|title=Tight bounds for graph homomorphism and subgraph isomorphism|trans-title = 圖同態與子圖同構之緊限界|authors=Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A.|conference=28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)|publisher={{link-en|Society for Industrial and Applied Mathematics|Society for Industrial and Applied Mathematics|SIAM}}|year=2016|arxiv=1507.03738|pages=1643–1649|isbn=978-1-611974-33-1|bibcode=2015arXiv150703738F|language = en}}</ref>換言之，限制<math>G</math>的大小時，問題顯然屬P，但仍可改為研究另一課題：除大小之外，是否其他限制可施加於<math>G</math>，使圖同態問題可於多項式時間內求解？

研究表明，關鍵性質是{{link-en|樹闊|treewidth}}，此參數衡量一幅圖有多似一棵樹。若<math>G</math>的樹闊至多為<math>k</math>，而<math>H</math>為任意圖，則利用標準的[[动态规划]]方法，可於<math>|V(H)|^{\mathcal O(k)}</math>時間內求解圖同態問題。實際甚至衹需假設<math>G</math>的核的樹闊不逾<math>k</math>，而無需知道其核為何。<ref>{{cite conference|first1=Víctor|last1=Dalmau|first2=Phokion G.|last2=Kolaitis|first3=Moshe Y.|last3=Vardi|title=Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics|trans-title = 約束滿足、有界樹闊、有限變數邏輯|conference=8th International Conference on Principles and Practice of Constraint Programming (CP 2002)|pages=310–326|year=2002|doi=10.1007/3-540-46135-3_21|language = en}}</ref><ref name="Grohe">{{citation|first=Martin|last=Grohe|authorlink=Martin Grohe|title=The complexity of homomorphism and constraint satisfaction problems seen from the other side|trans-title = 同態與約束滿足之複雜度，自另一方面觀之|volume=54|issue=1|pages=1–es|year=2007|journal=[[ACM期刊|Journal of the ACM]]|doi=10.1145/1206035.1206036|s2cid=11797906|language = en}}</ref>

該<math>|V(H)|^{\mathcal O(k)}</math>算法中，複雜度的指數可能無法再壓低太多：若{{link-en|指數時間假設|exponential time hypothesis}}{{註|指數時間假設與[[P/NP问题|P ≠ NP]]類似，皆是未獲證的複雜度假設，但前者更強。}}（{{lang|en|ETH}}）為真，則不存在時間複雜度為<math>|V(H)|^{o(\mathrm{tw}(G) / \log \mathrm{tw}(G))}</math>的算法。即使限制<math>G</math>衹能取值為某一族圖，衹要該族圖的樹闊無上界，則仍有同樣結論。<ref name="marx">{{citation|first=Dániel|last=Marx|title=Can You Beat Treewidth?|trans-title = 可以勝過樹闊乎？|journal=[[計算理論期刊|Theory of Computing]]|year=2010|volume=6|pages=85–112|doi=10.4086/toc.2010.v006a005|doi-access=free|language = en}}</ref>同樣假設下，幾乎沒有其他性質使問題可於多項式時間內求解，具體含義如下：

<blockquote>
（{{link-en|馬丁·格罗厄|Martin Grohe|格罗厄}}）假定{{lang|en|ETH}}，並給定由圖組成的[[递归集合|可計算]]族<math>\mathcal{G}</math>。考慮輸入為<math>(G,H)</math>，且<math>G \in \mathcal{G}</math>的圖同態問題。此問題屬P當且僅當<math>\mathcal{G}</math>中各圖之核的樹闊有界。<ref name="Grohe"/>
</blockquote>

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

同一命題對其他關係結構亦成立。換言之，其適用於一般的約束滿足問題，不過需要限制各項約束涉及的變量數有上界，即關係的[[元數]]有上界（以圖為例，僅得元數為2的關係）。此時，關鍵參數為{{link-en|原始約束圖|primal constraint graph}}{{註|約束滿足問題中，以變數為頂點，兩變數有出現在同一個約束中則連邊，可得「原始約束圖」。此即以各約束為邊的[[超圖]]的{{le|原始圖|primal graph}}。}}的樹闊。<ref name="marx"/>

== 參見 ==
* [[图论术语]]
* [[同态]]，其他代數結構的同一概念
* {{link-en|圖重寫|Graph rewriting}}
* {{link-en|中位圖|Median graph}}，可定義成{{link-en|超立方圖|hypercube graph}}的收縮核
* {{link-en|西多连科猜想|Sidorenko's conjecture}}<!--世界人名翻译大辞典-->

== 註 ==
{{備註表}}

== 參考資料 ==
{{reflist|30em}}
=== 一般書目、解說 ===
* {{cite web|first=P.|last=Cameron|title=Graph Homomorphisms, Combinatorics Study Group Notes|trans-title=圖同態，組合研習小組講義|year=2006|url=http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf|ref=harv|language=en|access-date=2022-02-12|archive-date=2021-05-07|archive-url=https://web.archive.org/web/20210507001500/http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf}}
* {{cite book|last1=Hell|first1=Pavol|last2=Nešetřil|first2=Jaroslav|publisher=Oxford University Press|title=Graphs and Homomorphisms|trans-title=圖與同態|series=Oxford Lecture Series in Mathematics and Its Applications|volume=28|year=2004|isbn=0-19-852817-5|url=http://www.cs.sfu.ca/~pavol/hombook.html|language=en|ref=harv|access-date=2022-02-12|archive-date=2021-05-06|archive-url=https://web.archive.org/web/20210506175223/https://www2.cs.sfu.ca/~pavol/hombook.html}}
* {{cite chapter|first1=G.|last1=Hahn|first2=C.|last2=Tardif|chapter=Graph homomorphisms: structure and symmetry|trans-chapter=圖同態：結構與對稱|title=Graph Symmetry: Algebraic Methods and Applications|trans-title=圖對稱：代數方法及應用|publisher=Springer|year=1997|pages=107–166|doi=10.1007/978-94-015-8937-6_4|url=http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf|language=en|ref=harv|access-date=2022-02-12|archive-date=2021-07-11|archive-url=https://web.archive.org/web/20210711070549/https://mast.queensu.ca/~ctardif/articles/ghss.pdf}}
* {{cite chapter|first1=C.|last1=Godsil |first2=G.|last2=Royle|title=Algebraic Graph Theory|trans-title = 代數圖論|doi=10.1007/978-1-4613-0163-9|isbn=978-1-4613-0163-9|year=2001|publisher=Springer–Verlag New York|series=Graduate Texts in Mathematics|volume=207|chapter=6. Homomorphisms|trans-chapter = 6、同態|language = en|ref=harv}}

=== 約束滿足、泛代數 ===
* {{cite web|first1=M.|last1=Bodirsky|title=Graph Homomorphisms and Universal Algebra, Course Notes|trans-title=圖同態與泛代數，講義|url=https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf|year=2007|language=en|ref=harv|access-date=2022-02-12|archive-date=2022-05-01|archive-url=https://web.archive.org/web/20220501142243/https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf}}
* {{cite journal|first1=Pavol|last1=Hell|first2=Jaroslav|last2=Nešetřil|title=Colouring, constraint satisfaction, and complexity|trans-title=染色、約束滿足、複雜度|year=2008|journal=Computer Science Review|volume=2|issue=3|pages=143–163|doi=10.1016/j.cosrev.2008.10.003|url=http://www.cs.sfu.ca/~pavol/cspCCC.pdf|language=en|ref=harv|access-date=2022-02-12|archive-date=2017-07-06|archive-url=https://web.archive.org/web/20170706115247/http://www.cs.sfu.ca/~pavol/cspCCC.pdf}}

=== 格論、範疇論 ===
* {{cite journal|first1=R.|last1=Brown|first2=I.|last2=Morris|first3=J.|last3=Shrimpton|first4=C. D.|last4=Wensley|title=Graphs of morphisms of graphs|trans-title=圖態射之圖|journal={{le|Electronic Journal of Combinatorics}}|year=2008|volume=15|issue=1|page=A1|doi=10.37236/919|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1|doi-access=free|language=en|ref=harv|access-date=2022-02-12|archive-date=2021-07-11|archive-url=https://web.archive.org/web/20210711045636/https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1}}
* {{cite web|first=C. T.|last=Gray|title=The Digraph Lattice|trans-title=有向圖之格|year=2014|url=http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf|language=en|ref=harv|access-date=2022-02-12|archive-date=2022-01-20|archive-url=https://web.archive.org/web/20220120165848/http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf}}

[[Category:图论]]
[[Category:态射]]