图同态

  关于两幅图如何算是“完全一样”，请见“图同构”。

  关于允许将边映成路径的映射，请见“图同胚”。

由花形蛇鲨图J₅射向环图C₅的同态，亦是到J₅中央五个顶点所成子图的收缩，所以J₅与其核C₅“同态等价”。

数学分支图论中，图同态（英语：graph homomorphism）是两幅图之间保结构的映射。具体而言，该映射将某图的各顶点映至另一图的顶点，且若两顶点相邻，则其像仍然相邻。

同态是若干种图着色概念的推广，适用于表达一类重要的约束满足问题，如调度、频段分配问题。同态可以复合，为全体图组成的类赋予丰富的代数结构：其上的预序关系、分配格结构、范畴结构（分为无向图范畴与有向图范畴两种）。欲查找任意两图间的同态，而无额外条件，则现时所知的计算复杂度高得不切实际，但对于某些特定类别的图，已知有多项式时间算法。此类问题易解与否，两者的分野，是活跃的研究方向。

定义

本条目中，除非另有声明，否则“图”皆为有限无向图，允许自环，但无重边（两点间连多于一条边）。自$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$同态于（homomorphic to）$H$，或可染$H$色（$H$-colourable），常简记为：

$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_{0}v_{1}$、$u_{1}v_{0}$。如此，可以定义函数将$v_{0}$和$v_{1}$皆映至$v$，既是图同态，也是覆叠映射。

图同胚是另一个概念，不一定是同态。粗略而言，同胚要求是单射，但不必将边映至边，允许映至路径。图子式的要求更松。

核与回缩

K₇，七个顶点的完全图，一种核图

主条目：核图

若两幅图$G$和$H$有同态$G\to H$及$H\to G$，则称两者同态等价（homomorphically equivalent）。该些映射不必单，也不必满。例如，完全二部图$K_{2,2}$与$K_{3,3}$同态等价，因为可将$K_{2,2}$左部两个顶点映到$K_{3,3}$左部同一个顶点，其右部的两个顶点映到$K_{3,3}$右部一个顶点，同样有$K_{3,3}\to K_{2,2}$的同态。

收缩映射（retraction）是自图$G$至其子图$H$的同态$r$，且对$H$中每个顶点$v$有$r(v)=v$。若有此种映射，则$H$称为$G$的收缩核（retract）。

核图（core）没有到任何真子图的同态。亦可等价定义成无法收缩到任何真子图的图。每幅图$G$皆同态等价于唯一的核图（不辨同构之别），称为$G$的核（the core of $G$）。此结论对无穷图不一定成立，但对（有限的）有向图可以照套用同样的定义，每幅有向图同态等价于唯一的核图。图（或有向图）的核，必为原图某个收缩核，以及某个导出子图。

举例，完全图$K_{n}$及奇环（奇数条边的循环图）皆属核图。若$G$可染三色，且有三角形（即子图$K_{3}$），则$G$同态等价于$K_{3}$，原因是$G$的三染色，下节将说明相当于同态$G\to K_{3}$，且另一方面，任意子图皆有同态嵌入到$G$，故有$K_{3}\to G$。如此，证毕$K_{3}$为所有此种$G$的核。与之相似，每幅非空二部图（有至少一条边）皆等价于$K_{2}$。

与染色的关系

对正整数$k$，图$G$的$k$染色是将每个顶点涂$k$色之一，使每条边的两端都不同色。此种染色，与自$G$至完全图$K_{k}$的同态，两类对象一一对应，因为$K_{k}$的各顶点对应$k$种色，且若$c_{1},c_{2}$为颜色，则其于图$K_{k}$相邻当且仅当$c_{1}\neq c_{2}$。于是，某函数是$G$至$K_{k}$的同态，当且仅当该函数将$G$中相邻的顶点映至不同颜色（即$k$染色的定义）。换言之，$G$可染$k$色等价于可染$K_{k}$色。

若有同态$G\to H$及$H\to K_{k}$，则两者复合可得同态$G\to K_{k}$。所以，若$H$可染$k$色，且有同态$G\to H$，则$G$同样可染$k$色。因此，$G\to H$推出$\chi (G)\leq \chi (H)$，其中$\chi$表示图的色数。

变式

其他同态亦可视作特殊的染色。给定图$H$，其顶点视为可用的颜色，每条边表示某两色“可兼容”，则$G$的$H$染色就是将相邻顶点染成兼容颜色的方案。此框架可容纳许多图染色的概念，将其表述为射向各类图的同态。举例如下：

• 循环染色可定义为至循环完全图的同态，从而推广一般的染色，定义“分数”色数。
• 分数染色与b重染色可定义成射向克内泽尔图的同态。
• T染色的可用色集为自然数集$\mathbb {N}$，但另有给定某子集$T\subseteq \mathbb {N}$，禁止相邻顶点所染颜色之差属于$T$。此种染色对应往某幅无穷图的同态。
• 有向染色除禁止相邻顶点同色外，还限制不同颜色之间的所有边皆同向（例如由蓝至红）。此为映向有向图的同态。
• L(2,1)染色以数表示颜色，要求距离为1（相邻）的顶点所染颜色之差至少为2，而距离为2的顶点染色之差至少为1。换言之，此为射向路图$P_{n}$之补的同态，且要求局部为单射，即在每个顶点的邻域上为单射。

无长路径的定向

主条目：高洛伊-哈塞-罗伊-维塔韦尔定理

图同态与图定向也有关。无向图$G$的定向是赋予每边一个方向（二选一），所得的有向图。同一幅无向图可以有多种不同的定向。举例，完全图$K_{k}$可定向成“传递循环赛图”${\overrightarrow {T_{k}}}$，其顶点为$1,2,\ldots ,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}}}$的同态。

有定理流传，对每个$k$，有向图$G$有同态至${\overrightarrow {T_{k}}}$，当且仅当$k+1$个顶点的有向路径图${\overrightarrow {P_{k+1}}}$无同态至$G$。

因此，某图可$k$染色，当且仅当其有某定向，不容任何自${\overrightarrow {P_{k+1}}}$至该定向的同态。此命题可加强成

高洛伊-哈塞-罗伊-维塔韦尔定理：某图可$k$染色，当且仅当该图有某定向，其中无长为$k$的有向路径（即${\overrightarrow {P_{k+1}}}$作为子图）。

与前一命题的分别在于，自${\overrightarrow {P_{k+1}}}$至某图的同态允许将两顶点映至同处，但“长为$k$的有向路径”不允许重复顶点。

与约束满足问题的关系

示例

图$H$，表示一周中不相邻的日子，同构于环$C_{7}$的补图，亦同构于环状团$K_{7/2}$

某些调度问题可用图同态建模。设学校已知各学生所选科目，要编排今学期各专题讨论班的时间，使同一学生所选的讨论班时间不致太近。考虑图$G$以各科为顶点，若两科有共同学生则连边，而图$H$以各课节为顶点，若两个时段隔足够远则连边。举例若限制时间表须每周循环，且每个学生所选的讨论班须相隔一日，则对应的$H$是环$C_{7}$的补图。如此，$G\to H$的图同态，就是讨论班对应到课节的合适方案。欲添加额外条件，如禁止学生同时于周五与周一有讨论班，只需从$H$删掉相应的边。

无线电的频段分配问题简述如下：无线网络中，有若干发讯机，要为每部机配置一个频率，供其发讯。为免干扰，地理位置较近的发讯机应选用相差较远的频率。若将条件中“地理较近”与“频率较远”简化至非黑即白，则合适的分配方案又可视为图同态$G\to H$。图$G$的顶点为各发讯机，边表示两机地理上接近；图$H$以各频段为顶点，边则表示两频段相隔够远。虽然此模型甚为简化，但是尚有保留一点弹性：若有两机相隔较远，但仍因地形导致可能干扰，则在$G$中加边即可。反之，若有两机永不在同一时段发讯，则不论其地理位置是否靠近，皆可从$G$中删去该边。同样，或许有某些频率相差颇远，但是互为谐波，导致干扰，则将该边自$H$移除即可

前述模型经简化，若要实际应用，许多问题仍待解决。约束满足问题是图同态问题的推广，能表达更多种条件（例如个体偏好，或重复分配次数有上限），从而建立更实际的数学模型。

抽象观点

数理逻辑或泛代数中，图与有向图属关系结构的特例，即集合配备若干关系。有向图就是基集（顶点集）之上有独一个二元关系（邻接关系）。如是观之，图作为关系结构的同态，按抽象代数的同态定义，等同于本文的图同态。一般而言，欲查找自某关系结构至另一关系结构的同态，属于约束满足问题（constraint satisfaction problem, CSP）。图的特例可作为第一步，帮助理解更复杂的CSP。许多查找图同构的算法，包括回溯、约束传播、局部搜索，通用于各种CSP。

给定图$G$、$H$，问是否有同态$G\to H$，相当于仅得一类约束的CSP实例：CSP的“变量”是$G$的顶点，每个变量的“域”（可取值的范围）是$H$的顶点集。“赋值”是一个函数，将逐个变量映至域的元素，即函数$f:V(G)\to V(H)$。$G$的每条边（或有向边）$(u,v)$对应一个“约束”$((u,v),E(H))$，限制赋值函数将边$(u,v)$映至关系$E(H)$中，即映至$H$的某边。CSP的“解”是满足全体约束的赋值，故前述CSP的解正是自$G$至$H$的同态。

同态的结构

同态的复合仍是同态，故可知图的$\to$关系具传递性，又显然自反，所以其为图之间的预序。同态等价意义下，记$G$所属等价类为$[G]$，每个等价类有唯一的核图为其代表。关系$\to$定义该些等价类之间的偏序，即同态等价类构成一个偏序集。

以$G<H$表示$G$有同态至$H$，但反之则不然。如此定义的序$<$稠密，即对任意（无向）图$G,H$，若$G<H$，则存在第三幅图$K$使$G<K<H$，除非是平凡反例$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$。此格中，并不可约元正好是连通图，证明方式是留意同态只会将连通图映到目标的一个连通分支中。交不可约元正好是积性图（multiplicative graphs），此种图$K$的特性是，若乘积$G\times H$有同态至$H$，则$G$或$H$两者之一有同态至$H$。如何识别积性图是赫德米猜想的关键。

图与同态还组成范畴：图是对象，而同态是态射。范畴的始对象是空图$K_{0}$，终对象有一个顶点和一个自环。图张量积是范畴论积，指数图是该范畴的指数对象。换言之，自$G\times H\to K$的同态与$H\to K^{G}$的同态自然地一一对应。由于对任意图$G,H$，张量积$G\times H$与幂$H^{G}$总有定义，图范畴是笛卡儿闭范畴。同理，同态等价类组成的格实际上是海廷代数：按海廷代数的语言，前述的积称为交运算$\land$，而前述的指数运算称为蕴涵$\Rightarrow$。

对于有向图，适用同样的定义。同样有$\to$是有向图同态等价类之间的偏序，其与无向图等价类的偏序$\to$有别，但后者是前者的子序，因为无向图亦可视为有向图，只是其中每条有向边$(u,v)$皆与其反向$(v,u)$成对出现。换言之，无向图同态的定义，与双向有向图的同态并无区别。有向图的$\to$序仍是分配格和海延代数，交与并的定义亦同上，但分别在于，该序并不稠密。亦有以有向图为对象、同态为态射的范畴，照样笛卡儿闭。

不可比图

格勒奇图，与$K_{3}$不可比

同态预序下，许多图不可比较。两幅不可比图（incomparable graphs）之间，并无自任意一幅至另一幅的同态。欲构造此种图，可考虑图的奇围长，即最短的奇环长度。奇围长可等价地说成最小的奇数$g$，使$g$个顶点的循环图$C_{g}$有同态至$G$。由此定义，若$G\to H$，则$G$的奇围长大于或等于$H$的奇围长。

另一方面，前节已证若$G\to H$，则$G$的色数小于或等于$H$的色数。所以，若$G$的奇围长及色数皆严格大于$H$，则$G$和$H$不可比较。 举例，格勒奇图色数为$4$，且无三角形（围长$4$，奇围长$5$），所以与三角形$K_{3}$不可比。

有几类图的奇围长和色数可取任意大，如克内泽尔图与广义梅切尔斯基图。如此一类图，若使其两参数同时递增，排成一列，则有无穷多幅不可比图（同态预序下的反链）。 同态预序稠密等其他性质，亦可利用此类图证明。此外，可构造同时具大色数和大围长（不仅是奇围长）的图，但较复杂，见围长 (图论) § 围长与图染色。

有向图之中，更易找到不可比图。例如，考虑有向环${\overrightarrow {C_{n}}}$，顶点为$1,2,\ldots ,n$，有向边自$i$至$i+1$（对$i=1,2,\ldots ,n-1$各一），及自$n$至$1$。对于$n,k\geq 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完全。

上述定理又称为无向图同态的“对分定理”（dichotomy theorem），因为将染$H$色问题分成NP完全与P两类，而无居中情况。有向图情况较复杂，此时问题等价于刻画看似更一般的约束满足问题的复杂度：有向图的染$H$色问题，与允许各种约束条件的CSP相比，同样多姿多彩，而不失一般性。严格而言，定义（有限）约束语言（constraint language，或称模板template）$\Gamma$为一个有限的取值域，其上配备有限多种关系，然后以${\mathsf {CSP}}(\Gamma )$表示约束只能选自$\Gamma$的一类约束满足问题，则有以下定理：

（费德、瓦迪，1998年）对任意约束语言$\Gamma$，必有某幅有向图$H$，使${\mathsf {CSP}}(\Gamma )$在多项式时间归约意义下等价于染$H$色问题。

直观理解，定理意味着任何算法技巧或复杂度结论，若适用于一般有向图$H$的染$H$色问题，则可套用至一般CSP。考虑将黑尔-内舍特日尔定理扩展至有向图。由上述定理，该推广等价于有关CSP对分的费德-瓦迪猜想（又称CSP猜想、对分猜想），即断言对任意约束语言$\Gamma$，${\mathsf {CSP}}(\Gamma )$或属NP完全，或属P。此猜想于2017年由德米特里·祖克（Dmitry Zhuk）与安德烈·布拉托夫（Andrei Bulatov）分别独立证出，故有以下推论：

（布拉托夫2017年；祖克2017年）给定$H$时，有向图的染$H$色问题或属P，或属NP完全。

自给定族的同态

若左输入$G$为给定，则图同态问题有暴力解法，即穷举$G$的各个顶点在$H$中的像，复杂度仅为${\mathcal {O}}\left(|V(H)|^{|V(G)|}\right)$，已是输入$H$的多项式函数。换言之，限制$G$的大小时，问题显然属P，但仍可改为研究另一课题：除大小之外，是否其他限制可施加于$G$，使图同态问题可于多项式时间内求解？

研究表明，关键性质是树阔，此参数衡量一幅图有多似一棵树。若$G$的树阔至多为$k$，而$H$为任意图，则利用标准的动态规划方法，可于$|V(H)|^{{\mathcal {O}}(k)}$时间内求解图同态问题。实际甚至只需假设$G$的核的树阔不逾$k$，而无需知道其核为何。

该$|V(H)|^{{\mathcal {O}}(k)}$算法中，复杂度的指数可能无法再压低太多：若指数时间假设（ETH）为真，则不存在时间复杂度为$|V(H)|^{o(\mathrm {tw} (G)/\log \mathrm {tw} (G))}$的算法。即使限制$G$只能取值为某一族图，只要该族图的树阔无上界，则仍有同样结论。同样假设下，几乎没有其他性质使问题可于多项式时间内求解，具体含义如下：

（格罗厄）假定ETH，并给定由图组成的可计算族${\mathcal {G}}$。考虑输入为$(G,H)$，且$G\in {\mathcal {G}}$的图同态问题。此问题属P当且仅当${\mathcal {G}}$中各图之核的树阔有界。

或考虑有所取舍，允许复杂度高度依赖$G$，换取复杂度与$H$的关系仅为固定的多项式。与前段类似，若$G$的取值范围中，核的树阔有界，则此目标可以实现，但若$G$的取值范围不满足该条件，则无法达成。利用带参数复杂度术语，上述成果可覆述为：${\mathcal {G}}$中的同态问题，以$G$的边数为参数，呈现对分现象。若${\mathcal {G}}$中各图之核的树阔有上界，则该问题为固定参数可驯顺，否则为W[1]完全。

同一命题对其他关系结构亦成立。换言之，其适用于一般的约束满足问题，不过需要限制各项约束涉及的变量数有上界，即关系的元数有上界（以图为例，仅得元数为2的关系）。此时，关键参数为原始约束图的树阔。

参见

• 图论术语
• 同态，其他代数结构的同一概念
• 图重写
• 中位图，可定义成超立方图的收缩核
• 西多连科猜想

参考资料

一般书目、解说

• Cameron, P. Graph Homomorphisms, Combinatorics Study Group Notes [图同态，组合研习小组讲义] (PDF). 2006 [2022-02-12]. （原始内容 (PDF)存档于2021-05-07） （英语）. 
• Hell, Pavol; Nešetřil, Jaroslav. Graphs and Homomorphisms [图与同态]. Oxford Lecture Series in Mathematics and Its Applications 28. Oxford University Press. 2004 [2022-02-12]. ISBN 0-19-852817-5. （原始内容存档于2021-05-06） （英语）. 
• Hahn, G.; Tardif, C. Graph homomorphisms: structure and symmetry [图同态：结构与对称]. Graph Symmetry: Algebraic Methods and Applications [图对称：代数方法及应用] (PDF). Springer. 1997: 107–166 [2022-02-12]. doi:10.1007/978-94-015-8937-6_4. （原始内容 (PDF)存档于2021-07-11） （英语）. 
• Godsil, C.; Royle, G. 6. Homomorphisms [6、同态]. Algebraic Graph Theory [代数图论]. Graduate Texts in Mathematics 207. Springer–Verlag New York. 2001. ISBN 978-1-4613-0163-9. doi:10.1007/978-1-4613-0163-9 （英语）. 

约束满足、泛代数

• Bodirsky, M. Graph Homomorphisms and Universal Algebra, Course Notes [图同态与泛代数，讲义] (PDF). 2007 [2022-02-12]. （原始内容 (PDF)存档于2022-05-01） （英语）. 
• Hell, Pavol; Nešetřil, Jaroslav. Colouring, constraint satisfaction, and complexity [染色、约束满足、复杂度] (PDF). Computer Science Review. 2008, 2 (3): 143–163 [2022-02-12]. doi:10.1016/j.cosrev.2008.10.003. （原始内容 (PDF)存档于2017-07-06） （英语）. 

格论、范畴论

• Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. Graphs of morphisms of graphs [图态射之图]. Electronic Journal of Combinatorics. 2008, 15 (1): A1 [2022-02-12]. doi:10.37236/919 . （原始内容存档于2021-07-11） （英语）. 
• Gray, C. T. The Digraph Lattice [有向图之格] (PDF). 2014 [2022-02-12]. （原始内容 (PDF)存档于2022-01-20） （英语）.