運籌學圖與網(wǎng)絡分析(編輯修改稿)
2025-06-19 22:12 本頁面
【文章內(nèi)容簡介】 用破圈法求出下圖的一個生成樹。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 v2 v3 v4 v5 e2 e4 e6 e8 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 （二） 避圈法：開始選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構成圈的邊，重復這個過程，直到不能進行為止。 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 根據(jù)破圈法和避圈法兩種方式得到了圖的兩個不同的生成樹，由此可以看到連通圖的生成樹不是唯一的。 最小生成樹問題 一棵生成樹所有樹枝上權的總和為這個生成樹的權 。 具有最小權的生成樹 ， 稱為最小生成樹 。 求賦權圖 G的最小支撐樹的方法也有兩種 ， “ 破圈法 ” 和 “ 避圈法 ” 。 破圈法 ：在原圖中 ， 任選一個圈 ， 從圈中去掉權最大 的一條邊 。 在余下的圖中重復這個步驟 ，直到得到一不含圈的圖為止 。 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 總造價 =1+4+9+3+17+23=57 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 避圈法 ：開始選一條 權最小 的邊 ， 以后每一步中 ，總從未被選取的邊中選一條權盡可能小 ， 且與已選邊不構成圈的邊 。 某六個城市之間的道路網(wǎng)如圖 所示 ， 要求沿著已知長度的道路聯(lián)結六個城市的電話線網(wǎng) ， 使電話線的總長度最短 。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 最短路的一般提法為：設 為連通圖 ，圖中各邊 有權 （ 表示 之間沒有邊 ） ， 為圖中任意兩點 ， 求一條路 ， 使它從 到 的所有路中總權最短 。 即： 最小 。 ),( EVG ?jil ???jilts vv , ?sv),( ji vv ji vv ,tv ?????),()(ji vvjilL(一 )、狄克斯徹 (Dijkstra)算法 適用于 wij≥ 0， 給出了從 vs到任意一個點 vj的最短路 。 三 、最短路問題 算法步驟： vs以 P標號 ，這表示從 vs到 vs的最短距離為 0，其余節(jié)點均給 T標號， 。 vi為剛得到 P標號的點，考慮點 vj， 其中 ，且 vj為 T標號。對 vj的 T標號進行如下修改： T標號的節(jié)點，把最小者改為 P標號，即： 當存在兩個以上最小者時 ， 可同時改為 P標號 。 若全部節(jié)點均為 P標號則停止 ， 否則用 代替 vi， 返回步驟 （ 2） 。 0)( ?svP???)( ivTEvv ji ?),(])(,)(m i n [)( ijijj lvPvTvT ??)](m in [)( ii vTvP ?iv例一：用 Dijkstra算法求下圖從 v1到 v6的最短路。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解： （ 1） 首先給 v1以 P標號 ， 給其余所有點 T標號 。 0)( 1 ?vP )6,3,2()( ????? ivT i（ 2） （ 3） 3]30,m i n [])(,)(m i n [)( 12122 ??????? lvPvTvT5]50,m i n [])(,)(m i n [)( 13133 ??????? lvPvTvT3)( 2 ?vP（ 4） 4]13,5m i n [])(,)(m i n [)( 23233 ????? lvPvTvT5]23,m i n [])(,)(m i n [)( 24244 ??????? l
高考資料相關推薦
鄂ICP備17016276號-1