簡單圖大概是所有定義裡頭最簡單的了。所謂的簡單圖,就是沒有包含重邊(multi-edge)和自環(self-loop)的圖。利用前一節我們介紹的度序列,我們可以透過給定一個合法的度序列來生成簡單圖。
§6.1 合法的簡單圖
Havel 以及 Hakimi 分別在 1955、1962 年發表了藉由給定度序列構造簡單圖的演算法。我們說一個序列 $(d_1, d_2, \ldots, d_n)$ 是 可製圖的(graphical) 若且唯若這個序列是某個簡單圖的度序列。
證明
"$\Leftarrow$" 這個方向是簡單的,如果少了一個點的序列是可製圖的,那麼把這個點補回去就會得到一個滿足度數要求的簡單圖。
"$\Rightarrow$" 令滿足度序列的圖 $G$ 所成的集合為 $\mathcal{G}$。假設存在至少一個簡單圖使得對於任意點 $v_i\in V$ 其度數恰好是 $d_i$。我們的目標是要證明:存在 $G\in\mathcal{G}$ 使得 $v_1$ 的鄰居 $N(v_1) = \set{v_2, \ldots, v_{d_1+1}}$。對於所有圖 $G\in\mathcal{G}$,我們定義 $i_G$ 為最小的編號使得 $v_1$ 與 $v_2, \ldots, v_{i_G}$ 相連,但是不與 $v_{i_G+1}$ 相連。顯然我們想證明存在一個滿足度序列的圖 $G$ 使得 $i_G = d_1+1$。
我們利用反證法證明之:若不然,$\forall G\in\mathcal{G},\ i_G \le d_1$。令 $G$ 是所有 $\mathcal{G}$ 裡面的圖中 $i_G$ 最大者。由於 $i_G \le d_1$,此時必存在 $j > i_G+1$ 使得 $(v_1, v_j)\in E$。注意到 $d_{i_G+1} \ge d_j$,但是在該圖上 $(v_1, v_{i_G+1})\notin E$、卻同時有 $(v_1, v_j)\in E$。因此我們可以推得:存在另一個 $v_k\in V$ 使得 $(v_{i_G+1}, v_k)\in E$ 但是 $(v_j, v_k)\notin E$。
現在讓我們把圖 $G$ 稍微修改一下:令 $G' = G -\set{(v_{i_G+1}, v_k), (v_1, v_j)} \cup \set{(v_1, v_{i_G+1}), (v_j, v_k)}$。此時 $G'$ 滿足所有度序列條件,因此 $G'\in \mathcal{G}$。但是 $i_{G'} > i_G$,與 $i_G$ 最大之假設矛盾,得證。
從 Havel-Hakimi 定理的敘述和證明我們不難得出具體的構造演算法。但真的得透過構造來證明指定度序列的簡單圖存在性嗎?答案是不一定需要。在 1960 年 Erdős 與 Gallai 發表了非構造性的數學論述:
Erdős-Gallai 定理的證明其實有點困難。最早的 1960 年的論文相當地繁雜。在 1970 年左右,法國數學家 Berge 利用網路流的概念證明了 E-G 定理。1986 年印度數學家 Choudum 提出了一個相對簡潔一點的數學歸納法證明。在這個證明裡頭,我們可以隱約看到剛才 Havel-Hakimi 定理的證明的影子。
證明
"$\Rightarrow$" 這個部分相當直觀:首先,對於任意簡單圖來說,由握手定理可以推得度數和必須是偶數。若我們取任意 $k$ 個點的集合 $S\subset V$,這個圖會被拆成兩部分:$G[S]$ 以及 $G[V\setminus S]$。對於一個簡單圖來說,$G[S]$ 至多只能有 $k(k-1)/2$ 條邊,因此這些邊貢獻的度數和至多為 $k(k-1)$。另外對於每一個 $V\setminus S$ 裡面的點 $v_i$,其連入 $S$ 至多只有 $\min(d_i, k)$ 條邊。於是,取 $S$ 為度數最大的 $k$ 個點,其度數和至多只能是 $k(k-1) + \sum_{i=k+1}^n \min(d_i, k)$。
"$\Leftarrow$" 我們可以對總點數加度數 $n+\sum d_i$ 進行歸納。
- (Base Case) 如果圖只有一個點 $n=1$,那麼 $d_1=0$ 是唯一可製圖的例子。
- (Inductive Step, Case 1) 如果 $d_n=0$,我們可以把這個點拿掉而不改變所有條件,根據歸納假設,此時存在一個簡單圖滿足要求。
- (Inductive Step, Case 2) 如果 $d_n>0$,此時顯然有 $d_n \le n-1$。我們選取 $t$ 使得 $d_1=d_2=\cdots = d_t > d_{t+1}$(如果 $t$ 不存在的話就讓 $t=n-1$)。接下來我們考慮修改後的度序列 $(d_1, d_2, \ldots, d_t -1, \ldots, d_{n-1}, d_n-1)$。選取的 $t$ 會保證新的序列也是非遞增的。接下來我們要作兩件事:首先證明新的度序列是可製圖的、然後利用做出來的圖,實現一個能對應原本度序列的圖。
證明新的度序列是可製圖的,可以透過分析以下幾個情形證明之:
- ($k\ge t$):比較 舊序列與新序列的不等式,發現左邊的值必定 $-1$、右邊的值可能少 $1$ 或不變。因此新序列在此情形的不等式保證成立。
- ($k < t$):此時不等式左邊永遠是 $kd_1$。接下來分成四種情形討論:
- $k > d_1$:此時 $kd_1 \le k(k-1)$,新的不等式保證成立。
- $k = d_1$:除非 $k=t-1$、$t=n-1$ 而且 $d_n=1$ 不然保證成立,但是此情形發生時,$d_1+\cdots+d_n=t(t-1)+1$ 是個奇數,與總度數為偶數之假設矛盾。
- $d_n\le k < d_1$:[定理 1.16,很巧妙的一步] 根據舊的不等式,把變數 $k$ 用 $k+1$ 重新寫過會得到
- $k < d_n$:不等式不會發生變化,所以保證成立。
證明新的度序列是可製圖的以後,根據歸納假設,存在一個圖 $G'$ 滿足新的度序列。如果此時 $(v_t, v_n)\notin E$,那我們把這條邊加上便能實現原本的度序列。如果此時 $(v_t, v_n)\in E$,那麼我們要找另外一條邊來交換:首先因為 $d_t-1 \le n-2$,存在一個 $v_i\neq v_n\in V$ 使得 $(v_t, v_i)\notin E$。接著,由於 $d_i \ge d_n$,存在一個 $d_j$ 使得 $(d_i, d_j)\in E$ 但 $(d_n, d_j)\notin E$。於是我們就可以把這個圖 $G'$ 換一下,扣掉原本的兩條邊、加回後兩條邊,得到一個 $(v_t, v_n)\notin E$ 但保有相同度序列的圖,此時再把 $(v_t, v_n)$ 加上去就構造完畢囉。
§6.2 樹的度序列
我們知道 $n$ 個點的樹是一個恰好有 $n-1$ 條邊的連通圖。如果 $d_1, \cdots, d_n$ 是這顆樹的度序列,顯然必須有 $d_1+\cdots + d_n = 2(n-1)$。不意外地,這也幾乎是從度序列建構一棵樹的充分條件。
這個證明只要用數學歸納法即可,不難。有趣的是,這個條件恰好也正是要讓一個連通圖存在的邊界條件。
§6.3 簡單連通圖
這個證明,可以直接透過 Havel-Hakimi 定理加上樹的度序列定理的證明方法證得:每一次挑選度數最小的點,將這個點連到度數最大的那些點並移除,得到總邊數較少的可製圖序列。不難驗證此時總度數仍滿足敘述條件。根據歸納假設我們得到一個連通圖,然後加回這個點時自然也是連通圖了。
習題
- 證明題 我們說一個兩個序列 $(a_1, a_2, \ldots, a_n)$ 和 $(b_1, b_2, \ldots, b_n)$ 是個二分圖序列(bigraphic),如果存在一個兩邊各自有 $n$ 個點的二分圖使得兩邊度數分別是 $a_1, \ldots, a_n, b_1, \ldots, b_n$。Gale-Ryser 定理 [1957] 證明了,若 $a_1\ge \cdots \ge a_n$,則兩序列是 bigraphic 若且唯若
- $\sum_{i=1}^n a_i = \sum_{i=1}^n b_i$,而且
- 對所有的 $1\le k\le n$:$\sum_{i=1}^k a_i \le \sum_{i=1}^n \min(b_i, k)$。
- 演算法 設計一個 $O(n)$ 時間的演算法,判斷一個長度為 $n$ 的非負整數序列是否為某個簡單圖的度序列。
- 程設題 幼稚園吃午餐問題?