圖與網(wǎng)絡(luò)規(guī)劃ppt課件(已修改)
2025-01-29 17:00 本頁面
【正文】 第 7章 圖與網(wǎng)絡(luò)規(guī)劃 圖的 基本概念 圖的基本概念 如果用節(jié)點(diǎn)來代表事物，用連接兩個(gè)節(jié)點(diǎn)之間的邊來表示事物之間的聯(lián)系，那么現(xiàn)實(shí)中的許多問題都可以用圖論的語言來描述。 如，互聯(lián)網(wǎng)，電話網(wǎng)，供應(yīng)鏈網(wǎng)絡(luò)，下水管道網(wǎng)絡(luò)，天然氣管道網(wǎng)絡(luò)，朋友之間的友誼網(wǎng)絡(luò)，親戚關(guān)系網(wǎng)絡(luò)等等 Powerlaw distribution Scalefree Network 舉例：群體中的朋友關(guān)系網(wǎng)絡(luò) 內(nèi)容框架 一、 圖的基本概念 （討論思路 ） G=（ V， E） 子圖 矩陣表示 含元素的個(gè)數(shù) 點(diǎn)的次 邊 特殊的圖 點(diǎn)邊關(guān)系 簡單圖 多重圖 空 圖 連通圖 樹 支撐樹 空 圖 G=(V,E) 矩陣表示 A 鄰接矩陣 B 關(guān)聯(lián)矩陣 C 割集矩陣 L 圈矩陣 M 可達(dá)矩陣 D 距離矩陣 邊 e=[u,v] 端點(diǎn) 重合 環(huán) 自回路 多重邊 平行邊 簡單圖 多重圖 含 點(diǎn)的次 0 1 奇數(shù) 偶數(shù) 子圖 真子圖 支撐子圖 導(dǎo)出子圖 孤立點(diǎn) 懸掛點(diǎn) 奇點(diǎn) 偶點(diǎn) 懸掛邊 頂點(diǎn)數(shù) p 邊數(shù) q 點(diǎn)邊關(guān)系 各種鏈的概念 點(diǎn)邊關(guān)系 真子圖 支撐子圖 導(dǎo)出子圖 各種鏈的概念 ???????????點(diǎn)）初等鏈（無重邊、無重簡單鏈（無重邊）初等回路簡單回路路）鏈、開鏈、閉鏈（即回點(diǎn)邊交替序列序列各種鏈的概念通路 樹 (6個(gè)等價(jià)定義 ) 連通圖 支撐樹 ?????弱連通（半道路連接）單側(cè)連通強(qiáng)連通有向 、無向 圖的概念 ： 圖 G(V, E)是頂點(diǎn)和邊的集合。 表示頂點(diǎn)的集合（節(jié)點(diǎn)集）； 表示邊的集合（邊集）。 { } ( 1 , 2 , , )iV v i
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1