動機
知道一個連通圖有生成樹,並不能告訴我們有多少種選擇。直接搜尋所有邊子集,即使每個候選都容易檢驗,代價也會變得很高。關聯矩陣把這個問題轉化為一個行列式,其中的抵消作用會自動剔除含圈的選擇。
權重所保留的資訊比單個計數更多。邊權的乘積記錄了每一棵樹,它們的和則成為一個生成多項式。對該多項式求導,就能回答關於隨機選取一棵加權樹的概率問題。
行列式恆等式在此處給出證明;只假設有限維矩陣乘法以及行列式的多重線性。
定義
定義 1.6.1
(帶標號的邊、關聯與生成樹多項式)
設 是有 個頂點的有限無向多重圖,其邊帶有標號;容許存在自環與平行邊。給每條邊賦予權重 ,起初它是有理數域上的不定元。生成樹包含每個頂點,是連通的且不含圈;自環永遠不屬於生成樹,兩條平行邊構成長度為二的圈。
定義
對於只有一個頂點的情形,即使存在自環,空樹也貢獻一。頂點數多於一的非連通圖,其生成樹多項式為零。
對每條非自環邊任意指定方向。其關聯列在起點處為負一,在終點處為正一,其餘位置為零。自環對應零列。設由此得到的 行 列矩陣為 ,邊權的對角矩陣為 。加權拉普拉斯(Laplace)矩陣為 。其非對角元等於這兩個頂點之間各邊權之和的相反數;其對角元是與該頂點關聯的非自環邊的權之和。這一約定同樣將自環排除在對角線之外。
選定根頂點 ,從 中刪去它所在的行,得到 。從 中刪去根所在的行與列,得到 。零階矩陣的行列式規定為一。
定理/命題
定理 1.6.2
(拉普拉斯矩陣的每個主餘因子都等於生成樹多項式)
對每個有限加權多重圖以及任意選定的根,
該等式是多項式恆等式。特別地,取單位權重時,它恰好給出帶標號生成樹的數目,並且該行列式既不依賴於任意指定的邊方向,也不依賴於刪去哪個根。
定理 1.6.3
(完全圖與完全二部圖有顯式的計數公式)
對於 個頂點的簡單完全圖,其生成樹數目為 。單頂點的情形計數為一。對於兩部分大小為正整數 的完全二部圖,其計數為
該公式包括星圖和單邊圖;兩部分的大小均為正,是命題陳述的一部分。
定理 1.6.4
(正的加權樹分佈具有精確的邊邊際概率)
設 連通,且所有非自環邊的權重均為正實數。以與權重乘積成正比的概率選取一棵生成樹。設 為邊 的約化關聯列, 為約化拉普拉斯矩陣。則
對於自環,右端為零。這些邊邊際概率之和為 ,且每一個都介乎零與一之間。改變邊的方向不影響它們。
概念視角代數
一個多項式同時支持計數、靈敏度分析與隨機選取
單位權重用來計數,形式權重保留了哪些邊出現,正的數值權重則定義出一個概率分佈。行列式恆等式是這三種用法所共有的,但只有在後面的正性與連通性假設下,才會用到可逆性與概率意義下的除法。
下面的證明按這個次序進行:先證餘因子恆等式,再算兩個顯式圖族,最後處理概率分佈。
證明思路或證明
行列式展開挑出了樹的邊集
論證建立在一個長方形行列式展開之上。
引理 1.6.5
(柯西–比內(Cauchy–Binet)展開)
設 是 矩陣, 是 矩陣,則
其中 取遍 的 元子集;當 時和為空。
證明
(以列的多重線性證明)
設 是 行 列的矩陣, 是 行 列的矩陣,則由列的多重線性, 可按從 中有序選取 列的方式展開。含有重複下標的選取,其行列式為零。對於固定的由 個互不相同的下標構成的無序集合 ,由行列式的帶符號置換公式,對它們所有排列求和恰好等於 。因此
若 ,則沒有互不相同的選取,和為零。當 時恰有空選取一種,兩邊均為一。這就直接證明了所需的柯西–比內恆等式。
證明
(主餘因子公式的證明)
將柯西–比內展開應用於 與 。對每個由 條帶標號的邊構成的集合 ,把所選的對角因子從行列式中提出,得到
下面證明:該行列式的平方恰好在 為生成樹時等於一,否則等於零。
若 含有自環,則其關聯列為零。若它含有圈,則沿該圈繞行,並按繞行方向選取符號,把該圈上各邊帶方向的關聯列相加,每個頂點的貢獻都相互抵消,從而得到一個非平凡的線性相關關係。這也包括帶有適當符號的兩條平行邊。刪去一行關聯矩陣後該相關關係仍然保持,所以所選子矩陣的行列式為零。
若 無圈,則它是森林。一個有 個頂點、 個連通分支的森林有 條邊,這可由對各分支(包括孤立頂點)內的樹的邊數求和得到。這裏 迫使 ,所以它是生成樹。
對於樹,我們對 用歸納法證明行列式的絕對值為一。 的情形是空行列式。對於 ,樹有一片不同於所選根的葉:取一條最長路徑的兩個端點,其中至少有一個不是該根。該葉的約化關聯行恰有一個非零元,等於正一或負一。沿該行展開,行列式在相差一個符號的意義下化為去掉該葉及其邊之後的樹的約化關聯行列式。再由歸納法即完成論證。代入這些取值為零或一的係數,公式即得證。
證明透視
行列式是在挑選關聯約束的基
三個要素各有分工。柯西–比內展開把 化為對所有 邊集合的求和,每項帶權 ;正因為子式取平方,定向的符號永遠無關緊要。圈的論證負責剔除非樹:圈給出關聯列之間帶符號的線性相關,刪去根所在的行後仍然成立,所以含圈或含自環的集合貢獻為零。森林計數保證大小為 的無圈集合連通,因此留下的只有生成樹。
隨後,葉的展開把每個保留下來的係數固定為一,使論證收尾。這裏刪去根行是關鍵:樹的完整關聯矩陣是 的,並非方陣;而 時總有一片不同於根的葉。若不刪去根, 是奇異矩陣,常見錯誤中的反例正說明這一點。
不枚舉樹而計算兩個重要的圖族
兩個顯式圖族還需要一個行列式事實。
引理 1.6.6
(秩一行列式更新)
對於可逆方陣 與列向量 ,
證明
(展開擾動單位矩陣的證明)
為證明它,先提出因子 ,再按列的多重線性展開 。在兩列中都選取所加向量的項為零,因為這兩列成比例。一列都不選的項為一;只在一列中選取的項之和為 。這就證明了該事實,按空向量的自然約定,階數為零的情形也包括在內。
證明
(兩個顯式計數的證明)
對於 ,約化拉普拉斯矩陣為 階的 ,其中 的每個元素都是一。由秩一恆等式,其行列式為 。該論證在 時同樣成立;單頂點的情形已另行定義過。
對於 ,在大小為 的那一部分中刪去一個根。對角塊為 與 ,非對角塊是元素全為負一的矩陣。用第一個塊的行的適當倍數去消去左下角的塊;這些行加法不改變行列式。下方的對角塊變為
其行列式為 。再乘以 ,即得所述結果。當 時,第二個塊為空,同一表達式的值為一;這裏並不需要對大小為空的正的那一部分求逆。
正權重把多項式變為概率分佈
證明
(邊際概率公式的證明)
對於約化向量 ,在其根座標處插入零,得到完整向量 。則
在非自環邊權重為正時,只有當 沿每條邊都取常值,這個量才為零。連通性與根處座標為零迫使 。因此對於 , 是正定的,從而可逆;單頂點的空矩陣按慣常約定有空逆矩陣。
生成樹多項式對每個單獨的權重都是線性的。因此 是包含 的所有樹的權重之和。在矩陣一側,僅將 改變 ,會使 改變 。由秩一行列式公式,其導數為 。把這兩個相等的導數除以正的歸一化多項式,就得到邊邊際概率公式。
每棵樹恰有 條邊,所以把各邊的邊際示性量相加,即得所斷言的和,而無需假設邊之間相互獨立。自環的關聯列為零,從不進入任何樹;把一條邊反向會使它的列在兩處同時變號,結果不變。
區分算法計算與恆等式
構造拉普拉斯矩陣需要對邊做線性次數的累加,在稠密實現中需要二次的矩陣儲存。行列式可以用消元法以三次的算術運算量求出,需要時選取非零的行主元。在權重為正時,約化矩陣是正定的,所以精確消元的對角主元非零。這些是關於算術運算次數的陳述;任意有理數輸入的長度以及精確分數的增長需要另行做位元計量,浮點計算的可靠性則需要進一步分析。
該公式還給出了一個直接的多項式恆等式,無需數值行列式算法也有用。對於一條非自環邊,把樹分成不含它的和含有它的兩類。收縮這條帶標號的邊,給出後一類與收縮後的多重圖的生成樹之間的雙射,其餘所選的邊保持不變。因此 。收縮可能產生自環與平行邊,它們仍沿用前面已述的約定。自環則直接忽略。
例題詳解
例題 1.6.7
(加權三角形記錄了全部三種刪除方式)
給三角形的三條邊賦予權重 。其生成樹多項式為 。刪去邊 所共有的那個頂點,得到約化矩陣,其對角元為 ,非對角元為 。其行列式為 。
在單位權重下有三棵樹,每條邊的包含概率都是三分之二。在權重 時,歸一化常數為五,權重為二的那條邊出現的概率為五分之四。較大的權重改變的是分佈,而不是產生了四個互不相同的帶標號副本。
例題 1.6.8
(平行邊的選擇相乘,而自環沒有貢獻)
取頂點 ,在 之間有權重分別為二和三的兩條平行邊,在 之間有一條權重為五的邊。在 處再加一個任意權重的自環。每棵樹都使用通向 的橋,並恰好使用兩條平行邊中的一條,所以其多項式的值為 。
以 為根,得到對角的約化矩陣,其元素為五和五。橋的邊際概率為一;兩條平行邊的邊際概率分別為五分之二和五分之三;自環的邊際概率為零。它們的和為二,恰好等於每棵生成樹的邊數。
例題 1.6.9
(兩個圖族給出不同量級的計數)
五個頂點的完全圖有 棵生成樹。兩部分大小分別為二和三的完全二部圖有 棵。
對於後者,以大小為三的那部分中的頂點為根,得到對角塊 以及元素全為負一的非對角塊。消元後下方的塊為 ,其行列式為 ;第一個塊貢獻九,從而得到十二。這個小計算展示了分塊消元的過程,而不只是引用封閉公式。
常見錯誤
反例模式
即使圖是連通的,完整拉普拉斯矩陣的行列式也為零
每個關聯列的元素之和為零,所以全一向量屬於完整拉普拉斯矩陣的核。對於單邊圖,拉普拉斯矩陣的對角元為一,非對角元為負一;其行列式為零,儘管恰有一棵生成樹。刪去一個根所在的行與列,得到元素為一的一階矩陣,這才是所需的餘因子。
常見錯誤
(把自環權重放到對角線上)
自環的關聯列為零,所以它對 沒有貢獻,也從不屬於生成樹。若把它的權重加到對角元上,餘因子就會改變:在以 為根的平行邊例子中,若在 放一個權重為 的自環並計入對角線,行列式會由 變為 ,而生成樹並沒有改變。
常見錯誤
(合併帶標號的平行邊)
平行邊是不同的帶標號邊,給出不同的生成樹。在平行邊例子中,把權重為 與 的兩條邊換成一條權重為 的邊,會得到 而不是 。只有合併後的邊帶有總權重 ,生成計數才保持不變;即使如此,兩條邊各自的邊際概率 與 也會丟失。
常見錯誤
(把邊際概率當作獨立包含)
邊際概率之和為 ,但樹的邊一般是相依的。在單位權重的四圈中,每條邊的概率都是 ,四條邊卻從不同時出現;若各邊獨立包含,四條邊同時出現的概率將是正數 。逆矩陣公式也需要圖連通:若 不連通且 ,則 , 奇異,根本沒有可歸一化的分佈。
總結
關聯矩陣的子式把拉普拉斯矩陣的一個餘因子變成完整的加權生成樹多項式。含圈的項消失,樹對應的子式的行列式絕對值為一。秩一與分塊消元給出了完全圖與完全二部圖的顯式計數,而正權重則給出精確的邊邊際概率,並清楚地區分了多項式恆等式與基於逆矩陣的概率計算。
練習
快速檢查
(求四圈的生成樹數目,以及在單位權重下每條邊的包含概率。檢驗邊際概率之和。)
每棵樹恰好省去圈上的一條邊。
解答 · 答案
刪去四條圈邊中的任意一條,都剩下一條生成路徑,所以共有四棵樹。每條指定的邊被其中一棵樹省去,被其餘三棵樹包含,邊際概率為 。這四個邊際概率之和為三,等於四個頂點時的 。這些邊並不獨立:它們同時被包含是不可能的,因為整個圈不是樹。
快速檢查
(對單位權重三角形的一條邊應用刪除–收縮。解釋為甚麼收縮後的圖有兩條帶標號的平行邊,以及它們的數目如何貢獻到計數中。)
收縮之後要保留多重圖中邊的身份。
解答
刪去所選的三角形的邊,剩下一條生成路徑,貢獻一。收縮它則得到由兩條不同的帶標號平行邊連接的兩個頂點。其中任意一條單邊都是該多重圖的生成樹,貢獻二。因此刪除–收縮給出 。
若把這些平行邊合併成一條不帶權的邊,則總共會錯誤地得到二。若把它們合併成一條權重為二的邊,則就此目的而言可以保持生成計數,但需要理解這會丟失各自獨立的邊際概率身份。
快速檢查
(計算 的生成樹數目,以及四個頂點的完全圖的生成樹數目。解釋為甚麼第一個圖的邊際概率全為一。)
星圖只有一棵可能的生成樹。
解答 · 答案
二部圖公式給出 。星圖的七條邊中每一條都是橋,都屬於那唯一的樹,所以七個邊際概率都等於一,和為七。對於四個頂點的完全圖,公式給出 。它多出的圈帶來了更多選擇;這兩個公式是在不同的外圍圖中數樹,而不只是使用了相同的頂點數。