2.1.4 圖的同構(gòu)

由圖的定義可知，圖本質(zhì)上是用來刻畫頂點(diǎn)集中任意一對頂點(diǎn)是否相鄰的。圖沒有唯一正確的畫法，頂點(diǎn)的位置及邊的長度、曲直和形狀通常沒有重要的意義。正因如此，有些表面上似乎完全不同的圖，本質(zhì)上是相同的。這種現(xiàn)象被稱為同構(gòu)，嚴(yán)格定義如下。

設(shè)、是兩個(gè)簡單圖，與稱為同構(gòu)，記作。如果存在一個(gè)從到的雙射，使得，與在中相鄰當(dāng)且僅當(dāng)與在中相鄰，則把稱為與之間的一個(gè)同構(gòu)映射。圖2.13所示的兩個(gè)圖與，，，定義（）。易驗(yàn)證：是與之間的一個(gè)同構(gòu)映射，因此與是同構(gòu)的。

圖2.13　一對典型的同構(gòu)圖

1．同構(gòu)測試算法

判斷圖與是否同構(gòu)的問題就是圖同構(gòu)測試問題。此問題是P問題還是NP完全問題尚無定論。

下面給出3個(gè)解決圖同構(gòu)測試問題的直觀方法。

（1）頂點(diǎn)數(shù)與邊數(shù)判別法。

定理2.2　若，則，，其逆 不真。　　　　█

此方法只能針對不同構(gòu)的兩個(gè)圖進(jìn)行判斷：若兩圖的頂點(diǎn)數(shù)不等，則它們一定不同構(gòu)；若兩圖的頂點(diǎn)數(shù)相等，但邊數(shù)不等，則也不同構(gòu)。這種判別方法非常粗糙，因?yàn)闈M足頂點(diǎn)數(shù)與邊數(shù)相等但不同構(gòu)的圖太多。例如，不同構(gòu)的(4,3)-圖共有3個(gè)，如圖2.14所示。

圖2.14　3個(gè)不同構(gòu)的(4,3)-圖

基于此，下面給出圖的度序列判別法。

（2）度序列判別法。

定理2.3　若，則，但其逆不真。　　　　█

此方法也只能針對不同構(gòu)的兩個(gè)圖進(jìn)行判斷：若兩圖的度序列不等，則它們不同構(gòu)。這種判別方法也比較粗糙，因?yàn)橥粋€(gè)圖序列可對應(yīng)多個(gè)不同構(gòu)的圖。例如，6個(gè)頂點(diǎn)且度序列為(2,2,2,2,2,2)的圖有兩個(gè)：一個(gè)是，另一個(gè)是兩個(gè)不相交的三角形。

（3）補(bǔ)圖判別法。

定理2.4　與是同構(gòu)的當(dāng)且僅當(dāng)它們的補(bǔ)與是同構(gòu)的。　　　　█

一般情況下，判別兩個(gè)圖是否同構(gòu)并不容易，已有很多用于求解該問題的算法被相繼提出。截至本書成稿之日，已知最好的判別圖同構(gòu)的算法是由Babai于2016年提出的擬多項(xiàng)式時(shí)間算法[5]。關(guān)于圖同構(gòu)算法更詳細(xì)的介紹，可參見文獻(xiàn)[6]。

2．圖同構(gòu)的應(yīng)用

圖同構(gòu)有豐富的應(yīng)用場景。判別兩個(gè)系統(tǒng)是否同構(gòu)在系統(tǒng)建模中具有非常實(shí)用的價(jià)值。此外，在利用計(jì)算機(jī)構(gòu)造圖時(shí)，必須排除大量的同構(gòu)圖。例如，澳大利亞圖論專家麥凱（McKay）在證明拉姆齊數(shù)（Ramsey Number）[7]和[8]時(shí)，成功利用了他提出的判別子圖同構(gòu)方法的優(yōu)勢。