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