【正文】 圖，各邊的聯(lián)接可表示為 e1=( v2 , v1 )， … e6=( v1 , v4 ) 圓 括號表示 有序偶對 ， 尖 括號表示 無序偶對 。1 課程設(shè)置目的 該門課在工程應(yīng)用中的重要性 1）礦井設(shè)計 2）礦井改擴(kuò)建 3）通風(fēng)系統(tǒng)調(diào)整 4）礦井災(zāi)害防治（瓦斯、火） 1）風(fēng)量分配與調(diào)整 2）風(fēng)流方向判斷 3）通風(fēng)設(shè)施合理位置的選擇 4）災(zāi)害煙氣蔓延與避災(zāi)路線的選擇 2 系統(tǒng)規(guī)劃 → 系統(tǒng)合并 —— 單一風(fēng)井工作 3 授課計劃 0 緒論 1 圖論基礎(chǔ) 圖的基本概念 圖的矩陣表示 生成樹選擇 2 礦井通風(fēng)網(wǎng)絡(luò) 礦井通風(fēng)網(wǎng)絡(luò)圖 礦井通風(fēng)網(wǎng)絡(luò)內(nèi)風(fēng)流變化的規(guī)律 通風(fēng)網(wǎng)絡(luò)分析與數(shù)學(xué)模型 實驗 4 授課計劃 3 通風(fēng)機(jī)運(yùn)轉(zhuǎn)特性及分析 扇風(fēng)機(jī)特性的數(shù)學(xué)描述 扇風(fēng)機(jī)工況點(diǎn)求解與分析 用計算機(jī)進(jìn)行扇風(fēng)機(jī)優(yōu)選 4 復(fù)雜通風(fēng)網(wǎng)絡(luò)自然分風(fēng)電算 復(fù)雜通風(fēng)網(wǎng)絡(luò)解算概述 回路法解算復(fù)雜風(fēng)網(wǎng) 節(jié)點(diǎn)法與割集法解算復(fù)雜風(fēng)網(wǎng) 風(fēng)網(wǎng)自然分風(fēng)算法評述 復(fù)雜風(fēng)網(wǎng)自然分風(fēng)電算程序?qū)嵗? 實驗 5 授課計劃 5 通風(fēng)網(wǎng)絡(luò)中風(fēng)流調(diào)節(jié)的計算方法 概述 獨(dú)立回路法 道路法 6 礦井通風(fēng)網(wǎng)絡(luò)優(yōu)化 礦井通風(fēng)網(wǎng)絡(luò)優(yōu)化概述 通風(fēng)網(wǎng)絡(luò)調(diào)節(jié)優(yōu)化 通風(fēng)中風(fēng)量分配的優(yōu)化 礦井通風(fēng)系統(tǒng)優(yōu)化設(shè)計簡介 6 授課計劃 7 網(wǎng)絡(luò)理論在礦井通風(fēng)中的應(yīng)用 在通風(fēng)設(shè)計中的應(yīng)用 在通風(fēng)管理中的應(yīng)用 8 礦井火災(zāi)的通風(fēng)網(wǎng)絡(luò)解析 礦井火災(zāi)時期風(fēng)流狀態(tài)的變化規(guī)律 礦井火災(zāi)時的通風(fēng)模擬 礦井火災(zāi)時風(fēng)流控制 礦井通風(fēng)模擬軟件示例 實驗 7 1 圖論基礎(chǔ) 圖的概念 — 圖的定義 頂點(diǎn)或 節(jié)點(diǎn) 邊 或分支 圖的 偶對表示 : 圖 → G G(V,E) 節(jié)點(diǎn) → V V(v1,v2, … vm) 節(jié)點(diǎn)集 m=|V| → 節(jié)點(diǎn)數(shù) 邊 → E E(e1,e2, … em) 邊集 n=|E| → 邊數(shù) 1）圖的定義 指某類 具體事物 和這些 事物間聯(lián)系 的抽象描述。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 圖的基本概念 G（ m， n） 8 1 圖論基礎(chǔ) 圖的概念 — 圖的定義 圖的拓?fù)潢P(guān)系 : 頂點(diǎn)和邊間的聯(lián)接關(guān)系。 G1=（ 5， 7） G2=（ 4， 6） G3=（ 6， 9） 10 1 圖論基礎(chǔ) 圖的概念 — 圖的定義 關(guān)聯(lián)與鄰接 : 鄰接點(diǎn)與鄰接邊 點(diǎn)、邊關(guān)聯(lián) 關(guān)聯(lián) 與 鄰接 的區(qū)別 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 v1與 e1關(guān)聯(lián) v5與 v6鄰接 e2與 e3鄰接 11 1 圖論基礎(chǔ) 圖的概念 — 圖的定義 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 平行邊 （重邊） 圈 多重圖 重邊數(shù)量叫重數(shù) =2 始末點(diǎn)重合的分支。 完全圖 每一對不同節(jié)點(diǎn)間均有一條邊相連 m階完全圖有多少條邊？ =m(m1)/2 2mCe6 v1 v2 v3 v4 e1 e2 e3 e4 e5 e10 簡單圖 12 1 圖論基礎(chǔ) 圖的概念 — 圖的同構(gòu) 2）圖的同構(gòu) 表示節(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系，對其它無限制。 （ 4,6）圖 網(wǎng)絡(luò)圖的美化調(diào)整 2 1 3 4 1 3 2 4 1 2 3 4 3 2 4 1 13 1 圖論基礎(chǔ) 圖的概念 — 子圖 3）子圖 )()( GVHV ?真子圖 : GH ?)()( GEHE ?)()( GVHV ?GH ? )()( GEHE ?或 H中至少有一個邊的重數(shù)小于 G中對應(yīng)邊的重數(shù) 且 ： H中邊的重數(shù)不超過 G中對應(yīng)邊的重數(shù) 生成子圖 : ),(1EVH ?),( EVG ? EE ?1H是包含了圖 G所有節(jié)點(diǎn)的真子圖 生成子圖是原圖的真子圖！ 若 若 且 或 14 1 圖論基礎(chǔ) 圖的概念 — 子圖 課堂練習(xí) 根據(jù)右圖 1）找出 3個子圖； 2）找出 4個真子圖； 3）試找出 2個生成子圖 e1 e5 e7 e8 e4 e6 e3 e2 e9 1 2 3 5 4 6 15 1 圖論基礎(chǔ) 圖的概念 — 賦權(quán)圖 4）賦權(quán)圖 一個圖 G=（ V， E）與定義在 E或 V上的權(quán)或權(quán)函數(shù)，稱為一個網(wǎng)絡(luò)或賦權(quán)圖，亦稱有權(quán)圖。一般將權(quán)值注在分支旁邊。 ei vi 1 vi 17 1 圖論基礎(chǔ) 道路與回路 — 鏈 簡單鏈 : 鏈 : 53483726345 vevevevevev ??????????閉鏈 : 53483726351 vevevevevev ??????????例 3 7 2 2 4 8 3 4 5 3 4 v e v e v e v e v e v ? ? ? ? ? ? ? ? ? ? V3 V1 V2 V4 V5 e1 e2 e3 e4 e5 e6 e7 e8 簡單鏈 : 基本鏈 : 沒有重復(fù)邊的鏈 沒有重復(fù) 頂點(diǎn) 的鏈 18 1 圖論基礎(chǔ) 道路與回路 — 路 2）路 路 道路 /通路 : 一條不閉合的基本鏈 方向一致的路 道路的權(quán) : 兩節(jié)點(diǎn)間每條道路內(nèi)各邊的權(quán)之和 最長路與最短路 回路 : 始點(diǎn)和終點(diǎn)重合的基本鏈 V3 V1 V2 V4 V5 e1 e2 e3 e4 e5 e6 e7 e8 19 1 圖論基礎(chǔ) 道路與回路 — 路 e1 e5 e7 e8 e4 e6 e3 e2 e9 1 2 3 5 4 6 課堂練習(xí) 根據(jù)右圖 1）找出經(jīng)過 2號點(diǎn)的 2條路； 2）找出 3個回路。 23 1 圖論基礎(chǔ) 道路與回路 — 歐拉公式 4）歐拉公式 網(wǎng)孔 f: 在自然網(wǎng)眼中，網(wǎng)眼內(nèi)部 既不含節(jié)點(diǎn)，也不含邊 歐拉公式 : 內(nèi)部回路數(shù) C: 自然網(wǎng)眼 : 邊圍成的區(qū)域 f+mn=2 =1 ? C=nm+1 聯(lián)系區(qū)別 V3 V1 V2 V4 V5 e1 e2 e3 e4 e5 e6 e7 e8 24 1 圖論基礎(chǔ) 樹 — 樹的概念 不含回路的連通圖。 包含所有節(jié)點(diǎn)；不唯一 生成樹 26 生成樹 : 包含圖 G全部節(jié)點(diǎn)的樹。 生 成 樹 的 特 點(diǎn) 圖 G(7,11) 生成樹 T 29 1 圖論基礎(chǔ) 樹 — 生成樹和余樹 特別提醒 任何 聯(lián)通圖 的 邊數(shù) 等于其 余樹弦數(shù) 和 樹枝數(shù) 之和 圖的 生成樹 連通但 不含 回路 余樹 既 可含回路 ，也 可不連通 任何 圖 的 邊數(shù) 等于其 余樹弦數(shù) 和 樹枝數(shù) 之和 30 1 圖論基礎(chǔ) 樹 — 生成樹和余樹 特別提醒 生成樹 與 余樹 之間的區(qū)別 節(jié)點(diǎn)數(shù)方面 回路方面 連通性方面 31 1 圖論基礎(chǔ) 樹 — 基本回路 3）基本回路 由一條余樹弦和 T的樹枝構(gòu)成的回路，稱為圖 G關(guān)于生成樹 T的基本回路。 最大樹 Tmax 最小樹 Tmin 34 1 圖論基礎(chǔ) 樹 — 最大樹與最小樹 圖的最小樹是（ ）的樹。 思考 以上都不是 權(quán)最大 35 1 圖論基礎(chǔ) 割集 — 割集的定義 割集 S是連通圖 G的邊的集合 ,把 S從 G中移去 ,使圖 G僅 成為 兩部分 ,但如少移去 S中的一條邊 ,則圖 G仍是連通的。 S2={a,c,e,g} 36 1 圖論基礎(chǔ) 割集 — 割集的定義 割點(diǎn) 去除該點(diǎn)