算法合集之生成樹的計數(shù)及其應(yīng)用

算法合集之生成樹的計數(shù)及其應(yīng)用第1頁，課件共31頁，創(chuàng)作于2023年2月引入最?。ù螅┥蓸渥钚。ù螅┒认拗粕蓸渥顑?yōu)比率生成樹……生成樹生成樹的計數(shù)第2頁，課件共31頁，創(chuàng)作于2023年2月[例一]高速公路一個國家需要在n座城市之間建立通信網(wǎng)絡(luò)。某些城市之間可以鋪設(shè)通信線路。要求任意兩座城市之間恰好有一條通訊路線，試求方案個數(shù)。滿足：1≤n≤12。第3頁，課件共31頁，創(chuàng)作于2023年2月分析首先將問題抽象成圖論模型點：城市邊：通訊線路任意兩點之間恰好只有一條路徑這是一顆樹！問題轉(zhuǎn)化為：給定一個n個點的無向圖，其中無重邊和自環(huán)，試求其生成樹的個數(shù)。第4頁，課件共31頁，創(chuàng)作于2023年2月分析由于原題規(guī)模較小，因此我們可以使用一些復(fù)雜度較高的算法來解決它，如指數(shù)級的動態(tài)規(guī)劃算法。但是，如果規(guī)模更 一些呢？預(yù)備知識關(guān)聯(lián)矩陣、Kirchhoff矩陣大

第5頁，課件共31頁，創(chuàng)作于2023年2月圖的關(guān)聯(lián)矩陣對于無向圖G，我們定義它的關(guān)聯(lián)矩陣B是一個n*m的矩陣，并且滿足：如果ek=(vi，vj)，那么Bik和Bjk一個為1，另一個為-1，而第k列的其他元素均為0。圖G的關(guān)聯(lián)矩陣如右下角所示：v1v2v3圖Ge1e2e3v1v2v3e1

e2

e3第6頁，課件共31頁，創(chuàng)作于2023年2月圖的關(guān)聯(lián)矩陣圖的關(guān)聯(lián)矩陣有什么特殊的性質(zhì)呢？我們不妨來考察一下B和它的轉(zhuǎn)置矩陣BT的乘積。第7頁，課件共31頁，創(chuàng)作于2023年2月圖的關(guān)聯(lián)矩陣根據(jù)矩陣乘法的定義，我們可以得到：也就是說，BBTij是B第i行和第j行的內(nèi)積。因此，當i=j時，BBTij=vi的度數(shù)；而當i≠j時，如果存在邊(vi，vj)，那么BBTij=-1，否則BBTij=0。我們通常將BBT稱為圖的Kirchhoff矩陣。第8頁，課件共31頁，創(chuàng)作于2023年2月圖的Kirchhoff矩陣對于無向圖G，它的Kirchhoff矩陣C定義為它的度數(shù)矩陣D減去它的鄰接矩陣A。顯然，這樣的定義滿足剛才描述的性質(zhì)。有了Kirchhoff矩陣這個工具，我們可以引入Matrix-Tree定理：對于一個無向圖G，它的生成樹個數(shù)等于其Kirchhoff矩陣任何一個n-1階主子式的行列式的絕對值。所謂n-1階主子式，就是對于任意一個r，將C的第r行和第r列同時刪去后的新矩陣，用Cr表示。第9頁，課件共31頁，創(chuàng)作于2023年2月Matrix-Tree定理讓我們通過一個例子來解釋一下定理。如圖所示，G是一個由5個點組成的無向圖。它的Kirchhoff矩陣C為第10頁，課件共31頁，創(chuàng)作于2023年2月Matrix-Tree定理我們?nèi)=2，根據(jù)行列式的定義易知|detC2|

=11，這11顆生成樹如下圖所示。

這個定理看起來非常“神奇”，讓我們嘗試著去證明一下吧！第11頁，課件共31頁，創(chuàng)作于2023年2月定理的證明經(jīng)過分析，我們可以發(fā)現(xiàn)圖的Kirchhoff矩陣C具有一些有趣的性質(zhì)：C的行列式總是0。如果圖是不連通的，則C的任一個n-1階主子式的行列式均為0。如果圖是一顆樹，那么C的任一個n-1階主子式的行列式均為1。證明略。第12頁，課件共31頁，創(chuàng)作于2023年2月定理的證明我們知道，C=BBT，因此，我們可以把C的問題轉(zhuǎn)化到BBT上來。設(shè)Br為B去掉第r行得到的矩陣，容易知道Cr=BrBr

T。這時，根據(jù)Binet-Cauchy公式，我們可以將Cr的行列式展開。其中，是把Br中屬于x的列抽出后形成的新矩陣。第13頁，課件共31頁，創(chuàng)作于2023年2月定理的證明注意觀察上面的式子，實際上是圖Gx的Kirchhoff矩陣的一個n-1主子式。其中Gx是由所有的頂點和屬于x的邊組成的一個G的子圖。若屬于x的n-1條邊形成了一顆樹時，由Kirchhoff矩陣的性質(zhì)可知等于1。若屬于x的n-1條邊沒有形成樹，則Gx中將至少含有兩個連通塊，這時等于0。因此，我們認為：每次從邊集中選出n-1條邊，若它們形成了生成樹，則答案加1，否則不變。第14頁，課件共31頁，創(chuàng)作于2023年2月定理的理解當x取遍邊集所有大小為n-1的子集后，我們就可以得到原圖生成樹的個數(shù)。這樣我們成功證明了定理！剛才的證明過程看起來有些“深奧”，下面就讓我們從直觀上來理解一下這個定理的原理。第15頁，課件共31頁，創(chuàng)作于2023年2月定理的理解試求方程

x1+x2+

x3=2

所有非負整數(shù)解的個數(shù)。這是大家都很熟悉的一道組合計數(shù)問題。通常的解法是，設(shè)有2個1和兩個△，我們將這4個元素任意排列，那么不同的排列的個數(shù)就等于原方程解的個數(shù)，即。為什么要這樣做呢？第16頁，課件共31頁，創(chuàng)作于2023年2月定理的理解我們將所有6種排列列出后發(fā)現(xiàn)，一種排列就對應(yīng)了原方程的一個解：△△11對應(yīng)x1=0，x2=0，x3=2△1△1對應(yīng)x1=0，x2=1，x3=1△11△對應(yīng)x1=0，x2=2，x3=0……也就是說，我們通過模型的轉(zhuǎn)化，找出了原問題和新問題之間的對應(yīng)關(guān)系，并利用有關(guān)的數(shù)學知識解決了轉(zhuǎn)化后的新問題，也就同時解決了原問題。這種轉(zhuǎn)化的重要意義在于：在不同問題之間的架起了互相聯(lián)系的橋梁。第17頁，課件共31頁，創(chuàng)作于2023年2月定理的理解回到我們討論的Matrix-Tree定理上來。我們同樣是經(jīng)過模型的轉(zhuǎn)化后（將圖模型轉(zhuǎn)化為矩陣模型），發(fā)現(xiàn)Binet-Cauchy公式展開式中的每一項對應(yīng)著邊集一個大小為n-1的子集。其中，值為1的項對應(yīng)一顆生成樹，而沒有對應(yīng)生成樹的項值為0。這樣，將問題轉(zhuǎn)化為求展開式中所有項之和。再利用已有的數(shù)學知識，就可以成功解決這個問題。第18頁，課件共31頁，創(chuàng)作于2023年2月兩個問題的對比方程的解圖的生成樹類似排列方案展開式的項類似對應(yīng)對應(yīng)不同之處在于：相互之間的對應(yīng)關(guān)系更加隱蔽、復(fù)雜需要更加強大的數(shù)學理論來支撐第19頁，課件共31頁，創(chuàng)作于2023年2月定理的擴展利用該定理，我們可以容易得到著名的Cayley公式：完全圖Kn有nn-2顆生成樹。我們剛才只對圖中沒有重邊的情況進行了分析。實際上，圖中有重邊時該定理仍然成立，并且證明與沒有重邊的情況類似。該定理也可以擴展到有向圖上，用來計算有向圖的外向樹的個數(shù)。第20頁，課件共31頁，創(chuàng)作于2023年2月[例二]UVap10766OrganisingtheOrganisation[例三]國王的煩惱信息學競賽中的應(yīng)用第21頁，課件共31頁，創(chuàng)作于2023年2月[例三]國王的煩惱一個王國由n座城市組成。由于遭到了洪水的襲擊，許多道路都被沖毀了。國王組織了專家進行研究，列舉出了所有可以正常通行的道路。其中有的已經(jīng)被沖毀，需要重新修復(fù)；有的則可以繼續(xù)使用。并且所有可以繼續(xù)使用的道路沒有形成環(huán)。第22頁，課件共31頁，創(chuàng)作于2023年2月[例三]國王的煩惱國王希望修建最少的道路，使得任意兩個城市之間都能互達。請你計算可行方案的總數(shù)。下面我們通過一個例子來看一下。bacd如右圖所示，王國由a、b、c、d，4座城市組成其中藍色邊表示可以通行但需要修復(fù)的道路紅色邊表示可以繼續(xù)使用的道路共有2種方案，如右下角所示bacdbacd方案1方案2第23頁，課件共31頁，創(chuàng)作于2023年2月問題分析難點在于由于必選邊的存在，我們無法直接應(yīng)用Matrix-Tree定理我們知道，如果要求生成樹中必須包含某條邊e，那么，我們可以將e壓縮，將原圖的問題轉(zhuǎn)化到新圖上來。因此，我們需要1、將所有的必選邊壓縮2、求壓縮后的圖的生成樹的個數(shù)第24頁，課件共31頁，創(chuàng)作于2023年2月問題分析壓縮一條邊的時間復(fù)雜度為O(n)，而最多只要壓縮n-1條邊。因此，第一步的復(fù)雜度為O(n2)。計算一個圖的生成樹的個數(shù)的時間復(fù)雜度依賴于求其Kirchhoff矩陣行列式的時間復(fù)雜度，為O(n3)。因此，整個算法的時間復(fù)雜度為O(n3)。第25頁，課件共31頁，創(chuàng)作于2023年2月總結(jié)矩陣的行列式圖的生成樹模型轉(zhuǎn)化數(shù)學證明扎實的數(shù)學功底是解決問題的保證創(chuàng)造性的聯(lián)想則是解決問題的靈魂第26頁，課件共31頁，創(chuàng)作于2023年2月謝謝大家！第27頁，課件共31頁，創(chuàng)作于2023年2月Cayley公式的證明首先計算完全圖Kn的Kirchhoff矩陣的一個n-1階主子式C1[Kn]：下面我們對C1[Kn]進行化簡。第2至第n-1列均減掉第一列，得到如下的矩陣：第28頁，課件共31頁，創(chuàng)作于2023年2月Cayley公式的證明我們可以發(fā)現(xiàn)，除了第一列以外，其他每列都在第一行上有一個-n，在對角線上有一個n，而其他位置上的元素均為0?，F(xiàn)在，我們把第2至第n行都加到第一行上去，可以得到如下矩陣：第29頁，課件共31頁，創(chuàng)作于2023年2月Cayley公式的證明再次觀察這個矩陣，我們可以發(fā)現(xiàn)：在第一行上只有一個1，剩下部分中，只有對角線上的數(shù)字為n，其他元素都是0。因此，完全圖Kn的生成樹的個數(shù)為nn-2。第30頁，課件共31頁，創(chuàng)作于2023年2月SPOJp