運籌學(xué)第九章-全文預(yù)覽
【正文】 j )的權(quán)為 dij ,則網(wǎng)絡(luò)的生成樹的權(quán)為生成樹的各邊的權(quán)的和 . C O D A B 10 4 5 6 C O D A B 4 10 4 9 5 8 6 13 C O D A B 4 9 5 6 C O D A B 4 10 4 5 6 （一）避圈法 （ Kruskal） 思想：在圖中取一條最小權(quán)的邊，以后每一步中，總 從未被選取的邊中選一條權(quán)最小的邊，并使 之與已選取的邊不構(gòu)成圈（每一步中，如果有 兩條或兩條以上的邊都是最小權(quán)的邊，則從中 任選一條）。 （一） 破圈法 （二） 避圈法 在圖中任取一條邊 e1，找一條與 e1不構(gòu)成圈的邊 e2，再找一條與 {e1， e2}不構(gòu)成圈的邊 e3。 定理 圖 G有生成樹的充分必要條件是圖 G是連通的。 邊數(shù) =點數(shù) 1 定義： 無圈的連通圖稱為樹。 第九章 降低管道網(wǎng)絡(luò)成本的最小樹方法 第一節(jié) 引 例 C O D A B 4 10 4 9 5 8 6 13 O: 鍋爐房 。 樹 T=（ V， E）， p=n， q=m， 則 m=n1。 v1 v3 v2 v4 v5 v6 （ a） v3 v1 v2 v4 v5 v6 （ b） （ b）是（ a）的一個生成樹。 現(xiàn)設(shè) G含圖，從圈中任意去掉一條邊，得 G的
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1