運籌學(xué)課件：五章1-圖的基本概念最小支撐樹-TJF

1、圖與網(wǎng)絡(luò)分析我們身處在相互聯(lián)系、不可避免的網(wǎng)絡(luò)世界中，無論是那些直接影響我們的，還是間接影響我們的網(wǎng)絡(luò)體系。 Martin Luther King Jr.圖與網(wǎng)絡(luò)分析問題提出哥尼斯堡七橋問題應(yīng)用：道路交通網(wǎng)絡(luò)、生產(chǎn)流程、煤氣管道鋪設(shè)、郵遞員問題等。哥尼斯堡七橋問題在圖中找一條經(jīng)過每邊一次且僅一次的路歐拉回路?！爸袊]路問題”管梅谷（1962年）提出一個郵遞員，負責(zé)某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？在圖中找一條經(jīng)過每邊的最短路類似帶權(quán)的歐拉回路。245563344494“出行問題”-從天大到大悅城前沿：復(fù)雜網(wǎng)絡(luò)研究

2、小世界實驗Milgram小世界實驗：通過信件傳遞發(fā)現(xiàn)世界上任意兩個人平均距離是6前沿：復(fù)雜網(wǎng)絡(luò)研究小世界實驗Kevin Bacon（凱文貝肯）游戲：任意一個演員和Bacon一起演過電影，則其Bacon數(shù)為1。平均Bacon數(shù)為2.944。周星馳的Bacon數(shù)為3：周星馳豪門夜宴與洪金寶合作，洪金寶死亡游戲與Colleen Camp合作， Colleen Camp在陷阱中與Bacon合作?；旌萌R塢且活躍在銀屏上的各國影人，或不怎么混好萊塢但有一定資歷的外國影人，Bacon number多為12。Brad Pitt（布拉德皮特）：1Denzel Washington（丹澤爾華盛頓）：2Takesh

3、i Kitano（黑澤明）：2Yun-Fat Chow（周潤發(fā)）：2Zhang Ziyi（章子怡）：2用圖表示比賽情況有A、B、C、D、E五支球隊，他們之間的比賽情況可以用圖表示出來。已知A隊和其他各隊都比賽過一次，B隊和A、C隊比賽過，D隊和E、C隊比賽過，E隊和A、D隊比賽過。該如何表示？用圖表示比賽情況如果在比賽中：A勝E，B勝C，A勝D，C勝A，E勝D，A勝B，該如何表示？2022/7/26 第一節(jié) 圖的基本概念1 . 圖與子圖e1e2e3e5e6e4e7v3v2v1v4如 G：圖是由一些點和一些點之間的聯(lián)線（帶箭頭或不帶箭頭）所組成。記作G=(V，E)或D =(V，A) ，其中V=(

4、v1，v2，vn)表示點的集合，E=(e1，e2，em) 為邊的集合， A=(a1，a2，am) 為弧的集合。2022/7/26 第一節(jié) 圖的基本概念1 . 圖與子圖e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：2022/7/26 第一節(jié) 圖的基本概念2 . 簡單圖一個結(jié)點對包含多條邊，稱為多重邊。簡單圖：無環(huán)、無多重邊的圖。否則稱為多重圖。2022/7/263 . 關(guān)聯(lián)與相鄰4 . 鏈與圈2022/7/265. 有向圖與無向圖，圈，回路比較：2022/7/266. 樹 例1 已知有5個城市，要在它們之間架設(shè)電話線網(wǎng)，要求任2城市都可通話（允許通

5、過其它城市），并且電話線的根數(shù)最少。v1v2v3v5v4 特點：連通、無圈。樹無圈的連通圖，記為T。2022/7/26v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈； （2）在樹中任去掉1邊，則不連通； （3）在樹中不相鄰2點間添1邊，恰成1圈； （4）若樹T有m個頂點，則T有m-1條邊。2022/7/267.圖的部分（支撐）樹 若圖G=（V，E）的子圖T=（V，E）是樹，則稱T為G的部分樹或支撐樹。特點邊少、點不少。性質(zhì)：G連通，則G必有部分樹。2022/7/26第二節(jié) 網(wǎng)絡(luò)分析網(wǎng)絡(luò)賦權(quán)圖，記D=（V，E，C），其中C=c1，cn， ci為邊ei上的權(quán)（設(shè)ci ）。網(wǎng)絡(luò)分析主要

6、內(nèi)容最小部分樹、最短路、最大流。2022/7/26一. 最小部分（支撐）樹問題問題：求網(wǎng)絡(luò)D的部分樹，使其權(quán)和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如圖網(wǎng)絡(luò)的最小部分樹。v5v1v3v6v4v2v72552335757112022/7/26避圈法是一種選邊的過程，其步驟如下：1. 從網(wǎng)絡(luò)D中任選一點vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊vi，vj，得第二個頂點vj；2. 把頂點集V分為互補的兩部分V1, 1 ，其中2022/7/26用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分樹如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？見圈就破，去掉其中權(quán)最大的。避圈法-例32022/7/2614321672253用避圈法求解一下問題的最小樹：2022/7/26143216722531432167225314321672253與邊相關(guān)聯(lián)的點2022/7/261432