從兩兩比較到有向圖
假設每兩位選手恰好比賽一次,而且沒有和局。從勝者向負者畫箭嘴,就記錄了所有結果。但結果未必能排成一致的名次:可能 勝 , 勝 ,而 又勝 。相同模型也適用於其他完整而不對稱的兩兩比較,無須先給對象指定數值分數。
定義 5.2.1
(競賽圖、有向路徑與有向圈)
競賽圖是有限有向圖:沒有自環,而且對任意不同頂點 , 和 恰有一條。有向路徑由互不相同的頂點組成,相鄰箭嘴都向前。哈密頓(Hamilton)路徑恰好經過每個頂點一次。有向圈沿箭嘴走,除起點與終點相同外頂點不重複。出度 是 的出鄰點數。我們容許空競賽圖;約定空排列是其哈密頓排列。討論可達性時,頂點可透過長度零的路徑到達自身。
每個競賽圖都有哈密頓路徑
這個結論不要求存在戰勝所有對手的選手。證明的辦法是把一個新頂點插入已有路徑,而非按出度排序。
定理 5.2.2
(競賽圖的有向哈密頓路徑)
每個有限競賽圖都有頂點排列 ,使每個 都滿足 。
證明
(插入新頂點)
對頂點數歸納。空圖和單頂點圖顯然成立。刪除頂點 ,由歸納假設,把其餘頂點排成有向路徑 。若 ,便把 放在最前。否則,取滿足 的最大指標 。若 ,便把 加在末尾;若 ,由最大性, 不指向 。競賽圖中兩者之間恰有一個方向,故 。把 插在 和 之間,只把原來的相鄰箭嘴替換為 ,所得仍是經過所有頂點的有向路徑。
證明透視
為甚麼最後一個入鄰點標出可用的空位
歸納假設用於刪去 後的競賽圖,而它仍是競賽圖:這個類別在刪去頂點後封閉,證明正依賴這一點。插入所需的是路徑上的一個轉換位置:某處有 且 ,或者是路徑的某一端。分情況討論保證這樣的位置存在。若 ,轉換位置在起點之前。否則 ,於是滿足 的指標集非空,有最大元 。或者 ,把 放在末尾;或者 不指向 。
最後一步是競賽圖公理唯一被使用之處:一對頂點若不是 ,就必然是 。在一般有向圖中,這兩點可能不相鄰,空位便無法接上。取最大指標只是找出轉換位置的方便辦法,並非唯一辦法;在五頂點例子中,第一個入鄰點 也可以,因為 。由於只改動了一對相鄰頂點,而兩條新箭嘴都已檢查,這一步便完成。
如果查詢任意一對頂點間的方向需要常數時間,每次插入至多檢查當前路徑長度,總共需要 次方向檢查。哈密頓路徑也不表示前面的每個頂點都勝過後面的每個頂點;定義只要求相鄰箭嘴向前。
常見錯誤
(按出度排序代替插入)
把頂點按出度由大到小排列,若相同出度任意排次序,所得未必是有向路徑。在 上取 、、、、、,出度為 ,次序 的出度不增;但 與 之間的箭嘴是 ,第一步就向後。插入證明從不依賴出度。
常見錯誤
(把路徑升格為哈密頓圈)
定理保證的是路徑而非圈。在傳遞競賽圖 、、 中,排列 是哈密頓路徑,但 的出度為零,無法離開,所以沒有有向圈經過它。傳遞競賽圖根本沒有任何有向圈。
例題 5.2.3
(插入後的路徑仍可能含反向比較)
設 、、。先取路徑 ,因為 ,把 加在末尾,得到哈密頓路徑 。然而 相對於排列向後,並閉合成有向三角形。所以路徑排列未必把所有比較排成一致名次。
例題 5.2.4
(把頂點插入路徑中間)
取五個頂點 。在 之間,箭嘴為 、、、、 和 ,因此 是一條有向路徑。涉及 的四次比較為 、、 和 。這十條箭嘴確定了每一對頂點之間的方向。
沿已有路徑檢查哪些頂點指向 :它們是 和 。其中最後一個是第三個位置的 ,其後繼為 。由於 ,把 插入這個空位,得到路徑 ;相鄰箭嘴依次是 、、 和 。特別是, 不妨礙構造,因為非相鄰頂點間的箭嘴無須向前。指向 的頂點不一定連成一段,所以尋找最後一個時要檢查相關位置。
甚麼情況下比較能排成一致名次?
定義 5.2.5
(傳遞競賽圖與有向三角形)
若不同頂點滿足 且 時總有 ,稱競賽圖傳遞。有向三角形是三個不同頂點組成的有向圈。
下面的定理說明,等價地,傳遞競賽圖的頂點可以排成一個次序,使所有箭嘴都從前指向後。
定理 5.2.6
(傳遞性的三個等價條件)
對有限競賽圖,下列條件等價:(1)它是傳遞的;(2)它沒有有向三角形;(3)存在一個頂點排列,使所有箭嘴向前。
證明
(從三點的條件得到整體次序)
傳遞圖不可能含 ,因為前兩條箭嘴要求 。現在假設沒有有向三角形。取一條哈密頓路徑 ,對 歸納證明 時都有 。相鄰情形由路徑定義成立。距離更大時,歸納假設給出 ,路徑給出 。若 ,便出現有向三角形,因此只能有 。最後,若所有箭嘴都向前,則 和 分別迫使 在 前、 在 前,故 ,即傳遞性成立。
傳遞競賽圖的這種次序是唯一的:任意兩頂點之間的箭嘴都決定它們的先後。 個頂點沿此次序的出度為 。更一般地,任何競賽圖的出度之和都等於 ,因為每對頂點恰好貢獻一條出箭嘴。但這個和不能判定傳遞性:相同頂點數的競賽圖都有相同的和。
反例模式
路徑不是整體排名
在三頂點有向圈中, 是哈密頓路徑,但 ;三個頂點的出度都是一。因此只按出度排序,未必能使所有箭嘴向前;有哈密頓路徑也不代表沒有有向圈。
縮短有向圈
不存在有向三角形也會排除更長的有向圈。以下構造說明競賽圖的特殊條件為何重要:圈上任何兩個不相鄰的頂點之間仍有箭嘴,可以用它作為捷徑。
引理 5.2.7
(有向圈的頂點中含有向三角形)
在競賽圖中,每個 的有向圈 都含有三個頂點構成有向三角形。
證明
(沿圈取捷徑)
設 是有向圈,其中 。若 ,它已經是三角形。若 ,考察 與 間的箭嘴:若為 ,首三個頂點構成有向三角形 ;否則箭嘴是 ,可以省去 ,得到較短的有向圈 ,其頂點仍互不相同。反覆執行,直至出現三角形;每次取捷徑都使圈的長度減少,所以過程終止。
這比只說競賽圖中某處存在三角形更強:三角形的頂點可以從原圈中選取。但這並不是說原圈上任取三個頂點都形成有向三角形。一般有向圖未必有這條捷徑,故不能照搬此論證。
出度大的頂點與短路徑
定義 5.2.8
(王點)
若頂點 能透過至多兩條有向邊到達每個頂點,就稱 為王點。其中 透過長度零的路徑到達自己。王點不一定直接勝過所有對手。
定理 5.2.9
(最大出度頂點是王點)
在非空有限競賽圖中,任意最大出度頂點都能透過至多兩條有向邊到達每個其他頂點。
證明
(比較出鄰點)
取最大出度頂點 。若 ,結論顯然。否則 。假設不存在 使 。 的每個出鄰點 都不同於 ,因而必須滿足 。此外還有 ,所以 至少有 個出鄰點,違反 的出度最大。因此必有這樣的 ,所需路徑是 。
反例模式
離開競賽圖,最大出度並不足夠
有人或會以為:在任何有向圖中,最大出度頂點都能在兩步內到達每個頂點。取頂點 ,只有箭嘴 、 和 。此時 是最大出度,但沒有箭嘴指向 ,所以 根本不能到達 。證明在「否則 」一步失效:這裏 與 之間兩個方向都沒有箭嘴。定理需要競賽圖公理:每對頂點恰好以一個方向相連。
例題 5.2.10
(王點不一定保持全勝)
在 中,三個出度都是一,而且每個頂點都是王點。例如 沿 到達 ,儘管直接比賽中 勝 。王點描述可達性,並非不敗選手。
例題 5.2.11
(出度較小的王點)
在 上取箭嘴 、、、、 和 。 的出度依次為 。儘管如此, 是王點:它直接到達 ,並分別沿 和 到達 。因此定理提供了尋找王點的可靠方法,但逆命題不成立:王點不一定具有最大出度。
練習
快速檢查
(頂點集為 ,箭嘴為 、、、、、。找一條哈密頓路徑、一個有向三角形和一個王點。)
讓路徑從勝過 的頂點開始。
解答 · 答案
是哈密頓路徑; 是有向三角形。 是王點:它直接到達 ,並透過 (或 )到達 。
快速檢查
(四頂點競賽圖的出度為 。它一定傳遞嗎?解釋原因。)
先刪去出度為三的頂點。
解答 · 答案
一定。出度為三的頂點勝過其他所有頂點。刪除它後,其餘三個頂點原來的出度 不變,因為與已刪頂點之間的邊指向它們。出度為二的頂點勝過剩下兩個,最後一條邊決定其餘二者的次序,因此按出度 排列時所有箭嘴向前。
快速檢查
(舉出一個三頂點競賽圖,它有哈密頓路徑但沒有出度為二的頂點。它有王點嗎?)
出度之和必須為三。
解答 · 答案
取 。 是哈密頓路徑,每個頂點出度都是一。每個頂點都是王點:對勝過它的頂點,可以經過第三個頂點到達。
快速檢查
(若競賽圖有某長度的有向圈,它必有頂點取自該圈的有向三角形嗎?用捷徑證明,不要假設給出的圈本身有三條邊。)
考察圈上第一與第三個頂點之間的箭嘴。
解答 · 答案
必有。若圈長至少為四,圈上第一與第三頂點之間的箭嘴或者與前兩條邊組成三角形,或者容許我們省去第二個頂點而得到較短的有向圈。重複此步驟終會得到三角形,而且只使用原圈上的頂點。
快速檢查
(若非空競賽圖中的一個頂點勝過所有其他頂點,證明它是唯一的王點。)
問一問:其他頂點究竟能否到達它?
解答 · 答案
設 勝過其他所有頂點。它至多經過一條邊便能到達所有頂點,因此是王點。其他頂點都不能沿有向路徑到達 :這樣的路徑最後一條邊必須指向 ,但與 相接的邊都從 指出。所以 是唯一的王點。