算法合集之生成樹的計數(shù)及其應(yīng)用-資料下載頁
2025-10-07 20:33本頁面
【正文】 向圖上，用來計算有向圖的外向樹的個數(shù)。 ?[例二 ] UVa p10766 Organising the Organisation ?[例三 ] 國王的煩惱 信息學(xué)競賽中的應(yīng)用 [例三 ]國王的煩惱 ?一個王國由 n座城市組成。 ?由于遭到了洪水的襲擊，許多道路都被沖毀了。 ?國王組織了專家進(jìn)行研究，列舉出了所有可以正常通行的道路。其中有的已經(jīng)被沖毀，需要重新修復(fù)；有的則可以繼續(xù)使用。并且所有可以繼續(xù)使用的道路 沒有形成環(huán) 。 [例三 ]國王的煩惱 ?國王希望修建最少的道路，使得任意兩個城市之間都能互達(dá)。 ?請你計算可行方案的總數(shù)。 ?下面我們通過一個例子來看一下。 b a c d 如右圖所示，王國由a、 b、 c、 d， 4座城市組成 其中 –藍(lán)色邊表示可以通行但需要修復(fù)的道路 –紅色 邊表示可以繼續(xù)使用的道路 ?共有 2種方案，如右下角所示 b a c d b a c d 方案 1 方案 2 問題分析 ?難點在于 –由于 必選邊 的存在，我們無法直接應(yīng)用MatrixTree定理 ?我們知道，如果要求生成樹中必須包含某條邊 e，那么，我們可以將 e壓縮，將原圖的問題轉(zhuǎn)化到新圖上來。 ?因此，我們需要 將所有的必選邊壓縮 求壓縮后的圖的生成樹的個數(shù) 問題分析 ?壓縮一條邊的時間復(fù)雜度為 O(n)，而最多只要壓縮 n1條邊。因此，第一步的復(fù)雜度為 O(n2)。 ?計算一個圖的生成樹的個數(shù)的時間復(fù)雜度依賴于求其 Kirchhoff矩陣行列式的時間復(fù)雜度，為 O(n3)。 ?因此，整個算法的時間復(fù)雜度為 O(n3)。 總結(jié) 矩陣的行列式 圖的生成樹 模型轉(zhuǎn)化 數(shù)學(xué)證明 扎實的數(shù)學(xué)功底是解決問題的保證 創(chuàng)造性的聯(lián)想則是解決問題的靈魂
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1