運(yùn)籌學(xué)基礎(chǔ)圖論方法(1)-展示頁(yè)
2025-05-26 22:18本頁(yè)面
【正文】 靈丘 原平 天津 塘沽 通縣 秦皇島 密云 承德 北京 張家口 懷柔 甲 乙 丙 丁 戊 圖的最基本的要素是點(diǎn)以及點(diǎn)與點(diǎn)之間的一些連線， 點(diǎn) 表示我們要研究的對(duì)象 ， 線 表示對(duì)象之間的某種 特定關(guān)系 。 圖的基本概念與模型 圖是反映研究對(duì)象之間相互關(guān)系的一種工具。 【 引例 2】 某河流中有幾個(gè)島嶼，從兩岸至各島嶼及島嶼之間的橋梁如圖。nigsberg城郊的 Pregerl河上有兩個(gè)小島，小島和河兩岸的陸地由 7座橋相連（如圖 a），問(wèn)題是如何從河岸或島上的某一個(gè)位置出發(fā)，能否經(jīng)過(guò) 7座橋正好各一次，最后回到出發(fā)地。第六章 圖論方法 【 引例 1】 K246。nigsberg七橋問(wèn)題 在 K246。 將圖抽象，用 4個(gè)點(diǎn)代表 4個(gè)被河隔開(kāi)的陸地（兩岸和島嶼），把橋表示為連接兩個(gè)陸地之間的邊，則得到圖 b所示的圖，從而問(wèn)題變?yōu)槿绾螐膱D中的某個(gè)點(diǎn)出發(fā)，經(jīng)過(guò)所有的邊正好一次，最后回到這個(gè)點(diǎn)。在一次軍事行動(dòng)中，問(wèn)至少炸斷幾座橋，才能完全切斷 A與 F的交通聯(lián)系？ A D B C D EF A F D E C B 2 1 3 1 2 1 2 1 1 167。是在紙上用點(diǎn)和線畫(huà)出的各種各樣的示意圖。 如圖中 點(diǎn) 和 線 賦與具體的含義和權(quán)重，稱(chēng)為網(wǎng)絡(luò)圖。如 e1=[v1, v2], v1, v2稱(chēng)為 e1的端點(diǎn) ， e1稱(chēng)為 v1,v2的關(guān)聯(lián)邊， v1,v2稱(chēng)為點(diǎn) 相鄰 ， e1,e2稱(chēng)為邊相鄰 v1 e1 v2 v3 v4 v5 v6 e2 e3 e4 e5 e6 e7 e8 e9 e10 環(huán) ：如果邊的兩個(gè)端點(diǎn)相重，稱(chēng)該邊為 環(huán) ，如 e10；如果兩個(gè)端點(diǎn)之間的邊多于一條 , 稱(chēng)為具有 多重邊 ，如 [v2, v4] ,無(wú)環(huán)，無(wú)多重邊的圖為簡(jiǎn)單圖 。 圖的名詞和基本概念 圈 ：若起始點(diǎn)和終點(diǎn)是同一個(gè)點(diǎn)的鏈稱(chēng)為圈。 v1 e1 v2 v3 v4 v5 v6 e2 e3 e4 e5 e6 e7 e8 e9 e10 鏈 ：是一個(gè)點(diǎn)、邊交錯(cuò)序列 , 如 （ v1 ,e1 ,v2 ,e2 ,v4 ) 路 ：如果鏈中每個(gè)項(xiàng)點(diǎn)都不相同 , 則稱(chēng)為路，如 （ v1 ,e1 ,v2 ,e2 ,v4 ) 回路 ：若起始點(diǎn)和終點(diǎn)是同一個(gè)點(diǎn)的路稱(chēng)為回路。否則稱(chēng)為 不連通的 。打?qū)μ?hào)的是各運(yùn)動(dòng)員參加比賽的項(xiàng)目，問(wèn)六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。 樹(shù)圖和圖的最小部分樹(shù) 一、樹(shù)的性質(zhì) 例如 性質(zhì) 1：任何樹(shù)至少有一個(gè)懸掛節(jié)點(diǎn) 性質(zhì) 2：具有 n個(gè)頂點(diǎn)的樹(shù)的邊恰好為 (n1)條 性質(zhì) 3：任何具有 n個(gè)頂點(diǎn)、 (n1)條邊的連通圖是樹(shù)圖。 例：樹(shù)的形成 已知在五個(gè)城市間架設(shè)電話(huà)線，要求任何兩個(gè)城市都可以通話(huà)（允許通過(guò)其它城市），并且電話(huà)線的條數(shù)最少。 求圖的 最小樹(shù)杈問(wèn)題 的方法有 “破圈法” 和 “避圈法” 。 此為最小樹(shù)杈 v1 v2 v3 v4 v5 25 20 10 9 15 12 30 破圈法： 任選一個(gè)圈，從圈中去掉杈最大的一條邊 。 最小線路長(zhǎng)度為： 20+15+10+9=54 避圈法 (普賴(lài)姆法 ) 避圈法： 從任意一個(gè)節(jié)點(diǎn)開(kāi)始，選一條杈 較小的邊連接 ，以后每一步中，總從未被選取的邊中選一條杈盡可能小，且與已選邊不構(gòu)成圈的邊。求最小線路。 最短線路問(wèn)題 當(dāng)通過(guò)網(wǎng)絡(luò)的各邊所需時(shí)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1