算法合集之平面圖在信息學(xué)中的應(yīng)用-文庫(kù)吧資料
2024-10-22 20:30本頁(yè)面
【正文】 算法二 枚舉一條邊，再枚舉第三個(gè)頂點(diǎn)，判斷是否與邊上的兩個(gè)端點(diǎn)相鄰。） ? 若 C[u]≠0，則 (C[u]， L) ? C[u]← L ?O(NlogN) ?O(N) ?O(Ymax) 總計(jì) ： O(NYmax) 時(shí)間性能分析 如何建立圖 G？ 應(yīng)用 例 1:水平可見(jiàn)線段 (CEPC2021) ? 算法二 – 定義線段樹(shù) T： ? 設(shè)節(jié)點(diǎn) N描述區(qū)間 [a,b]的覆蓋情況 0 (無(wú)線段覆蓋 [a,b]) ? 則 = L (線段 L完全覆蓋 [a,b]) 1 (其他情形 ) – 線段樹(shù)的存儲(chǔ)： 使用完全二叉樹(shù)的數(shù)組結(jié)構(gòu)，可以免去復(fù)雜的指針運(yùn)算和不必要的空間浪費(fèi)。..2y39。39。（坐標(biāo)值為 0到 8000的整數(shù)） 應(yīng)用 例 1:水平可見(jiàn)線段 (CEPC2021) 分析 ? 把線段看成點(diǎn) ? 若兩條線段水平可見(jiàn)，則在對(duì)應(yīng)兩點(diǎn)之間連一條邊，建立無(wú)向圖 G ? 統(tǒng)計(jì) G中的三角形的數(shù)目 應(yīng)用 例 1:水平可見(jiàn)線段 (CEPC2021) ? 算法一 – 設(shè)數(shù)組 C[I]（ I=0..2Ymax）， C[2y]表示覆蓋 y點(diǎn)的最后一條線段， C[2y+1]表示覆蓋區(qū)間 (y,y+1)的最后一條線段 – 把線段按從左到右的順序排序 – 依次檢查每一條線段 L(L=[y39。三條兩兩“水平可見(jiàn)”的線段構(gòu)成一個(gè)“三元組”。 相關(guān)定義、定理及推論 ? 定理 1：若 G=V， E， F是連通平面圖，則 ∑f∈ Fd(f)=2|E|. ? 定理 2：若 G=V， E， F是連通平面圖，則 |V||E|+|F|=2. 證明： 首先假定 G是樹(shù)，則 |E|=|V|1， G只有一個(gè)無(wú)限面， 因此 |V||E|+|F|=|V|(|V|1)+1=2. 現(xiàn)在假設(shè) G不是樹(shù)，由于 G是連通的，故 G中至少存在一個(gè)基本圈 C，于是 G必有一個(gè)有限面 f，而 f的邊界是由基本圈 C及可能連同計(jì)算兩次的一些邊組成 .如果從 G中刪去基本圈 C上的一條邊后得到的平面圖 G1=V1， E1， F1，則 |V1|=|V|， |E1|=|E|1，|F1|=|F|1，故 |V1||E1|+|F1|=|V||E|+|F|，仿此做下去，最終得到 G的一棵
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1