運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析課件

運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析簡單圖運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析V1V4V3V2XY運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析 2 2、頂點(diǎn)的次、頂點(diǎn)的次 定義定義5 5：運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析初等鏈：初等鏈：鏈中無重復(fù)的點(diǎn)和邊；鏈中無重復(fù)的點(diǎn)和邊；初等圈：圈初等圈：圈中無重復(fù)的點(diǎn)和邊；中無重復(fù)的點(diǎn)和邊；運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析道路道路道路道路回路回路4528572111vevevevevQ 44322112vevevevQ 1956452113vevevevevQ 鏈鏈初等鏈初等鏈初等圈初等圈運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析連通圖：連通圖：圖中任意兩點(diǎn)之間均至少有一圖中任意兩點(diǎn)之間均至少有一條通路，否則稱為不連通圖。條通路，否則稱為不連通圖。運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析，運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析V1V3V5V6V4V2654321010000101010100010010010000100000110vvvvvvAv1 v2 v3 v4 v5 v6運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析v1v2v5v4v3924386745543210650760844580320430974290vvvvvA v1 v2 v3 v4 v5運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析v1v3v6v9v8v7v4v5v2v1v3v6v9v8v7v4v5v2343449545642343449545642運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析v1v3v6v9v8v7v4v5v2v1v3v6v9v8v7v4v5v2343449545642運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析v1v3v6v9v8v7v4v5v2再次調(diào)整的v1v3v6v9v8v7v4v5v26434524運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析 總結(jié)總結(jié): :圖的基本概念圖的基本概念子圖子圖矩陣表示矩陣表示含元素的個(gè)數(shù)含元素的個(gè)數(shù)點(diǎn)的次點(diǎn)的次邊邊特殊的圖特殊的圖點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系簡單圖簡單圖多重圖多重圖連通圖連通圖樹樹生成子圖生成子圖運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析G=(V,E) 鄰接矩陣鄰接矩陣 權(quán)矩陣權(quán)矩陣邊邊e=(u,v) 關(guān)聯(lián)邊關(guān)聯(lián)邊 端點(diǎn)端點(diǎn) 環(huán)環(huán)多重邊多重邊 多于多于1條邊條邊簡單圖簡單圖多重圖多重圖 0 1 奇數(shù)奇數(shù) 偶數(shù)偶數(shù) 子圖子圖孤孤立立點(diǎn)點(diǎn)懸懸掛掛點(diǎn)點(diǎn)奇奇點(diǎn)點(diǎn)偶偶點(diǎn)點(diǎn)懸掛邊懸掛邊頂點(diǎn)數(shù)頂點(diǎn)數(shù)n邊數(shù)邊數(shù)m點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系各種鏈的概念各種鏈的概念子子圖圖生成生成子圖子圖運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析初等鏈（無重復(fù)邊、無重復(fù)點(diǎn)的鏈)鏈、圈（即起點(diǎn)與終點(diǎn)同）點(diǎn)邊交替序列序列各種鏈的概念 （無向圖）初等圈（無重復(fù)邊、無重復(fù)點(diǎn)的圈)連通圖連通圖 點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系各種鏈的概念各種鏈的概念通路通路生成樹生成樹子子圖圖生成生成子圖子圖有向圖道路、回路經(jīng)過每邊一次且僅一次歐拉道路歐拉回路運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析 1.思考題思考題 子圖與生成子圖的區(qū)別是什么？子圖與生成子圖的區(qū)別是什么？ 2.討論題討論題 中國郵路問題的解題步驟？中國郵路問題的解題步驟？運(yùn)籌學(xué)教程運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析 小結(jié): 1.圖的基本知識。 2.圖的矩陣表示。 3.歐拉道路與歐拉回路。