關(guān)于圖論的知識(shí)點(diǎn)

1、退出開始電路分析基礎(chǔ)1-4 圖論的初步知識(shí) 內(nèi)容提要圖論的起源圖論的基本概念X1. 圖論的起源圖論屬于數(shù)學(xué)的一個(gè)分支，它是一個(gè)年輕但卻迅速成熟的學(xué)科，它主要是研究事物之間的客觀規(guī)律。哥尼斯堡橋問題X從任一陸地出發(fā)走遍七座橋（而且只走一次）再回到 原地是否可行？1736年Euler（歐拉：圣彼得堡大學(xué)的數(shù)學(xué)教授）證明 無解。古普魯士哥尼斯堡城的Pregel有七座橋?qū)⑺膲K陸地相 連。連通圖每點(diǎn)連接的邊數(shù)為偶數(shù)才能有解。演示返回1. 圖論的起源X2. 圖論的一些基本概念1.圖 2.有向圖 3.連通圖9.割集 8.網(wǎng)孔4.平面圖 5.子圖 6.樹7.基本回路X2. 圖論的一些基本概念應(yīng)用圖論討論電路的

2、結(jié)構(gòu)及其聯(lián)接性質(zhì)，對(duì)電路進(jìn)行分析，稱為網(wǎng)絡(luò)圖論（網(wǎng)絡(luò)拓?fù)鋵W(xué)）。2.1 拓?fù)?topology)：幾何或聯(lián)接性質(zhì)。2.2 圖(Graph):電路（網(wǎng)絡(luò)）的圖由支路（線段）和節(jié)點(diǎn)（點(diǎn)）組成，用G表示。每一支路代表一個(gè)電路元件或一些電路元件的某種組合，每一支路都連接在圖中的兩個(gè)節(jié)點(diǎn)之間。標(biāo)準(zhǔn)支路組合X電路圖 拓?fù)鋱DG 在電路分析中，圖中邊上的箭頭即表示該邊所代表的支路電壓、電流方向。 2. 圖論的一些基本概念2.3 有向圖(directed graph)：給圖中的每一條支 路都規(guī)定了方向的圖。否則，稱為無向圖( undirected graph)令b表示邊數(shù)，n表示節(jié)點(diǎn)數(shù)，則圖中b4， n3 。X2

3、.5 連通圖(connected graph)：圖G中任意兩節(jié)點(diǎn)之間至少存在一條路徑的圖。否則稱為不連通圖(unconnected graph)。 連通圖不連通圖2. 圖論的一些基本概念2.4 路徑(path)：從圖G的某一節(jié)點(diǎn)出發(fā)，沿著一些支路連續(xù)移動(dòng)，從而到達(dá)另一指定的節(jié)點(diǎn)或原節(jié)點(diǎn)，則這樣一系列的支路便構(gòu)成了圖G的一條路徑。X2.6 平面圖(planar graph)：一個(gè)圖G畫在平面上時(shí)，其各條支路除所聯(lián)接的節(jié)點(diǎn)外不再交叉的圖。否則稱為非平面圖。平面圖非平面圖2. 圖論的一些基本概念X 圖G 子圖2. 圖論的一些基本概念2.7 子圖(subgraph)：圖G中的一部分稱為其子圖。子圖有很多。子圖X2. 圖論的一些基本概念2.8 樹(tree-T) ：樹是連通圖G的一個(gè)連通子圖；包含圖G的所有的節(jié)點(diǎn)；不包含任何回路。T2 T1 樹支：組成樹的支路。連支：其余的支路。 圖G X樹支電壓，連支電流 2.9 基本回路：只含有一條連支的回路。樹支集合 連支集合以連支的方向?yàn)榛净芈返睦@行方向。注意2. 圖論的一些基本概念X2.10 網(wǎng)孔(mesh)：內(nèi)部不包含支路的回路叫網(wǎng)孔。2. 圖論的一些基本概念圖中網(wǎng)孔為：1,2,3 2,4,5 3,5,6基本回路為：X 割集2.11 割集 (cutset) ：圖G的割集是G的一些支路集合，把這些支路移去將使