動機
一張圖並不由畫中線條的位置或長度決定,重要的是哪些頂點相連。要比較兩幅圖,我們需要「重新標號」的精確意思;要進行計算,還須決定如何儲存相鄰數據。表示法記錄某一套具體標號,而同構則把只在名稱上不同的圖視為相同。
定義與儲存
定義 8.1.1
(鄰接矩陣與鄰接表)
本節中 是有限簡單無向圖:每條邊是 的二元素子集,因此不容許自環或重邊。記 、,並選定頂點次序 。鄰接矩陣 定義為:若 ,則 ,否則 。它是對稱矩陣,對角線為零。反過來,每個對稱、對角線為零的零一矩陣,都恰好決定其有序頂點集上的一張簡單圖。
鄰接表為每個頂點記錄其所有鄰點。每條邊在兩張表中各出現一次;孤立頂點的表是空表,但頂點集仍須記錄,以免遺失孤立頂點。
矩陣儲存 個項目,判斷一對頂點是否相鄰只需一次索引查詢。鄰接表佔 個項目,連同存取表頭,完整掃描 的鄰點需 次操作;但要判斷任意一對頂點是否相鄰,可能須掃描整張表。這些界假設頂點已編號,而陣列存取為常數時間;把表排序或使用雜湊,都會改變這種取捨。
編碼記錄了甚麼,沒有記錄甚麼
設一個數據檔只給出邊對 與 。它沒有說明頂點集是 ,還是另有孤立頂點 。兩種理解給出不同構的圖。完整的編碼必須同時給出頂點和邊。若頂點已編號為 ,列出這些編號或給出整數 便補足了所缺的數據。在聲稱是簡單圖的邊表中重複一條邊,並不會產生另一條邊;程式要麼拒絕重複項,要麼明確把輸入當作集合處理。下文的結果都假設給出的是簡單圖的有效編碼。
矩陣令這個區別特別明顯。孤立頂點會增加一整行零和一整列零。第 行中 的個數等於 ,而全部項目之和為 :每條邊在兩個對稱位置各產生一個項目。因此只檢查對角線以上的位置便可重建邊集。但這並不表示矩陣本身與頂點次序無關。換一個次序,會改變哪一行描述哪個頂點,儘管底層的圖沒有改變。
例題 8.1.2
(孤立頂點也是圖的一部分)
設 的頂點集為 ,邊為 。按此次序,其矩陣為
各行之和為 ,總和為 。第四行表明頂點 是孤立頂點。若頂點集改為 ,同樣兩對邊便描述一條三頂點路徑,其矩陣是左上角的 子塊。兩圖不同構,因為大小不同的頂點集之間不存在雙射。
子圖:選擇頂點與選擇邊
比較兩張完整的圖之前,先分清楚「取出圖的一部分」可以有甚麼不同意思。
定義 8.1.3
(子圖、生成子圖與誘導子圖)
的一個子圖是圖 ,其中 ,而且
這裏 表示 的所有二元素子集所組成的集合。因此,每條保留下來的邊,其兩端都必須在 內;但即使兩個端點都保留,仍可以刪去它們之間的邊。如果 ,這個子圖稱為生成子圖:它保留全部原頂點,包括刪邊後變成孤立頂點的那些頂點。由 決定的誘導子圖記作 ,它保留原圖中兩端都在 內的每一條邊:
選定 之後,誘導子圖便唯一確定;一般子圖在同一頂點集上還可以少保留一些邊。刪去頂點 ,要連同所有與它關聯的邊一起刪去,得到 。刪去一條邊則只移除該邊,並不刪除任何頂點。這兩種操作不能混淆,即使畫圖時經常把刪邊後留下的孤立頂點漏畫了。
從鄰接矩陣看,形成 就是同時保留由 索引的行與列,並保留它們原來的相對次序。所得矩陣稱為主子矩陣。若要形成頂點集為 的一般子圖,還可以把某些對稱位置上的一對一改成零。只刪一行而不刪相應的列,並不是從圖中刪去一個頂點。
例題 8.1.4
(一條路徑可以是子圖,卻不是誘導子圖)
設 的頂點為 ,邊為 。對 , 是三角形,因為邊 都必須保留。頂點集同為 、但只含邊 的圖是子圖,卻不是由 誘導的子圖。如果保留全部四個原頂點、邊仍只取 ,得到的則是生成子圖;頂點 仍然存在,而且孤立。最後,從 刪去頂點 ,留下的是頂點 及唯一的邊 ,並不是含邊 的路徑。
這個區別會影響性質能否傳給子圖。無圈圖的每個子圖仍然無圈,因為子圖中的圈必然也是原圖中的圈。二部圖的每個子圖仍然是二部圖:將原來兩個獨立頂點集分別與保留的頂點集取交;刪邊不會在同一側內引入新邊。但連通性不同。在路徑 中, 誘導的子圖只有兩個孤立頂點。原來連接保留頂點的路徑,可能必須經過一個已刪去的頂點。
最短路徑的頂點之間沒有可用的弦
定義 8.1.5
(誘導路徑與弦)
路徑 的頂點互異,並含邊 。如果這些邊恰好是 的全部邊,便稱它為誘導路徑。額外出現的邊 ,其中 ,稱為這條路徑的弦。
一串頂點構成路徑,並不代表周圍的圖中沒有這些弦;上面三角形中的兩邊路徑就是例子。
定理 8.1.6
(無權圖的最短路徑必為誘導路徑)
設有限簡單圖中的 之間存在路徑。任何一條由 到 、邊數最少的路徑都是誘導路徑。反過來不一定成立。
證明
(弦會縮短路徑)
設 是最短路徑。如果有弦 ,其中 ,便用這一條邊取代路徑段 。新序列仍然是路徑:其頂點只是原來互異頂點的一個子序列。新路徑的長度是 ,與最短性矛盾。因此弦不存在。長度為零或一時,本來就沒有可能的弦,結論同樣成立。
證明透視
最短路徑的論證改變了甚麼
兩個端點始終固定,優化目標只是邊數。一條弦至少省去一條邊,而且不改變端點。但也可能有一條更短路線經過原路徑以外的頂點;誘導路徑的定義完全不檢查那些頂點。因此證明只得到一個方向,不能反推。加權最短路徑亦不能直接套用同一論證:一條弦的權重可能比它取代的整段路徑還大。
例題 8.1.7
(誘導路徑不一定最短)
考慮五圈,邊為 。路徑 是誘導路徑,因為這四個頂點之間只有 三條邊。但它不是由 到 的最短路徑: 只有兩條邊,原路徑卻有三條。更短路線使用了頂點 ;判斷原路徑是否誘導時,並沒有檢查這個頂點。相比之下,三角形中的兩邊路線連誘導性也不滿足,因為它的兩個端點本來就相鄰。
同構保留邊與非邊
定義 8.1.8
(同構與自同構)
由 到 的同構是雙射 ,使任何兩個不同頂點 滿足
兩個方向都重要:邊和非邊都要保留。由一張圖到自身的同構稱為自同構。空圖透過空雙射與自身同構,但不與有頂點的圖同構。
以矩陣等式描述重新標號
定理 8.1.9
(排列矩陣描述同構)
設 與 的有序頂點集分別為 和 ,鄰接矩陣分別為 和 。兩圖同構,當且僅當存在排列矩陣 使 。
證明
(計算 的項目)
為看清約定,令 的第 列為標準基向量 ,則 。因此上述等式正是說映射 同時保留相鄰與不相鄰。反過來,由 到 的任何同構都給出這樣一個排列。同構的逆仍是同構,所以所述等價成立。特別是,改變一張圖的頂點次序時,矩陣要按同一排列同時改變行和列,而不是把行與列各自任意重排。
定義 8.1.10
(同構不變量)
被每個同構保留的性質稱為不變量。不變量取值不同可證明不同構;取值相同只表示這項檢驗未能區分兩圖。要證明同構,須給出雙射並檢驗相鄰關係的等價,而不能只列出相同的不變量。
例如,同構把每個頂點的鄰點雙射到其像的鄰點。因此度數、排序後的度數序列、頂點數、邊數,以及連通分支的數目和大小都得以保留。路徑映成路徑,這說明了有關分支的結論;逆映射則保證分支一一對應。
反例模式
度數序列並不決定一張圖
六圈 與不交併 都有六個頂點、六條邊,度數序列都是 。然而 連通,兩個三角形卻不連通,所以不存在同構。畫圖可以提示這個區別,但連通性給出與畫法無關的證明。
檢驗給出的對應
同構之所以是有用的證書,是因為讀者可以直接檢驗它。先檢查給出的像都屬於目標頂點集,而且每個目標頂點恰好出現一次。然後檢查源圖中每一對不同頂點:比較它的相鄰位與其像的相鄰位。若全部一致,定義便成立;若有一對不一致,這一對就是映射失敗的簡短而明確的理由。有兩個鄰接矩陣時,在檢查雙射之後,這樣檢驗給定映射需要 次頂點對比較;除輸入外,儲存映射及其逆需要 空間。這是驗證的成本,而不是尋找合適映射的界。逐一檢驗全部 個雙射是一個有限的判定方法,但單憑這一點並不能得到一般的高效算法。
若兩圖都以有效的邊表給出,還有另一種檢驗。驗證雙射性,映射源圖的每條邊,再把所得集合與目標邊集比較。兩者相等就保證邊與非邊都得以保留:不在像中的目標邊,或在目標中不存在的映射頂點對,都表明失敗。在雙射下,不同的源邊有不同的像。若已知源圖與目標圖的邊數相同,只須檢查每條映射後的源邊都是目標邊,因為大小相同的有限邊集之間的單射必為滿射。沒有邊數相等這個條件,這條捷徑便不成立。所需時間視乎如何實現對目標邊集的成員查詢;不能僅因有鄰接表便保證常數時間查詢。
例題 8.1.11
(保留邊的雙射仍可能失敗)
設 的頂點為 、邊為 , 的頂點為 、邊為 。雙射 、、 把 的每條邊都映成 的邊,卻把非邊 映成了邊 ,所以它不是同構。事實上兩圖分別有兩條和三條邊,因此任何其他雙射也不可能是同構。這個例子說明了定義為何使用等價,而不只是正向蘊含。
畫法不能挽救一個失敗的證書。交叉點若沒有列為頂點,便不會自動成為頂點;反過來,把兩個頂點畫得很近也不會令它們相鄰。每個聲稱的對應都必須對照給定的頂點集和邊集來檢驗,而不是對照外觀上的相似。一張畫得很複雜的連通圖,與同一張圖不帶交叉的畫法,在恆等映射下仍有完全相同的相鄰數據。
補圖:恰好記錄缺少的邊
定義 8.1.12
(補圖)
簡單圖 的補圖 保留同一頂點集 ,邊集則是 。對每一對不同頂點, 與 中恰有一個包含連接它們的邊。補圖不會引入自環。
因此,若固定頂點次序後 的鄰接矩陣是 ,便有
其中 是每個項目均為一的 矩陣, 是單位矩陣。非對角位置上的零與一互換;對角位置則是 。若只寫成 ,便會錯誤地在每個頂點加入自環。此外,取兩次補圖會回到 ,而 ,因為 的 個可能鄰點被兩張圖分配完畢。
一個雙射是由 到 的同構,當且僅當同一個雙射也是由 到 的同構。理由是:兩個不同頂點在補圖中相鄰,恰好表示它們在原圖中不相鄰;對原來相鄰關係的等價式兩邊同時取否定,便得到補圖的等價式。再取一次補圖,可得反方向。同樣,取誘導子圖與取補圖可以交換次序:
兩邊的頂點集都是 ; 中一對不同頂點在任何一邊構成邊,當且僅當它們在 中不相鄰。注意左邊的補圖是在頂點集 上取的,並不是在較大的 上取的。
定理 8.1.13
(不連通圖的補圖必連通)
設有限簡單圖 有 個頂點,而且不連通。那麼 中任何兩個不同頂點之間,都有長度至多為二的路徑。特別地, 連通。
證明
(不同分支或同一分支)
若 屬於 的不同連通分支,它們在 中不相鄰,所以在 中直接相鄰。若它們屬於同一分支,因 不連通,可以在另一分支選取頂點 。邊 在 中都不存在,因此 是 中的路徑;三個頂點互異。這兩種情況包括了所有不同頂點對。
所以,當 時, 與 至少有一個連通,但不一定恰好一個連通。定理的前提是原圖不連通;它的等價逆否命題是「補圖不連通,則原圖連通」。
反例模式
原圖與補圖可以同時連通
四頂點路徑的邊為 ,補圖的邊為 。這些邊構成路徑 ,所以兩圖均連通。映射 、、、 甚至給出了原圖到補圖的同構:原來三條邊恰好映為 。但不能由此認為取補圖總會保留連通性。至少有兩個頂點的完全圖是連通的,其補圖卻完全沒有邊。
關於子圖與補圖的練習
快速檢查
(圖的頂點為 ,邊為 。判斷路徑 是否誘導、是否是兩端之間的最短路徑,並與 比較。)
解答 · 答案
在 上只有邊 ,所以第一條路徑是誘導的。由於 不是邊,不存在一邊路線;給定的兩邊路徑便是最短的。第二條確實也是路徑,但它有弦 ,把 換成 就會縮短。因此第二條既非誘導,亦非最短。
快速檢查
(設 由 上的三角形和孤立頂點 組成。求 ,並解釋它為何連通,以及兩個頂點間的最大距離為何恰好是二。)
解答 · 答案
缺少的頂點對為 ,所以補圖是以 為中心的星形圖。每片葉都與中心相鄰;不同的兩片葉經中心相連,卻不直接相鄰,所以距離恰好是二。這也說明定理中的「至多二」一般不能改成「至多一」。相反,如果不連通的 沒有任何邊,其補圖便是完全圖,不同頂點之間的距離是一。
快速檢查
(設 是同構,。證明把 限制在 上,可得同構 。「誘導」這個條件為何重要?)
解答 · 答案
限制後的映射是由 到 的雙射。 中的一對頂點在 中構成邊,當且僅當它們在 中構成邊,當且僅當其像在 中構成邊,也當且僅當其像在 中構成邊。因此邊與非邊都保留。如果任意而獨立地選取兩個子圖,結論便可能失敗:即使原同構是三角形上的恆等映射,也不能將兩邊生成路徑同構地映到完整三角形。誘導限制保留了所有頂點對原有的相鄰數據,原來的等價式才可以直接沿用。
矩陣冪數遊走
定理 8.1.14
(矩陣冪編碼遊走數目)
對每個整數 , 等於由 到 的長度 遊走數目。遊走可以重複頂點和邊。這裏 ,所以長度零的遊走停在起點。
證明
(對遊走長度作歸納)
當 ,單位矩陣恰好給出這些遊走;當 ,命題就是鄰接的定義。設命題對 成立。矩陣乘法給出 。第 項數的是倒數第二個頂點為 的遊走:若邊 存在,便把它接在一條長度 的遊走後面。這些類別互不相交,並窮盡所有長度 的遊走,由歸納法得證。 時沒有下標需要檢驗。
例如, 時 是共同鄰點的數目,而 。後者數的是走出去再走回來的遊走,雖然簡單圖沒有自環。矩陣項目為正表示存在指定長度的遊走,不一定存在同樣長度的簡單路徑。
例題詳解
例題 8.1.15
(給出重新標號)
設 的頂點集為 、邊為 ; 的頂點集為 、邊為 。映射 、、、 把這五條邊依次映為 。它是雙射。兩圖各恰好列出五條邊,五條不同的邊像便窮盡 ;因此非邊也得以保留,它是同構。
例題 8.1.16
(由矩陣平方讀出遊走)
對路徑 ,令 ,則 。其中 數了 與 ,而 數了 。前兩條遊走重複頂點;按通常簡單圈的約定,這些遊走都不是圈。
重新標號與遊走數目
設 對某排列矩陣滿足 。由於 ,反覆相乘便得對每個 都有 。這個等式也可以直接看出:把遊走中每個頂點改名,保留其相繼的邊和長度,再用逆改名把構造倒過來。特別是,對應頂點在每個固定長度上的閉遊走數目相同;把對角項目相加得 。因此這些量可以否定所謂的同構。它們仍然只是不變量,一組相同的不變量本身並不是給出的雙射。
三角形有一個有用的特殊情形。在簡單圖中,長度三的閉遊走有三個不同頂點:相鄰兩步重複同一頂點需要自環,而兩步後回到起點則會令第三步成為不容許的自環。因此每條這樣的遊走都沿一個三角形走一圈,而每個三角形共貢獻六條遊走:三個頂點各作起點,兩個方向各一條。於是 等於三角形的數目。這個除法依賴簡單無向圖的約定;若容許自環或重邊,便需要重新論證。
常見錯誤
常見錯誤
(把零對角線讀作「沒有邊」)
對角線為零只表示沒有自環,並不表示沒有邊,因為邊記錄在對角線以外。
常見錯誤
(把任何零一矩陣都讀作無向圖)
對稱且對角線為零的零一矩陣表示無向簡單圖;不對稱的零一矩陣只有在另外選定約定之後,才表示有向的相鄰關係。
常見錯誤
(只重排行而不重排列)
交換兩行而不交換相應的兩列,可能破壞對稱性,也不是為頂點改名的矩陣運算。改變標號必須同時作用於每條邊兩端的名稱。
練習
快速檢查
(頂點為 的圖有邊 。按此次序寫出其鄰接矩陣,以及包括每個頂點的鄰接表,並給出到路徑 的雙射。)
解答 · 答案
矩陣的四行為 、、、。鄰接表為 、、、。雙射 、、、 把列出的三條邊恰好映為目標的三條邊,因此也保留非邊。
快速檢查
(六圈與兩個互不相交的三角形是否同構?解釋度數相同為何不足,並給出能區分兩者的不變量。)
解答 · 答案
不同構。兩圖各頂點的度數都是二,但前者只有一個連通分支,後者有兩個。同構必須保留連通分支,所以度數序列相同並不足夠。
快速檢查
(對簡單圖證明對角項目 是包含 的三角形數目的兩倍。為何這並不表示所有長度三的遊走都是三角形?)
解答 · 答案
以 為起點的長度三閉遊走形如 。由於圖是簡單圖,相鄰頂點互不相同,閉合的那條邊迫使 ;同時 。因此三個頂點互異並組成三角形。每個包含 的三角形恰好給出兩條這樣的遊走,每個方向一條。矩陣冪定理數的正是它們。不閉合的長度三遊走可以折返,例如單條邊上的 ,它不是三角形。