把互相衝突的頂點分成兩類
假設每個頂點要塗上兩種顏色之一,而且每條邊的兩端顏色不同;例如這可表示把互相衝突的任務分成兩組。
定義 1.2.1
(二部圖)
存在這種著色的圖稱為二部圖:兩個顏色類構成頂點的劃分,其中一類可以為空。
以下考慮有限無向簡單圖,允許不連通及孤立頂點。圈至少有三個不同頂點,起點在結尾重複除外。
奇圈判準
定理 1.2.2
(二部圖等價於沒有奇圈)
有限無向簡單圖是二部圖,當且僅當它不含奇數長度的圈。
證明
(顏色交替與樹距離的奇偶)
若存在合法二色著色,沿每條邊行走都會轉換顏色。沿圈回到起點顏色必須轉換偶數次,因此每個圈長度均為偶數。
反過來,在每個連通分支分別處理。選一個根並建立廣度優先搜尋樹,按頂點到根的樹距離奇偶著色。假設某邊 兩端同色。由 到 的唯一樹路徑長度為偶數:若 是它們的最低共同祖先,其長度為 。邊 不是樹邊,因樹邊兩端的深度奇偶不同。把它加到簡單樹路徑上得到奇圈。因此若沒有奇圈,沒有邊可連接同色頂點,著色必定合法。孤立根可取任一顏色。
證明透視
失敗的邊如何給出具體見證
兩條由根通往頂點的路徑可能共用開首部分,因此直接把兩條完整路徑和該邊接起來可能重複頂點。移去共同部分,改用經最低共同祖先的唯一樹路徑。它是簡單路徑;端點奇偶相同時,其長度為偶數,加上非樹邊便形成奇圈。這同時說明證書的奇偶性和簡單性。
算法及輸出
由未著色頂點開始廣度優先搜尋,給它顏色零,並讓每個新發現鄰點取相反顏色。若檢查到某邊的兩端同色,利用兩條樹路徑及該邊重構並輸出奇圈。若一個分支無衝突地結束,就從另一未著色頂點重新開始;全部完成後輸出兩個顏色類。用鄰接串列時,每個頂點和每條邊只檢查常數次,時間為 ,包括輸入表示的空間為 ;重構一個見證所需的父節點指標只用額外 空間。空圖輸出兩個空類。
例子
例題 1.2.3
(路徑與四圈)
對路徑 ,以 為根,深度奇偶給出顏色類 和 ,每條邊都跨越兩類。加入 得到四圈,此著色仍然有效。
例題 1.2.4
(三角形給出最短的見證)
對三角形邊 ,以 為根。廣度優先搜尋可令 都是 的子節點,因此同色。邊 產生衝突;樹路徑 加上 是長度三的奇圈。另一個孤立頂點可取任一顏色,但不會消除此障礙。
例題 1.2.5
(五圈:衝突邊遠離根)
取圈 ,以 為根進行搜尋。則 的深度為 , 的深度為 ,父節點分別是 和 。邊 連接兩個深度為 的頂點,所以它就是衝突邊。兩者的最低共同祖先是 ,樹路徑長度為 ,即 。加上 ,見證就是整個五圈。這裏見證和三角形的情形一樣經過根;一般而言最低共同祖先可以更深,只用到兩條根路徑在它之下的部分。
反例模式
只檢查一個分支不夠
一個圖可以有二分的分支,另有獨立三角形。若只從第一個分支開始搜尋,就找不到衝突,但整個圖不是二部圖。從每個未著色分支重新開始是算法的一部分,不是外觀細節。
常見錯誤
(一個偶圈甚麼也證明不了)
找到一個偶圈並不能說明圖是二部圖。 含有四圈 ,但 是三角形。判準要求沒有任何奇圈,實際上要用整個圖的合法二色著色來證明。
常見錯誤
(自由選色造成的衝突不是見證)
逐個頂點任意選色,即使在二部圖中也可能出現衝突。在路徑 上,先取 、,此時兩者尚無聯繫;接著 是被迫的,而 必須同時異於 和 ,這不可能。但這條路徑是二部圖。只有當涉及的每個顏色都是從同一分支的一個根被迫推出時(例如廣度優先搜尋),衝突才證明奇圈存在。
練習
快速檢查
(給六圈 一個二色著色。)
解答 · 答案
取 和 。
快速檢查
(解釋為何在二部圖中加入連接兩個同色頂點的弦會破壞該著色;每條新邊都會破壞二分性嗎?)
解答 · 答案
新邊的兩端同色,違反該著色;但不是所有新邊都破壞二分性,例如加入一條原本不存在、跨越兩類的邊可保留它。
快速檢查
(廣度優先樹的根 有子節點 ,圖另有邊 。給出奇圈見證。)
解答 · 答案
樹路徑 加上 是三邊圈。
快速檢查
(對三個孤立頂點,算法可輸出甚麼?)
解答 · 答案
三個頂點的任意劃分都是合法二色著色;每次由新頂點重啟,可把三者全放在一類,另一類留空。