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

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

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

e2

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

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

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

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

x1+x2+

x3=2

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