图同态

<image>

数学分支图论中，图同态（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_0v_1$、$u_1 v_0$。如此，可以定义函数将$v_0$和$v_1$皆映至$v$，既是图同态，也是覆叠映射。

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

### 核与回缩

<image>

若两幅图$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$）。1a1=Cameron此结论对无穷图不一定成立，但对（有限的）有向图可以照套用同样的定义，每幅有向图同态等价于唯一的核图。图（或有向图）的核，必为原图某个收缩核，以及某个导出子图。

举例，完全图$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$的同态，两类物件一一对应1a1=Cameron，因为$K_k$的各顶点对应$k$种色，且若$c_1, c_2$为颜色，则其于图$K_k$相邻当且仅当$c_1 \neq c_2$。于是，某函数是$G$至$K_k$的同态，当且仅当该函数将$G$中相邻的顶点映至不同颜色（即$k$染色的定义）。换言之，$G$可染$k$色等价于可染$K_k$色。1a1=Cameron

若有同态$G \to H$及$H \to K_k$，则两者复合可得同态$G \to K_k$。所以，若$H$可染$k$色，且有同态$G \to H$，则$G$同样可染$k$色。因此，$G \to H$推出$\chi(G) \le \chi(H)$，其中$\chi$表示图的色数使该图可染$k$色的最小$k$值。

### 变式

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

- 循环染色可定义为至循环完全图取$0$至$n-1$为$n$个顶点，相异两点$u, v$间有连边当且仅当模$n$运算时，$|u - v|$大于某定值。同态，从而推广一般的染色，定义“分数”色数。1a1=Hell
- 分数染色与分数染色可定义成射向克内泽尔图的同态。1a1=Hell
- 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}}$ $\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$的有向路径”不允许重复顶点。

## 与约束满足问题的关联

### 范例

<image>

某些排程问题可用图同态建模。设学校已知各学生所选科目，要编排今学期各专题讨论班的时间，使同一学生所选的讨论班时间不致太近。考虑图$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$。1a1=Hell例如，任意两幅整数阶完全图（除$K_0, K_1, K_2$外）之间，必有无穷多幅环状团，相当于整阶数之间的有理数阶数。1a1=Hell

同态等价类的偏序集是分配格，并$[G]\lor[H]$是互斥并$[G \sqcup H]$，而交$[G] \land [H]$是图张量积$[G\times H]$，其定义不取决于等价类中所选的代表$G, H$。此格中，并不可约$x$为并不可约，意即$x= a \lor b$推出$x = a$或$x = b$。对偶概念为交不可约。正好是连通图，证明方式是留意同态只会将连通图映到目标的一个连通分支中。交不可约正好是赫德米猜想（multiplicative graphs），此种图$K$的特性是，若乘积$G \times H$有同态至$H$，则$G$或$H$两者之一有同态至$H$。如何识别积性图是赫德米猜想的关键。

图与同态还组成范畴：图是物件，而同态是态射。范畴的始物件是空图$K_0$，终物件有一个顶点和一个自环。图张量积是范畴论积，赫德米猜想指数图（exponential graph）$H^G$的顶点是函数$f:V(G) \to V(H)$，两顶点$f, g: V(G) \to V(H)$连边当且仅当对$G$中任意两个相邻顶点$v, v'$，有$f(v)$与$g(v')$在$H$中相邻。是该范畴的指数物件。换言之，自$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$序仍是分配格和海延代数，交与并的定义亦同上，但分别在于，该序并不稠密。亦有以有向图为物件、同态为态射的范畴，照样笛卡儿闭。

### 不可比图

<image>

同态预序下，许多图不可比较。两幅不可比图（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 \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完全。

上述定理又称为无向图同态的“对分定理”（dichotomy theorem），因为将染$H$色问题分成NP完全与P两类，而无NP中间情况。有向图情况较复杂，此时问题等价于刻画看似更一般的约束满足问题的复杂度：有向图的染$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)}$算法中，复杂度的指数可能无法再压低太多：若指数时间假设指数时间假设与P ≠ NP类似，皆是未获证的复杂度假设，但前者更强。（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}$中各图之核的树阔有上界，则该问题为固定参数可驯顺，否则为带参数复杂度完全。

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

## 参见

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