圖論的初步知識(shí)PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1圖論的初步知識(shí)圖論的初步知識(shí)圖論屬于數(shù)學(xué)的一個(gè)分支，它是一個(gè)年輕但卻迅速成圖論屬于數(shù)學(xué)的一個(gè)分支，它是一個(gè)年輕但卻迅速成熟的學(xué)科，它主要是研究事物之間的客觀規(guī)律。熟的學(xué)科，它主要是研究事物之間的客觀規(guī)律。哥尼斯堡橋問題哥尼斯堡橋問題X第1頁/共13頁從任一陸地出發(fā)走遍七座橋（而且只走一次）再回到從任一陸地出發(fā)走遍七座橋（而且只走一次）再回到 原地是否可行？原地是否可行？17361736年年EulerEuler（歐拉：圣彼得堡大學(xué)的數(shù)學(xué)教授）證明（歐拉：圣彼得堡大學(xué)的數(shù)學(xué)教授）證明 無解。無解。ACBDabcdegf古普魯士古普魯士哥尼斯堡哥尼斯堡城的城的PregelPregel有七座橋

2、將四塊陸地相有七座橋?qū)⑺膲K陸地相 連。連。連通圖每點(diǎn)連接的邊數(shù)為偶數(shù)才能有解。連通圖每點(diǎn)連接的邊數(shù)為偶數(shù)才能有解。演示演示返回返回X第2頁/共13頁1.1.圖圖 2.2.有向圖有向圖 3.3.連通圖連通圖9.9.割集割集 8.8.網(wǎng)孔網(wǎng)孔4.4.平面圖平面圖 5.5.子圖子圖 6.6.樹樹7.7.基本回路基本回路X第3頁/共13頁應(yīng)用圖論討論電路的結(jié)構(gòu)及其聯(lián)接性質(zhì)，對(duì)電路進(jìn)行應(yīng)用圖論討論電路的結(jié)構(gòu)及其聯(lián)接性質(zhì)，對(duì)電路進(jìn)行分析，稱為分析，稱為網(wǎng)絡(luò)圖論（網(wǎng)絡(luò)拓?fù)鋵W(xué)）。網(wǎng)絡(luò)圖論（網(wǎng)絡(luò)拓?fù)鋵W(xué)）。2.1 拓?fù)渫負(fù)?topology)：幾何或聯(lián)接性質(zhì)幾何或聯(lián)接性質(zhì)。2.2 圖圖(Graph):電路（網(wǎng)絡(luò)）

3、的圖由支路（線段）和節(jié)電路（網(wǎng)絡(luò)）的圖由支路（線段）和節(jié)點(diǎn)（點(diǎn)）組成，用點(diǎn)（點(diǎn)）組成，用G表示。每一支路代表一個(gè)電路元件表示。每一支路代表一個(gè)電路元件或一些電路元件的某種組合，每一支路都連接在圖中或一些電路元件的某種組合，每一支路都連接在圖中的兩個(gè)節(jié)點(diǎn)之間。的兩個(gè)節(jié)點(diǎn)之間。 i u 標(biāo)準(zhǔn)支標(biāo)準(zhǔn)支路組合路組合X第4頁/共13頁 1234 電路圖電路圖 拓?fù)鋱D拓?fù)鋱DG 1234 在電路分析中，圖中邊上的箭頭即表示該邊所代表在電路分析中，圖中邊上的箭頭即表示該邊所代表的支路電壓、電流方向。的支路電壓、電流方向。 2.3 有向圖有向圖(directed graph)：給圖中的每一條支給圖中的每一條支

4、路都路都規(guī)定了方向的圖。否則，稱為規(guī)定了方向的圖。否則，稱為無向圖無向圖( undirected graph)令令b表示表示邊數(shù)，邊數(shù)，n表示節(jié)點(diǎn)數(shù)，則圖中表示節(jié)點(diǎn)數(shù)，則圖中b4， n3 3 。X第5頁/共13頁2.5 連通圖連通圖(connected graph)：圖圖G中任意兩節(jié)點(diǎn)之間中任意兩節(jié)點(diǎn)之間至 少 存 在 一 條 路 徑 的 圖 。 否 則 稱 為至 少 存 在 一 條 路 徑 的 圖 。 否 則 稱 為 不 連 通 圖不 連 通 圖(unconnected graph)。 連通圖連通圖不連通圖不連通圖2.4 路徑路徑(path)：從圖從圖G的某一節(jié)點(diǎn)出發(fā)，沿著一些支的某一節(jié)點(diǎn)出

5、發(fā)，沿著一些支路連續(xù)移動(dòng)，從而到達(dá)另一指定的節(jié)點(diǎn)或原節(jié)點(diǎn)，則路連續(xù)移動(dòng)，從而到達(dá)另一指定的節(jié)點(diǎn)或原節(jié)點(diǎn)，則這樣一系列的支路便構(gòu)成了圖這樣一系列的支路便構(gòu)成了圖G的一條路徑。的一條路徑。X第6頁/共13頁2.6 平面圖平面圖( (planar graph) )：一個(gè)圖一個(gè)圖G畫在平面上時(shí)，畫在平面上時(shí)，其各條支路除所聯(lián)接的節(jié)點(diǎn)外不再交叉的圖。否則稱其各條支路除所聯(lián)接的節(jié)點(diǎn)外不再交叉的圖。否則稱為非平面圖。為非平面圖。平面圖平面圖非平面圖非平面圖X第7頁/共13頁 12345 圖圖G 1245子圖子圖1G2.7 子圖子圖( (subgraph) )：圖圖G中的一部分稱為其子圖。中的一部分稱為其子圖

6、。子圖有很多。子圖有很多。子子圖圖2G 1345X第8頁/共13頁 123 1451 nnt樹支數(shù)1 nbnblt數(shù)連支2.8 樹樹(tree-T) ：樹是連通圖樹是連通圖G的一個(gè)的一個(gè)連通連通子圖；包含子圖；包含圖圖G的所有的節(jié)點(diǎn)；不包含任何回路。的所有的節(jié)點(diǎn)；不包含任何回路。T2 T1 樹支：樹支：組成樹的支路。組成樹的支路。連支：連支：其余的支路。其余的支路。 12345 圖圖G X第9頁/共13頁樹支電壓，連支電流樹支電壓，連支電流 123456 2 5 6 ， 5 6 3 ， 5 2 4 ， 2.9 基本回路：基本回路：只含有一條連支的回路。只含有一條連支的回路。 123456 6

7、5 2 ，樹支集合樹支集合 4 3 1 ， 連支集合連支集合以連支的方向?yàn)榛净芈返睦@行方向。以連支的方向?yàn)榛净芈返睦@行方向。注注意意X第10頁/共13頁2.10 網(wǎng)孔網(wǎng)孔(mesh)：內(nèi)部不包含支路的回路叫網(wǎng)孔。內(nèi)部不包含支路的回路叫網(wǎng)孔。2. 圖論的一些基本概念圖論的一些基本概念圖中網(wǎng)孔為：圖中網(wǎng)孔為：1,2,3 2,4,5 3,5,6 2 5 6 ， 5 6 3 ， 5 2 4 ，基本回路為：基本回路為： 123456 123456X第11頁/共13頁 4 5 3 ，割集割集2.11 割集割集 (cutset) ：圖圖G的割集是的割集是G的一些支路集合，的一些支路集合，把這些支路移去將使把這些支路移去將使G分離為兩個(gè)部分，而如果少移分離為兩個(gè)部分，而