動機
生成樹以無冗餘的邊連接所有頂點。加一條邊會產生一個圈;加多條邊則會產生許多互相重疊的圈。怎樣不逐一枚舉所有圈,就描述每個偶度邊集?方法是為每條非樹邊保留一個基本圈,用對稱差組合它們。這為後續割與平面對偶論證中使用的循環空間提供了具體的基。
定義
本節 是有限無向簡單圖,有 個頂點、 條邊和 個連通分支,孤立頂點也算分支。
定義 1.3.1
(邊集與偶度邊集)
邊集指 的子集,同時保留原來所有頂點;某頂點在該邊集中的度數只計算選中的關聯邊。若每個頂點的選中度數均為偶數(包括零),稱該邊集為偶度邊集。空邊集是偶度的。
定義 1.3.2
(對稱差與循環空間)
邊集 的對稱差 是恰好屬於 之一的邊所成的集合。將每個邊集視為 中的零一向量,對稱差就是加法。 的循環空間是所有偶度邊集連同這個加法所成的集合。
每個頂點在 中的度數奇偶性,等於它在 中度數奇偶性的模二和,因此偶度邊集的對稱差仍為偶度,循環空間是 的子空間。空間的元素是邊集,不一定是單個簡單圈。
定義 1.3.3
(生成森林與基本圈)
的生成森林 是一個無圈邊集,在每個連通分支內包含一棵生成樹。對不在 中的邊 , 中唯一的 – 路徑與 組成基本圈 。
生成森林滿足 ,包括孤立頂點及空圖的情形。每條不在 中的邊 的端點處於同一分支,所以 中存在 – 路徑;又因 無圈,這條路徑唯一。 唯一不在森林中的邊就是 。
定理 1.3.4
(基本圈構成基)
對任意生成森林 ,每個偶度邊集 都有唯一表達式
空對稱差為空集。因此基本圈構成循環空間的基,其維數為 ,空間恰有 個邊集。
證明
(消去非森林邊的證明)
設 為偶度邊集,令
每個 恰有一條非森林邊,即 本身。因此除 本身外, 中每條非森林邊 恰出現在所加的一個集合中,從而被抵消;不在 中的非森林邊則不出現在任何一個集合中。所以 。每個基本圈都是偶度邊集,對稱差保持偶度,所以 仍為偶度。
森林內的偶度邊集只能為空。否則其選中子圖是非空森林;其中某個含邊的分支是非平凡樹,有選中度數為一的葉頂點,與偶度矛盾。因此 ,即得 的上述表達式。
唯一性:設 ,其中 是某個非森林邊集合。在所有基本圈中,非森林邊 只出現在 中,所以 當且僅當 ,故 。特別地,基本圈線性無關,而第一部分說明它們生成整個空間。它們有 個,這個基的 個子集給出不同的偶度邊集。
證明透視
無圈與生成各用在哪裏
證明分開使用 的兩個性質。「生成」只用來保證每條非森林邊都有基本圈:它的端點在同一分支內,而 連通該分支。「無圈」用了兩次:使路徑從而 唯一,以及透過葉頂點論證說明 內的偶度邊集為空。
關鍵一步是觀察到每個 與非森林邊的交恰為 。以非森林邊為座標,基本圈就是標準單位向量。這一個事實既清除了 的非森林部分,又讀出了係數,所以存在性與唯一性來自同一觀察。論證之所以收尾,是因為剩下的是一個沒有餘地保持非空的偶度邊集。
每個假設都不可缺。在三角形中取 ,它無圈但不生成,沒有任何邊有基本圈,三角形卻是偶度的。若 取整個三角形,它生成但不無圈,就沒有非森林邊,表達式只給出 ,三角形同樣被遺漏。
森林本身沒有非森林邊,其唯一偶度邊集為空。非連通圖中每個基本圈都留在自己的分支內,不需要虛構連接不同分支的邊。更換生成森林會改變所選的基,卻不會改變偶度邊集本身或它們的數目。
概念視角代數
循環空間是一個核
設 是 在 上的 頂點–邊關聯矩陣。對指示向量為 的邊集, 就是 的選中度數模二。所以循環空間恰為 。由秩–零化度定理,,於是基定理同時算出秩:在 上 。 中以 為指標的行就是割 ,對頂點集 中的行求和得 ,所以 的行空間正是下面研究的割的集合。
核的描述把偶度化為一個線性方程;下一節研究行空間,即割。
圈、割與奇偶
定理 1.3.5
(偶度邊集可分解成圈,且與割偶數相交)
每個非空偶度邊集都可寫成邊互不相交的簡單圈之並。對任意頂點集 ,偶度邊集與割 的交集有偶數條邊。
證明
(剝去圈與對度數求和的證明)
先證第一項。只看選中邊及其關聯頂點組成的子圖;其中每個頂點的正度數都是偶數,至少為二。在這個子圖中取最長簡單路徑。由極大性,其末端頂點的所有鄰點都在路徑上,而末端頂點有一個不同於相鄰前驅的鄰點;這條邊閉合成一個簡單圈。刪除該圈的邊:每個圈上頂點恰失去兩條選中關聯邊,因此剩餘邊集仍為偶度。不斷重複,每次都刪除邊,最終結束。得到的圈邊互不相交,但可以共用頂點,分解也未必唯一。
再對 中頂點求選中度數之和。 內部的每條選中邊貢獻二,穿過割的每條選中邊貢獻一。該和為偶數,故穿割的選中邊數也為偶數。證明適用於任意頂點集,不要求兩邊誘導圖連通。
特別地,橋不可能屬於偶度邊集:刪除橋 後,含其一個端點的分支的頂點集 滿足 ,與它相交一次會違反偶數性。反過來,不是橋的邊位於某個圈上,故屬於某個偶度邊集。這是存在性陳述,不是說每個偶度邊集都包含每條非橋邊。
逆命題與割空間的大小
割的奇偶定理也有逆命題。若一個邊集與每個割相交的邊數都是偶數,對任意頂點取只含該頂點的單點集。其割恰由該頂點的所有關聯邊組成;相交為偶數就說明該頂點的選中度數為偶數。逐點檢查可知該邊集為偶度。因此檢查所有單點割已足以證明偶度;前面的定理隨後保證它與任意割都偶數相交。
還可以計算不同割的數目。對於頂點集 ,一條邊恰跨越兩個割之一,當且僅當它跨越 的割。所以 ,割在對稱差下組成向量空間。空集和整個頂點集都對應空割;一般說來,不同頂點集也可能產生同一個割,不能把全部 個頂點集當作不同割來計數。
定理 1.3.6
(不同割的數目)
對頂點集 , 當且僅當 是若干完整連通分支的並。因此 恰有 個不同的割。
證明
(經由空割的證明)
由上面的恆等式, 表示 為空。一個頂點集的割為空恰表示沒有邊連接它與補集,於是每個分支要麼全部選入,要麼全部不選。這樣的分支之並有 種,孤立頂點也各自提供一次選擇。對任意固定割,其所有表示集恰是某個表示集與這些分支之並作對稱差所得,所以每個割恰有 種表示,總數為 。空圖的兩個指數都為零,結論仍成立。
因此循環空間和割空間的維數之和為 。
反例模式
維數互補並不表示交集平凡
待檢驗的說法:既然兩個維數之和為 ,循環空間與割空間就只有空邊集是公共元素。取四邊形 及 。邊 都連接 中一個頂點與 之一,所以 就是整個四邊形。同一個邊集在每個頂點的選中度數都是二,所以它是偶度的。它是兩個空間共有的非空邊集,該說法不成立。真正成立的是 上的正交性:每個偶度邊集與每個割都有偶數條公共邊。這裏的交有四條邊,在內積中貢獻零,儘管四條邊都是共有的。
將該四邊形與另一張僅由兩個頂點及一條邊組成的圖比較:那條邊是割卻不是偶度邊集,因為它的兩個端點選中度數為一。整個四邊形在這個圖中既偶度又是割;一般圖中的單個圈卻未必是割。判斷兩個空間時要檢查相應定義,不能只靠圖形看起來像邊界。
這個計數還說明為甚麼分支是表示方式中歧義的單位。連通圖中將割的兩側全部互換,不改變穿割邊,恰得到兩種表示。多個分支之間沒有邊,故可以在每個分支內獨立互換兩側。孤立頂點也可獨立變換,卻永遠不會改變割邊;因此不需假設割的任一側連通。
是:在二元域上,割空間正是循環空間的正交補。
自然延伸的下一個問題
割是否恰好是與每個偶度邊集交於偶數條邊的邊集?
是:在二元域上,割空間正是循環空間的正交補。
每個割與每個偶度邊集都交於偶數條邊,所以割空間包含於循環空間的正交補。在 上該正交補的維數是 ,與割空間的維數相同,因此兩者相等。由於基本圈生成循環空間,一個邊集是割,當且僅當它與每個基本圈都交於偶數條邊。
例題
例題 1.3.7
(一個正方形及一條對角線)
設邊為 ,選森林 。非森林邊為 ,其基本圈分別為 和 。對稱差抵消 ,得到 ,即另一三角形。四個偶度邊集是空集、兩個基本圈及其對稱差。這裏 。
例題 1.3.8
(分支與孤立頂點都要計算)
取頂點 上的三角形、另一條邊 和孤立頂點 。則 。生成森林包含三角形的兩條邊及 ,故只有一個基本圈,即該三角形,而 。偶度邊集只有空集和三角形。 是橋,不能被任何偶度邊集選中;孤立頂點雖然沒有邊,卻同時計入 和 。
例題 1.3.9
(圈之並未必是單個圈)
兩個三角形恰共用一個頂點而不共邊。它們的並為偶度邊集:公共頂點度數為四,其餘頂點度數均為二。該邊集不是單個簡單圈,因為公共頂點需要被訪問兩次。它仍是兩個邊不相交的圈之並,說明循環空間的元素不只有簡單圈。
常見錯誤
常見錯誤
(普通並不是加法)
邊集的普通並不是循環空間中的加法。正方形例中兩個基本圈共用 ;它們的普通並是全部五條邊,此時 與 的選中度數為三。對稱差則抵消這兩條公共邊,結果為偶度。
常見錯誤
(維數不是圈的數目)
一組基不是全部簡單圈的列表, 是獨立二元選擇的個數,不是簡單圈的數目。正方形加一條對角線有三個簡單圈,即兩個三角形和正方形,但循環空間的維數是 ;正方形是兩個三角形之和。
常見錯誤
(計算分支數時遺漏孤立頂點)
公式 只在 計入所有分支(包括孤立頂點)時成立。對一個三角形、另一條邊和一個孤立頂點,若取 而保留 ,會得到 ;但三角形說明維數是 。
奇偶性要在所選邊集中檢查,不是在原圖中檢查:原圖中度數為奇數的頂點,在某個偶度子集中的選中度數可以是偶數。
練習
快速檢查
(正方形加對角線的例子中,用基本圈表達三角形 ,並驗證各頂點的選中度數。)
使用兩條非森林邊 與 。
解答 · 答案
它是 。 的選中度數均為二, 為零,故它是偶度邊集。
快速檢查
(一個圖由兩個互不相交的三角形和一個孤立頂點組成。求 、循環空間維數及所有偶度邊集。)
把孤立頂點算作一個分支。
解答 · 答案
,維數為 。四個偶度邊集為空集、分別只取其中一個三角形,以及取兩個三角形的並。孤立頂點屬於圖,但沒有關聯邊。
快速檢查
(證明森林中的非空邊集不可能是偶度的。為甚麼僅數邊數不足以證明?)
在選中子圖中找一個葉頂點。
解答 · 答案
森林的非空選中子圖有一個含邊的分支,該分支是非平凡樹,在選中子圖中有度數為一的葉頂點,所以該邊集不是偶度的。邊的條數本身不能決定頂點度數:邊數相同的集合可能具有不同的度數奇偶。
快速檢查
(設 為任意頂點集, 為偶度邊集。若 恰含 中的三條邊,能得出甚麼結論?)
與割的奇偶定理比較。
解答 · 答案
這樣的偶度邊集不存在:割的奇偶定理要求選中的穿割邊數為偶數,而三為奇數。這裏使用的是選中邊數,不是割中所有邊的總數。