关于兩幅圖如何算是「完全一樣」,请见「
圖同構 」。
关于允許將邊映成路徑的映射,请见「
圖同胚 」。
由花形蛇鯊圖 J 5 射向環圖C 5 的同態,亦是到J 5 中央五個頂點所成子圖的收縮,所以J 5 與其核 C 5 「同態等價」。
数学 分支圖論 中,圖同態 (英語:graph homomorphism )是兩幅图 之間保結構的映射 。具體而言,該映射將某圖的各顶点 映至另一圖的頂點,且若兩頂點相鄰,則其像 仍然相鄰。
同態是若干種圖着色 概念的推廣,適用於表達一類重要的約束滿足問題 ,如排程 、頻段分配 問題。同態可以複合 ,為全體圖組成的類 賦予豐富的代數結構:其上的预序关系 、分配格結構 、範疇結構 (分為無向圖範疇 與有向圖範疇兩種)。欲尋找任意兩圖間的同態,而無額外條件,則現時所知的計算複雜度 高得不切實際,但對於某些特定類別的圖,已知有多項式時間 算法。此類問題易解與否,兩者的分野,是活躍的研究方向。
定義
本條目中,除非另有聲明,否則「圖」皆為有限無向圖 ,允許自环 ,但無重边 (兩點間連多於一條邊)。自
G
=
(
V
(
G
)
,
E
(
G
)
)
{\displaystyle G=(V(G),E(G))}
至另一圖
H
=
(
V
(
H
)
,
E
(
H
)
)
{\displaystyle H=(V(H),E(H))}
的圖同態 [ 4]
f
{\displaystyle f}
,記作
f
:
G
→
H
,
{\displaystyle f:G\to H,}
是頂點集
V
(
G
)
{\displaystyle V(G)}
至
V
(
H
)
{\displaystyle V(H)}
的函數,其將
G
{\displaystyle G}
每條邊的兩端分別映至
H
{\displaystyle H}
某邊的兩端。以符號表示:對
V
(
G
)
{\displaystyle V(G)}
中每對頂點
u
,
v
{\displaystyle u,v}
,若
{
u
,
v
}
∈
E
(
G
)
{\displaystyle \{u,v\}\in E(G)}
,則
{
f
(
u
)
,
f
(
v
)
}
∈
E
(
H
)
{\displaystyle \{f(u),f(v)\}\in E(H)}
。若存在
G
{\displaystyle G}
至
H
{\displaystyle H}
的同態,則稱
G
{\displaystyle G}
同態於 (homomorphic to )
H
{\displaystyle H}
,或可染
H
{\displaystyle H}
色 (
H
{\displaystyle H}
-colourable ),常簡記為:
G
→
H
.
{\displaystyle G\to H.}
上述定義可引伸至有向圖 ,此時,
f
:
G
→
H
{\displaystyle f:G\to H}
為同態的條件是,
G
{\displaystyle G}
中每條有向邊
(
u
,
v
)
{\displaystyle (u,v)}
的像
(
f
(
u
)
,
f
(
v
)
)
{\displaystyle (f(u),f(v))}
,仍是
H
{\displaystyle H}
的有向邊。
自
G
{\displaystyle G}
至
H
{\displaystyle H}
有單 同態(將不同頂點映至不同頂點),當且僅當
G
{\displaystyle G}
為
H
{\displaystyle H}
的子圖 。若同態
f
:
G
→
H
{\displaystyle f:G\to H}
為双射 (兩圖頂點集的一一對應 ),且其逆
f
−
1
{\displaystyle f^{-1}}
亦是圖同態,則
f
{\displaystyle f}
為图同构 。
圖的覆疊映射 是一類特殊的圖同態,相當於將圖視為拓撲空間 時,拓撲學 上的覆疊映射 ,其定義及性質亦是類似:圖覆疊是滿 同態(即作為陪域 的圖,其每個頂點皆為定義域 某頂點的像),且局部 為雙射,即若限制到每個頂點的鄰域 ,則為雙射。舉例,圖的典範雙重覆疊 ,是將每點
v
{\displaystyle v}
分裂為
v
0
,
v
1
{\displaystyle v_{0},v_{1}}
兩點,並將原圖每條邊
u
v
{\displaystyle uv}
換成交叉的兩條邊
u
0
v
1
{\displaystyle u_{0}v_{1}}
、
u
1
v
0
{\displaystyle u_{1}v_{0}}
。如此,可以定義函數將
v
0
{\displaystyle v_{0}}
和
v
1
{\displaystyle v_{1}}
皆映至
v
{\displaystyle v}
,既是圖同態,也是覆疊映射。
圖同胚 是另一個概念,不一定是同態。粗略而言,同胚要求是單射,但不必將邊映至邊,允許映至路徑 。图子式 的要求更鬆。
核與回縮
K 7 ,七個頂點的完全圖,一種核圖
若兩幅圖
G
{\displaystyle G}
和
H
{\displaystyle H}
有同態
G
→
H
{\displaystyle G\to H}
及
H
→
G
{\displaystyle H\to G}
,則稱兩者同態等價 (homomorphically equivalent )。[ 4] 該些映射不必單,也不必滿。例如,完全二部圖
K
2
,
2
{\displaystyle K_{2,2}}
與
K
3
,
3
{\displaystyle K_{3,3}}
同態等價,因為可將
K
2
,
2
{\displaystyle K_{2,2}}
左部兩個頂點映到
K
3
,
3
{\displaystyle K_{3,3}}
左部同一個頂點,其右部的兩個頂點映到
K
3
,
3
{\displaystyle K_{3,3}}
右部一個頂點,同樣有
K
3
,
3
→
K
2
,
2
{\displaystyle K_{3,3}\to K_{2,2}}
的同態。
收縮映射 (retraction )是自圖
G
{\displaystyle G}
至其子圖
H
{\displaystyle H}
的同態
r
{\displaystyle r}
,且對
H
{\displaystyle H}
中每個頂點
v
{\displaystyle v}
有
r
(
v
)
=
v
{\displaystyle r(v)=v}
。若有此種映射,則
H
{\displaystyle H}
稱為
G
{\displaystyle G}
的收縮核 (retract )。
核圖 (core )沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。每幅圖
G
{\displaystyle G}
皆同態等價於唯一的核圖(不辨 同構之別),稱為
G
{\displaystyle G}
的核 (the core of
G
{\displaystyle G}
)。此結論對無窮圖不一定成立,但對(有限的)有向圖可以照套用同樣的定義,每幅有向圖同態等價於唯一的核圖。圖(或有向圖)的核,必為原圖某個收縮核,以及某個导出子图 。
舉例,完全圖
K
n
{\displaystyle K_{n}}
及奇環(奇數條邊的循环图 )皆屬核圖。若
G
{\displaystyle G}
可染三色 ,且有三角形(即子圖
K
3
{\displaystyle K_{3}}
),則
G
{\displaystyle G}
同態等價於
K
3
{\displaystyle K_{3}}
,原因是
G
{\displaystyle G}
的三染色,下節 將說明相當於同態
G
→
K
3
{\displaystyle G\to K_{3}}
,且另一方面,任意子圖皆有同態嵌入 到
G
{\displaystyle G}
,故有
K
3
→
G
{\displaystyle K_{3}\to G}
。如此,證畢
K
3
{\displaystyle K_{3}}
為所有此種
G
{\displaystyle G}
的核。與之相似,每幅非空二部圖 (有至少一條邊)皆等價於
K
2
{\displaystyle K_{2}}
。
與染色的關聯
對正整數
k
{\displaystyle k}
,圖
G
{\displaystyle G}
的
k
{\displaystyle k}
染色 是將每個頂點塗
k
{\displaystyle k}
色之一,使每條邊的兩端都不同色。此種染色,與自
G
{\displaystyle G}
至完全圖
K
k
{\displaystyle K_{k}}
的同態,兩類物件一一對應,因為
K
k
{\displaystyle K_{k}}
的各頂點對應
k
{\displaystyle k}
種色,且若
c
1
,
c
2
{\displaystyle c_{1},c_{2}}
為顏色,則其於圖
K
k
{\displaystyle K_{k}}
相鄰當且僅當
c
1
≠
c
2
{\displaystyle c_{1}\neq c_{2}}
。於是,某函數是
G
{\displaystyle G}
至
K
k
{\displaystyle K_{k}}
的同態,當且僅當該函數將
G
{\displaystyle G}
中相鄰的頂點映至不同顏色(即
k
{\displaystyle k}
染色的定義)。換言之,
G
{\displaystyle G}
可染
k
{\displaystyle k}
色等價於可染
K
k
{\displaystyle K_{k}}
色。
若有同態
G
→
H
{\displaystyle G\to H}
及
H
→
K
k
{\displaystyle H\to K_{k}}
,則兩者複合可得同態
G
→
K
k
{\displaystyle G\to K_{k}}
。所以,若
H
{\displaystyle H}
可染
k
{\displaystyle k}
色,且有同態
G
→
H
{\displaystyle G\to H}
,則
G
{\displaystyle G}
同樣可染
k
{\displaystyle k}
色。因此,
G
→
H
{\displaystyle G\to H}
推出
χ
(
G
)
≤
χ
(
H
)
{\displaystyle \chi (G)\leq \chi (H)}
,其中
χ
{\displaystyle \chi }
表示圖的色數 [ 註 1] 。
變式
其他同態亦可視作特殊的染色。給定圖
H
{\displaystyle H}
,其頂點視為可用的顏色,每條邊表示某兩色「可兼容」,則
G
{\displaystyle G}
的
H
{\displaystyle H}
染色就是將相鄰頂點染成相容顏色的方案。此框架可容納許多圖染色的概念,將其表述為射向各類圖的同態。舉例如下:
循環染色 可定義為至循環完全圖 [ 註 2] 的同態,從而推廣一般的染色,定義「分數」色數。
分數染色 與b 重染色 可定義成射向克內澤爾圖 的同態。
T 染色 的可用色集為自然數集
N
{\displaystyle \mathbb {N} }
,但另有給定某子集
T
⊆
N
{\displaystyle T\subseteq \mathbb {N} }
,禁止相鄰頂點所染顏色之差屬於
T
{\displaystyle T}
。此種染色對應往某幅無窮圖的同態。
有向染色 除禁止相鄰頂點同色外,還限制不同顏色之間的所有邊皆同向(例如由藍至紅)。此為映向有向圖 的同態。
L(2,1)染色 以數表示顏色,要求距離為1(相鄰)的頂點所染顏色之差至少為2,而距離為2的頂點染色之差至少為1。換言之,此為射向路圖
P
n
{\displaystyle P_{n}}
之補 的同態,且要求局部為單射,即在每個頂點的鄰域上為單射。[ 19]
無長路徑的定向
圖同態與圖定向 也有關。無向圖
G
{\displaystyle G}
的定向是賦予每邊一個方向(二選一),所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例,完全圖
K
k
{\displaystyle K_{k}}
可定向成「遞移循環賽圖 」
T
k
→
{\displaystyle {\overrightarrow {T_{k}}}}
,其頂點為
1
,
2
,
…
,
k
{\displaystyle 1,2,\ldots ,k}
,對所有
i
<
j
{\displaystyle i<j}
有(有向)邊自
i
{\displaystyle i}
指向
j
{\displaystyle j}
。給定
G
{\displaystyle G}
的定向與
H
{\displaystyle H}
的定向之間的同態,忘掉定向即得本來無向圖之間的同態。另一方面,給定無向圖同態
G
→
H
{\displaystyle G\to H}
,
H
{\displaystyle H}
任何定向
H
→
{\displaystyle {\overrightarrow {H}}}
可以拉回 到
G
{\displaystyle G}
的定向
G
→
{\displaystyle {\overrightarrow {G}}}
,使原同態亦是
G
→
→
H
→
{\displaystyle {\overrightarrow {G}}\to {\overrightarrow {H}}}
的有向圖同態。綜上,無向圖
G
{\displaystyle G}
可染
k
{\displaystyle k}
色(即有同態至
K
k
{\displaystyle K_{k}}
),當且僅當
G
{\displaystyle G}
有某定向,具有至
T
k
→
{\displaystyle {\overrightarrow {T_{k}}}}
的同態。
有定理流傳[ 註 3] ,對每個
k
{\displaystyle k}
,有向圖
G
{\displaystyle G}
有同態至
T
k
→
{\displaystyle {\overrightarrow {T_{k}}}}
,當且僅當
k
+
1
{\displaystyle k+1}
個頂點的有向路徑圖
P
k
+
1
→
{\displaystyle {\overrightarrow {P_{k+1}}}}
[ 註 4] 無同態至
G
{\displaystyle G}
。
因此,某圖可
k
{\displaystyle k}
染色,當且僅當其有某定向,不容任何自
P
k
+
1
→
{\displaystyle {\overrightarrow {P_{k+1}}}}
至該定向的同態。此命題可加強成
高洛伊-哈塞-羅伊-維塔韋爾定理 :某圖可
k
{\displaystyle k}
染色,當且僅當該圖有某定向,其中無長為
k
{\displaystyle k}
的有向路徑(即
P
k
+
1
→
{\displaystyle {\overrightarrow {P_{k+1}}}}
作為子圖)。
與前一命題的分別在於,自
P
k
+
1
→
{\displaystyle {\overrightarrow {P_{k+1}}}}
至某圖的同態允許將兩頂點映至同處,但「長為
k
{\displaystyle k}
的有向路徑」不允許重複頂點。
與約束滿足問題的關聯
範例
圖
H
{\displaystyle H}
,表示一週中不相鄰的日子,同構於環
C
7
{\displaystyle C_{7}}
的補圖 ,亦同構於環狀團
K
7
/
2
{\displaystyle K_{7/2}}
某些排程問題可用圖同態建模。設學校已知各學生所選科目,要編排今學期各專題討論班的時間,使同一學生所選的討論班時間不致太近。考慮圖
G
{\displaystyle G}
以各科為頂點,若兩科有共同學生則連邊,而圖
H
{\displaystyle H}
以各課節為頂點,若兩個時段隔足夠遠則連邊。舉例若限制時間表須每週循環,且每個學生所選的討論班須相隔一日,則對應的
H
{\displaystyle H}
是環
C
7
{\displaystyle C_{7}}
的補圖 。如此,
G
→
H
{\displaystyle G\to H}
的圖同態,就是討論班對應到課節的合適方案。欲添加額外條件,如禁止學生同時於週五與週一有討論班,衹需從
H
{\displaystyle H}
刪掉相應的邊。
無線電的頻段分配 問題簡述如下:无线网络 中,有若干發訊機,要為每部機配置一個頻率,供其發訊。為免干擾 ,地理位置較近的發訊機應選用相差較遠的頻率。若將條件中「地理較近」與「頻率較遠」簡化至非黑即白,則合適的分配方案又可視為圖同態
G
→
H
{\displaystyle G\to H}
。圖
G
{\displaystyle G}
的頂點為各發訊機,邊表示兩機地理上接近;圖
H
{\displaystyle H}
以各頻段為頂點,邊則表示兩頻段相隔夠遠。雖然此模型甚為簡化,但是尚有保留一點彈性:若有兩機相隔較遠,但仍因地形導致可能干擾,則在
G
{\displaystyle G}
中加邊即可。反之,若有兩機永不在同一時段發訊,則不論其地理位置是否靠近,皆可從
G
{\displaystyle G}
中刪去該邊。同樣,或許有某些頻率相差頗遠,但是互為谐波 ,導致干擾,則將該邊自
H
{\displaystyle H}
移除即可
前述模型經簡化,若要實際應用,許多問題仍待解決。約束滿足問題 是圖同態問題的推廣,能表達更多種條件(例如個體偏好,或重複分配次數有上限),從而建立更實際的數學模型。
抽象觀點
數理邏輯或泛代數 中,圖與有向圖屬關係結構 的特例,即集合配備若干關係 。有向圖就是基集(頂點集)之上有獨一個二元關係(鄰接關係)。[ 26] 如是觀之,圖作為關係結構的同態 ,按抽象代數的同態定義,等同於本文的圖同態。一般而言,欲尋找自某關係結構至另一關係結構的同態,屬於約束滿足問題 (constraint satisfaction problem, CSP )。圖的特例可作為第一步,幫助理解更複雜的CSP 。許多尋找圖同構的算法,包括回溯 、約束傳播 、局部搜索 ,通用於各種CSP 。
給定圖
G
{\displaystyle G}
、
H
{\displaystyle H}
,問是否有同態
G
→
H
{\displaystyle G\to H}
,相當於僅得一類約束的CSP 實例:CSP 的「變量」是
G
{\displaystyle G}
的頂點,每個變量的「域」(可取值的範圍)是
H
{\displaystyle H}
的頂點集。「賦值」是一個函數,將逐個變量映至域的元素,即函數
f
:
V
(
G
)
→
V
(
H
)
{\displaystyle f:V(G)\to V(H)}
。
G
{\displaystyle G}
的每條邊(或有向邊)
(
u
,
v
)
{\displaystyle (u,v)}
對應一個「約束」
(
(
u
,
v
)
,
E
(
H
)
)
{\displaystyle ((u,v),E(H))}
,限制賦值函數將邊
(
u
,
v
)
{\displaystyle (u,v)}
映至關係
E
(
H
)
{\displaystyle E(H)}
中,即映至
H
{\displaystyle H}
的某邊。CSP 的「解」是滿足全體約束的賦值,故前述CSP 的解正是自
G
{\displaystyle G}
至
H
{\displaystyle H}
的同態。
同態的結構
同態的複合仍是同態,故可知圖的
→
{\displaystyle \to }
關係具遞移性 ,又顯然自反 ,所以其為圖之間的預序 。同態等價意義下,記
G
{\displaystyle G}
所屬等价类 為
[
G
]
{\displaystyle [G]}
,每個等價類有唯一的核圖為其代表。關係
→
{\displaystyle \to }
定義該些等價類之間的偏序 ,即同態等價類構成一個偏序集 。
以
G
<
H
{\displaystyle G<H}
表示
G
{\displaystyle G}
有同態至
H
{\displaystyle H}
,但反之則不然。如此定義的序
<
{\displaystyle <}
稠密 ,即對任意(無向)圖
G
,
H
{\displaystyle G,H}
,若
G
<
H
{\displaystyle G<H}
,則存在第三幅圖
K
{\displaystyle K}
使
G
<
K
<
H
{\displaystyle G<K<H}
,除非是平凡反例
G
=
K
0
{\displaystyle G=K_{0}}
或
G
=
K
1
{\displaystyle G=K_{1}}
。[ 30] 例如,任意兩幅整數階完全圖 (除
K
0
,
K
1
,
K
2
{\displaystyle K_{0},K_{1},K_{2}}
外)之間,必有無窮多幅環狀完全圖 ,相當於整階數之間的有理數階數。
同態等價類的偏序集是分配格 ,併
[
G
]
∨
[
H
]
{\displaystyle [G]\lor [H]}
是互斥併
[
G
⊔
H
]
{\displaystyle [G\sqcup H]}
,而交
[
G
]
∧
[
H
]
{\displaystyle [G]\land [H]}
是圖張量積
[
G
×
H
]
{\displaystyle [G\times H]}
,其定義不取決於等價類中所選的代表
G
,
H
{\displaystyle G,H}
。[ 32] 此格中,併不可約元 [ 註 5] 正好是連通圖 ,證明方式是留意同態衹會將連通圖映到目標的一個連通分支 中。[ 33] 交不可約元 [ 註 5] 正好是積性圖 (multiplicative graphs ),此種圖
K
{\displaystyle K}
的特性是,若乘積
G
×
H
{\displaystyle G\times H}
有同態至
H
{\displaystyle H}
,則
G
{\displaystyle G}
或
H
{\displaystyle H}
兩者之一有同態至
H
{\displaystyle H}
。如何識別積性圖是赫德米猜想 [ 35] 的關鍵。[ 36] [ 37]
圖與同態還組成範疇 :圖是物件,而同態是態射。範疇的始物件 是空圖
K
0
{\displaystyle K_{0}}
,終物件 有一個頂點和一個自环 。圖張量積 是範疇論積 ,指數圖 [ 註 6] 是該範疇的指數物件 。換言之,自
G
×
H
→
K
{\displaystyle G\times H\to K}
的同態與
H
→
K
G
{\displaystyle H\to K^{G}}
的同態自然地 一一對應。[ 37] 由於對任意圖
G
,
H
{\displaystyle G,H}
,張量積
G
×
H
{\displaystyle G\times H}
與冪
H
G
{\displaystyle H^{G}}
總有定義,圖範疇是笛卡儿闭范畴 。同理,同態等價類組成的格實際上是海廷代数 :按海廷代數的語言,前述的積稱為交運算
∧
{\displaystyle \land }
,而前述的指數運算稱為蘊涵
⇒
{\displaystyle \Rightarrow }
。[ 37]
對於有向圖,適用同樣的定義。同樣有
→
{\displaystyle \to }
是有向圖同態等價類之間的偏序 ,其與無向圖等價類的偏序
→
{\displaystyle \to }
有別,但後者是前者的子序,因為無向圖亦可視為有向圖,衹是其中每條有向邊
(
u
,
v
)
{\displaystyle (u,v)}
皆與其反向
(
v
,
u
)
{\displaystyle (v,u)}
成對出現。換言之,無向圖同態的定義,與雙向有向圖的同態並無區別。有向圖的
→
{\displaystyle \to }
序仍是分配格和海延代數,交與併的定義亦同上,但分別在於,該序並不稠密。亦有以有向圖為物件、同態為態射的範疇,照樣笛卡儿闭 。
不可比圖
格勒奇圖 ,與
K
3
{\displaystyle K_{3}}
不可比
同態預序下,許多圖不可比較。兩幅不可比圖(incomparable graphs )之間,並無自任意一幅至另一幅的同態。欲構造此種圖,可考慮圖的奇圍長 ,即最短的奇環長度。奇圍長可等價地說成最小的奇數
g
{\displaystyle g}
,使
g
{\displaystyle g}
個頂點的循环图
C
g
{\displaystyle C_{g}}
有同態至
G
{\displaystyle G}
。由此定義,若
G
→
H
{\displaystyle G\to H}
,則
G
{\displaystyle G}
的奇圍長大於或等於
H
{\displaystyle H}
的奇圍長。
另一方面,前節 已證若
G
→
H
{\displaystyle G\to H}
,則
G
{\displaystyle G}
的色數小於或等於
H
{\displaystyle H}
的色數。所以,若
G
{\displaystyle G}
的奇圍長及色數皆嚴格大於
H
{\displaystyle H}
,則
G
{\displaystyle G}
和
H
{\displaystyle H}
不可比較。
舉例,格勒奇圖 色數為
4
{\displaystyle 4}
,且無三角形(圍長
4
{\displaystyle 4}
,奇圍長
5
{\displaystyle 5}
)[ 43] ,所以與三角形
K
3
{\displaystyle K_{3}}
不可比。
有幾類圖的奇圍長和色數可取任意大,如克內澤爾圖 與廣義梅切爾斯基圖 [ 45] 。如此一類圖,若使其兩參數同時遞增,排成一列,則有無窮多幅不可比圖(同態預序下的反鏈 )。
同態預序稠密 等其他性質,亦可利用此類圖證明。此外,可構造同時具大色數和大圍長(不僅是奇圍長)的圖,但較複雜,見圍長 (圖論) § 圍長與圖染色 。
有向圖之中,更易找到不可比圖。例如,考慮有向環
C
n
→
{\displaystyle {\overrightarrow {C_{n}}}}
,頂點為
1
,
2
,
…
,
n
{\displaystyle 1,2,\ldots ,n}
,有向邊自
i
{\displaystyle i}
至
i
+
1
{\displaystyle i+1}
(對
i
=
1
,
2
,
…
,
n
−
1
{\displaystyle i=1,2,\ldots ,n-1}
各一),及自
n
{\displaystyle n}
至
1
{\displaystyle 1}
。對於
n
,
k
≥
3
{\displaystyle n,k\geq 3}
,
C
n
→
{\displaystyle {\overrightarrow {C_{n}}}}
至
C
k
→
{\displaystyle {\overrightarrow {C_{k}}}}
有同態當且僅當
n
{\displaystyle n}
為
k
{\displaystyle k}
的倍數。所以,當
p
{\displaystyle p}
取質數值時,
C
p
→
{\displaystyle {\overrightarrow {C_{p}}}}
兩兩不可比。
計算複雜度
圖同態問題是給定一對圖
(
G
,
H
)
{\displaystyle (G,H)}
,求自
G
{\displaystyle G}
至
H
{\displaystyle H}
的圖同態。對應的決定性問題 問是否存在此種解。一般情況下,即詢問的實例
(
G
,
H
)
{\displaystyle (G,H)}
不受額外限制的情況下,此決定性問題為NP完全 。若限制詢問的範圍,衹限從某類圖中選出
G
{\displaystyle G}
或
H
{\displaystyle H}
,則可得多種不同的問題,其中有些較易求解。限制左邊
G
{\displaystyle G}
和限制右邊
H
{\displaystyle H}
相比,適用的方法相去甚遠,但兩者似乎有一共同特點:難易情況之間似乎有明確的分界,此分界或者已獲證,或有論文猜想如此。
至給定圖的同態
圖同態問題若固定右邊的圖
H
{\displaystyle H}
不變,則稱為染
H
{\displaystyle H}
色問題。
H
{\displaystyle H}
為完全圖
K
k
{\displaystyle K_{k}}
時,化成染k 色問題 ,在
k
=
0
,
1
,
2
{\displaystyle k=0,1,2}
時,可於多項式時間 內求解,但其餘情況則是NP完全 。
k
=
2
{\displaystyle k=2}
的情況相當於問圖
G
{\displaystyle G}
可否染
K
2
{\displaystyle K_{2}}
色,即是否二部圖 ,此問題可在線性時間 內求解。更一般地,衹要
H
{\displaystyle H}
是二部圖就有同一結論:可染
H
{\displaystyle H}
色等價於可染
K
2
{\displaystyle K_{2}}
色,即可染二色,故此種情況同樣易判斷。可染
K
0
{\displaystyle K_{0}}
色和可染
K
1
{\displaystyle K_{1}}
色分別等價於無頂點和無邊,亦易判斷。帕沃爾·黑爾 和雅羅斯拉夫·內舍特日爾 證明,對無向圖而言,無其他情況可馴順:
(黑爾-內舍特日爾定理,1990年)若
H
{\displaystyle H}
為二部圖,則染
H
{\displaystyle H}
色問題屬於P ,但其餘情況則為NP完全。[ 53]
上述定理又稱為無向圖同態的「對分定理」(dichotomy theorem ),因為將染
H
{\displaystyle H}
色問題分成NP完全與P兩類,而無居中 情況。有向圖情況較複雜,此時問題等價於刻畫看似更一般的約束滿足問題的複雜度 :有向圖的染
H
{\displaystyle H}
色問題,與允許各種約束條件的CSP 相比,同樣多姿多彩,而不失一般性。[ 56] 嚴格而言,定義(有限)約束語言(constraint language ,或稱模板template )
Γ
{\displaystyle \Gamma }
為一個有限的取值域,其上配備有限多種關係 ,然後以
C
S
P
(
Γ
)
{\displaystyle {\mathsf {CSP}}(\Gamma )}
表示約束衹能選自
Γ
{\displaystyle \Gamma }
的一類約束滿足問題,則有以下定理:
(费德、瓦迪 ,1998年)對任意約束語言
Γ
{\displaystyle \Gamma }
,必有某幅有向圖
H
{\displaystyle H}
,使
C
S
P
(
Γ
)
{\displaystyle {\mathsf {CSP}}(\Gamma )}
在多项式时间归约 意義下等價於染
H
{\displaystyle H}
色問題。[ 56]
直觀理解,定理意味着任何算法技巧或複雜度結論,若適用於一般有向圖
H
{\displaystyle H}
的染
H
{\displaystyle H}
色問題,則可套用至一般CSP 。考慮將黑爾-內舍特日爾定理擴展至有向圖。由上述定理,該推廣等價於有關CSP 對分的费德-瓦迪猜想(又稱CSP 猜想、對分猜想),即斷言對任意約束語言
Γ
{\displaystyle \Gamma }
,
C
S
P
(
Γ
)
{\displaystyle {\mathsf {CSP}}(\Gamma )}
或屬NP完全,或屬P。此猜想於2017年由德米特里·祖克(Dmitry Zhuk )與安德烈·布拉托夫(Andrei Bulatov )分別獨立證出,故有以下推論:
(布拉托夫2017年;祖克2017年)給定
H
{\displaystyle H}
時,有向圖的染
H
{\displaystyle H}
色問題或屬P,或屬NP完全。
自給定族的同態
若左輸入
G
{\displaystyle G}
為給定,則圖同態問題有暴力解法 ,即窮舉
G
{\displaystyle G}
的各個頂點在
H
{\displaystyle H}
中的像,複雜度僅為
O
(
|
V
(
H
)
|
|
V
(
G
)
|
)
{\displaystyle {\mathcal {O}}\left(|V(H)|^{|V(G)|}\right)}
,已是輸入
H
{\displaystyle H}
的多項式函數。[ 57] 換言之,限制
G
{\displaystyle G}
的大小時,問題顯然屬P,但仍可改為研究另一課題:除大小之外,是否其他限制可施加於
G
{\displaystyle G}
,使圖同態問題可於多項式時間內求解?
研究表明,關鍵性質是樹闊 ,此參數衡量一幅圖有多似一棵樹。若
G
{\displaystyle G}
的樹闊至多為
k
{\displaystyle k}
,而
H
{\displaystyle H}
為任意圖,則利用標準的动态规划 方法,可於
|
V
(
H
)
|
O
(
k
)
{\displaystyle |V(H)|^{{\mathcal {O}}(k)}}
時間內求解圖同態問題。實際甚至衹需假設
G
{\displaystyle G}
的核的樹闊不逾
k
{\displaystyle k}
,而無需知道其核為何。[ 58] [ 59]
該
|
V
(
H
)
|
O
(
k
)
{\displaystyle |V(H)|^{{\mathcal {O}}(k)}}
算法中,複雜度的指數可能無法再壓低太多:若指數時間假設 [ 註 7] (ETH )為真,則不存在時間複雜度為
|
V
(
H
)
|
o
(
t
w
(
G
)
/
log
t
w
(
G
)
)
{\displaystyle |V(H)|^{o(\mathrm {tw} (G)/\log \mathrm {tw} (G))}}
的算法。即使限制
G
{\displaystyle G}
衹能取值為某一族圖,衹要該族圖的樹闊無上界,則仍有同樣結論。[ 60] 同樣假設下,幾乎沒有其他性質使問題可於多項式時間內求解,具體含義如下:
(格罗厄 )假定ETH ,並給定由圖組成的可計算 族
G
{\displaystyle {\mathcal {G}}}
。考慮輸入為
(
G
,
H
)
{\displaystyle (G,H)}
,且
G
∈
G
{\displaystyle G\in {\mathcal {G}}}
的圖同態問題。此問題屬P當且僅當
G
{\displaystyle {\mathcal {G}}}
中各圖之核的樹闊有界。[ 59]
或考慮有所取捨,允許複雜度高度依賴
G
{\displaystyle G}
,換取複雜度與
H
{\displaystyle H}
的關係僅為固定的多項式。與前段類似,若
G
{\displaystyle G}
的取值範圍中,核的樹闊有界,則此目標可以實現,但若
G
{\displaystyle G}
的取值範圍不滿足該條件,則無法達成。[ 59] 利用帶參數複雜度 術語,上述成果可覆述為:
G
{\displaystyle {\mathcal {G}}}
中的同態問題,以
G
{\displaystyle G}
的邊數為參數,呈現對分現象。若
G
{\displaystyle {\mathcal {G}}}
中各圖之核的樹闊有上界,則該問題為固定參數可馴順 ,否則為W[1] 完全。
同一命題對其他關係結構亦成立。換言之,其適用於一般的約束滿足問題,不過需要限制各項約束涉及的變量數有上界,即關係的元數 有上界(以圖為例,僅得元數為2的關係)。此時,關鍵參數為原始約束圖 [ 註 8] 的樹闊。[ 60]
參見
註
參考資料
^ 4.0 4.1 引論見諸:Cameron (2006) ; Hahn & Tardif (1997) ; Hell & Nešetřil (2004) . 由短至長排。
^ Fiala, J.; Kratochvíl, J. , Partial covers of graphs [圖之部分覆蓋], Discussiones Mathematicae Graph Theory, 2002, 22 (1): 89–99, S2CID 17507393 , doi:10.7151/dmgt.1159 (英语)
^ Hell & Nešetřil 2004 ,第28頁,該書稱關係結構(relational structures )為「關係系統」(relational systems )。
^ Welzl, E., Color-families are dense [染色族稠密], Theoretical Computer Science , 1982, 17 : 29–41, doi:10.1016/0304-3975(82)90129-3 (英语)
^ Hell & Nešetřil 2004 ,Proposition 3.2,分配律載於Proposition 2.4;又見Hahn & Tardif 1997 ,Theorem 2.37.
^ Kwuida, Léonard; Lehtonen, Erkko, On the Homomorphism Order of Labeled Posets [論標號偏序集之同態序], Order , 2011, 28 (2): 251–265, S2CID 14920600 , arXiv:0911.0200 , doi:10.1007/s11083-010-9169-x (英语)
^ 譯名見 陳宏賓. 捉住黑暗中的微光,年輕數學家希多夫擊破[赫德米猜想] . UniMath. 2020-02-22 [2021-12-21 ] . (原始内容 存档于2021-12-21).
^ Tardif, C., Hedetniemi's conjecture, 40 years later [赫德米猜想四十年] (PDF) , Graph Theory Notes of New York, 2008, 54 : 46–57 [2021-12-21 ] , MR 2445666 , (原始内容 (PDF) 存档于2021-07-12) (英语) .
^ 37.0 37.1 37.2 Dwight, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi's conjecture [以範疇論研究赫德米猜想所得的格], Discrete Mathematics , 1996, 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W (英语)
^ Weisstein, Eric W. (编). Grötzsch Graph . at MathWorld --A Wolfram Web Resource. Wolfram Research, Inc. (英语) .
^ Gyárfás, A.; Jensen, T.; Stiebitz, M., On Graphs With Strongly Independent Color-Classes [論色類強獨立之圖], Journal of Graph Theory , 2004, 46 (1): 1–14, doi:10.1002/jgt.10165
^ Hell, Pavol; Nešetřil, Jaroslav. On the complexity of H-coloring [論染H色之複雜度]. Journal of Combinatorial Theory, Series B . 1990, 48 (1): 92–110. doi:10.1016/0095-8956(90)90132-J (英语) .
^ 56.0 56.1 Feder, Tomás; Vardi, Moshe Y. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory [單調單子SNP與約束滿足之計算結構:藉Datalog與群論研究] . SIAM Journal on Computing . 1998, 28 (1): 57–104 [2022-02-06 ] . doi:10.1137/S0097539794266766 . (原始内容 存档于2022-02-06) (英语) .
^ Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A. Tight bounds for graph homomorphism and subgraph isomorphism [圖同態與子圖同構之緊限界]. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM : 1643–1649. 2016. Bibcode:2015arXiv150703738F . ISBN 978-1-611974-33-1 . arXiv:1507.03738 (英语) .
^ Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics [約束滿足、有界樹闊、有限變數邏輯]. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002): 310–326. 2002. doi:10.1007/3-540-46135-3_21 (英语) .
^ 59.0 59.1 59.2 Grohe, Martin , The complexity of homomorphism and constraint satisfaction problems seen from the other side [同態與約束滿足之複雜度,自另一方面觀之], Journal of the ACM , 2007, 54 (1): 1–es, S2CID 11797906 , doi:10.1145/1206035.1206036 (英语)
^ 60.0 60.1 Marx, Dániel, Can You Beat Treewidth? [可以勝過樹闊乎?], Theory of Computing , 2010, 6 : 85–112, doi:10.4086/toc.2010.v006a005 (英语)
一般書目、解說
約束滿足、泛代數
格論、範疇論