專題五 通風網(wǎng)絡(luò)理論

1、一一. 圖的基本知識圖的基本知識n圖是用來研究一組具體事物之間相互關(guān)系的抽圖是用來研究一組具體事物之間相互關(guān)系的抽象代數(shù)。用點表示事物，用連線表示不同事物象代數(shù)。用點表示事物，用連線表示不同事物之間的關(guān)系。之間的關(guān)系。n這樣就形成了用這些點和連線表示事物特征的這樣就形成了用這些點和連線表示事物特征的抽象圖形。如：抽象圖形。如：事物 不同事物間的聯(lián)系圖1：角聯(lián)網(wǎng)絡(luò)圖例圖圖2 2：簡單網(wǎng)絡(luò)圖例：簡單網(wǎng)絡(luò)圖例圖的定義12,mVv vv圖是由作為研究對象的有限個點（如圖是由作為研究對象的有限個點（如mm個）個）的集合和表達這些點之間關(guān)系的的集合和表達這些點之間關(guān)系的n n條連線的條連線的集合所組成的，

2、可以記作集合所組成的，可以記作12,mEe ee如圖如圖，它們都是以，它們都是以v v1 1,v,v2 2, , ,v vmm標記點的集標記點的集合，以合，以e e1 1,e ,e2 2, , ,e ,en n標記點的連線（簡稱為線）的標記點的連線（簡稱為線）的集合所組成的集合所組成的 是點的是點的有窮非空集合有窮非空集合（即（即為節(jié)點的集合）記作（），其元素為節(jié)點的集合）記作（），其元素為點為點 是圖的連線的集合，記是圖的連線的集合，記作（）其元素為線作（）其元素為線圖的定義圖的定義12,mVv vv給出的圖的基本定義包括（、給出的圖的基本定義包括（、）12,mEe ee圖的定義圖的定義、是

3、以到中的有序或無序偶對所成集合的映射。即：對于集合中的每一個元素，按照某一規(guī)則，都可在集合中找到唯一元素與之對應。如323,)(vve例如：圖可記作：例如：圖可記作：具有具有mm個點，個點，n n條連線的圖，通常也稱為條連線的圖，通常也稱為（mm，n)n)圖。圖就是一個圖。圖就是一個（，）圖（，）圖圖論中，用帶箭頭的線表示有向分支，箭圖論中，用帶箭頭的線表示有向分支，箭頭方向表示由初節(jié)點指向末節(jié)點的方向頭方向表示由初節(jié)點指向末節(jié)點的方向856( ),ev v2,11)(vve 312,)(vve 圖的定義圖的定義圖的定義圖3、一個多重圖（二）、線度n線度是圖論中的一個重要數(shù)據(jù)簡單地講，線度是圖

4、論中的一個重要數(shù)據(jù)簡單地講，在圖（，）中，與某個點相關(guān)聯(lián)的在圖（，）中，與某個點相關(guān)聯(lián)的邊（或分支）的數(shù)目，就是該點的線度，邊（或分支）的數(shù)目，就是該點的線度，記作記作)(ivd3)(1vd),(531eee),(42ee5)(2)(11vdvd)(51ee 出為+入為-（三）圖的連通性（三）圖的連通性在一個圖中，如果在每一對點之間至在一個圖中，如果在每一對點之間至少存在一條鏈連接，則稱為少存在一條鏈連接，則稱為連通圖連通圖。否則就是否則就是不連通圖不連通圖。思考：風洞是否是連通圖？思考：風洞是否是連通圖？ 一個圖一個圖G=G=（V V，E E）和定義在）和定義在G G的邊或的邊或分支集分支集

5、E E或點集或點集V V上的一個實函數(shù)上的一個實函數(shù)f(ef(e) )或或f(vf(v) )，稱為一個網(wǎng)絡(luò)或有權(quán)圖。即：有，稱為一個網(wǎng)絡(luò)或有權(quán)圖。即：有權(quán)圖叫做網(wǎng)絡(luò)。權(quán)圖叫做網(wǎng)絡(luò)。 記作：記作：N=N=（G G，f f），函數(shù)），函數(shù)f f叫權(quán)函數(shù)。叫權(quán)函數(shù)。網(wǎng)絡(luò)的圖解是通過在圖的分支或點的旁網(wǎng)絡(luò)的圖解是通過在圖的分支或點的旁邊注明權(quán)來表示。邊注明權(quán)來表示。由上分析可見：通風網(wǎng)絡(luò)是一個由多個有方由上分析可見：通風網(wǎng)絡(luò)是一個由多個有方向的分支組成的連通圖。向的分支組成的連通圖。1 1、節(jié)點：三條以上分支的相交點稱作節(jié)點，、節(jié)點：三條以上分支的相交點稱作節(jié)點，用用v vi i來表示。來表示。風流方

6、向：風流方向：2 2、割點：是節(jié)點的一種形式，當把割點從圖、割點：是節(jié)點的一種形式，當把割點從圖中去掉時，原網(wǎng)路圖可分為若干子圖。中去掉時，原網(wǎng)路圖可分為若干子圖。 321vvv通風網(wǎng)絡(luò)的基本術(shù)語通風網(wǎng)絡(luò)的基本術(shù)語3 3、風路：兩個節(jié)點間的分支。記作、風路：兩個節(jié)點間的分支。記作e ei i。4 4、回路：由兩條以上風路形成的閉合圈，記作、回路：由兩條以上風路形成的閉合圈，記作b bi i。5 5、網(wǎng)孔：回路內(nèi)無其它風路時，稱為網(wǎng)孔。是回、網(wǎng)孔：回路內(nèi)無其它風路時，稱為網(wǎng)孔。是回路的特殊形式。路的特殊形式。試分別指出圖中回路、網(wǎng)孔的個數(shù)試分別指出圖中回路、網(wǎng)孔的個數(shù)6 6、通路：從、通路：從v

7、 v1 1到到v vmm由不同風路組成的一條由不同風路組成的一條路徑，記作路徑，記作P Pi i。圖中紅色部分為一個通路圖中紅色部分為一個通路1. 質(zhì)量守恒定律：在單位時間內(nèi)，任一節(jié)點流入質(zhì)量守恒定律：在單位時間內(nèi)，任一節(jié)點流入 和流出空氣質(zhì)量的代數(shù)和為零。和流出空氣質(zhì)量的代數(shù)和為零。01ijnjijq三 通風網(wǎng)路的基本性質(zhì)),.2 , 1,(miij54321iiiiiqqqqqnjijq10通風網(wǎng)路的基本性質(zhì)2. 2. 能量守恒定律：在任何回路（或網(wǎng)孔）能量守恒定律：在任何回路（或網(wǎng)孔）上所發(fā)生的風流能轉(zhuǎn)換的代數(shù)和為零。上所發(fā)生的風流能轉(zhuǎn)換的代數(shù)和為零。njnjnjzijijijhhh0)

8、 1,2 , 1,(mniij式中式中: hij在第在第i個回路上的第個回路上的第j條風路的風壓值，條風路的風壓值，Pa hfij在第在第i個回路上的第個回路上的第j條風路中風機的風壓，條風路中風機的風壓，Pa hzij在第在第i個回路上的第個回路上的第j條風路的自然風壓，條風路的自然風壓，Pa當回路中既無通風機又忽略自然風壓時當回路中既無通風機又忽略自然風壓時,即為風壓平衡定律即為風壓平衡定律 。 通風網(wǎng)路的基本性質(zhì)3.3.阻力定律阻力定律: : 管道流多為完全紊狀態(tài)管道流多為完全紊狀態(tài), , 其阻力定律為其阻力定律為2iiiQRh ), 2 , 1(ni通風網(wǎng)路的基本性質(zhì)4.風路中的串聯(lián)特

9、性: 總風量和分風量的關(guān)系:總風壓和分風壓的關(guān)系:總風阻和分風阻的關(guān)系:nQQQQ210nhhhh210001010210QhQhQhhRRnRRRnn通風網(wǎng)路的基本性質(zhì)nQQQQ210nhhhh2105. 風路的并聯(lián)特性： 風量: 風壓: 風阻:22101111nRRRRnRRR11110nnRhRhRhRh221100RhQRhQRhQ,22211100052 通風網(wǎng)路的拓撲關(guān)系一一網(wǎng)路拓撲的定義網(wǎng)路拓撲的定義 通風網(wǎng)路圖也稱通風網(wǎng)路圖也稱為拓撲圖為拓撲圖, ,即是用線段即是用線段（有向分支）和節(jié)點（有向分支）和節(jié)點表示的圖，均稱拓撲表示的圖，均稱拓撲圖。如：右圖可表示圖。如：右圖可表示為

10、有向圖為有向圖G(V,E,G(V,E,) ) 。 網(wǎng)路拓撲的定義12612913212323956,:,Vv vvEe eeev vev vev vev v這里表示第條邊以這里表示第條邊以vi為始節(jié)點，為始節(jié)點，vj為終節(jié)點為終節(jié)點,kijev v,ijjiv vv v其中其中對于無向圖如何？二、樹的概念及其定理1 1、子圖、子圖: : 下頁圖中的下頁圖中的1 1、2 2、3 3稱為子圖：稱為子圖： 非連通圖一般由若干子圖所構(gòu)成。非連通圖一般由若干子圖所構(gòu)成。2 2、樹：、樹： 樹是網(wǎng)路圖樹是網(wǎng)路圖G G中的一個子圖中的一個子圖GG。若。若GG是是連通圖，且包含圖連通圖，且包含圖G G中所有節(jié)

11、點，但又不形成中所有節(jié)點，但又不形成回路，則稱回路，則稱GG為為G G的一個生成樹，簡稱樹。的一個生成樹，簡稱樹。3 3、余樹：在網(wǎng)路圖中，把樹去掉，剩下的部分、余樹：在網(wǎng)路圖中，把樹去掉，剩下的部分圖形稱為余樹，用圖形稱為余樹，用L L 表示。表示。樹的概念及其定理子圖樹和余樹樹和余樹6.6.定理：定理： 網(wǎng)路圖網(wǎng)路圖G(VG(V，E),E),V V =m=m，E E =n=n。則其樹必有則其樹必有mm個節(jié)點和個節(jié)點和（m-1m-1）條分支（或邊）；）條分支（或邊）；若網(wǎng)路圖若網(wǎng)路圖G G的（的（m-1m-1）條分）條分支（或邊）不形成回路，支（或邊）不形成回路，則這（則這（m-1m-1）條

12、分支必）條分支必 是是G G的一個樹。的一個樹。樹的概念及其定理實線部分分別表示一棵樹1,1TLEmEn m 樹的概念及其定理可見，一個可見，一個G G的生成樹是包含了圖的生成樹是包含了圖G G的全部節(jié)的全部節(jié)點，但不包含任何回路的連通子圖。而余樹點，但不包含任何回路的連通子圖。而余樹E EL L則可能含有回路。則可能含有回路。由定理知：由定理知： 53 圖的矩陣表示o 借助于圖的圖解表示，雖然可使圖的概念借助于圖的圖解表示，雖然可使圖的概念的描述具有一定的直觀性，但這種表示方的描述具有一定的直觀性，但這種表示方法卻有局限性，尤其是隨著頂點和邊的數(shù)法卻有局限性，尤其是隨著頂點和邊的數(shù)的增加，要

13、用圖的結(jié)構(gòu)就變得很困難，而的增加，要用圖的結(jié)構(gòu)就變得很困難，而且，圖解表示也不便于圖的運算。且，圖解表示也不便于圖的運算。o 因此，有必要應用代數(shù)的方法來表示一個因此，有必要應用代數(shù)的方法來表示一個圖，這就是圖的矩陣表示。圖，這就是圖的矩陣表示。圖的矩陣表示圖的矩陣表示o 圖實現(xiàn)矩陣表示后 圖的運算非常有效 可以實現(xiàn)圖在計算機里的存儲與運算定理來研究分析可以使用矩陣規(guī)則圖的矩陣表示圖的矩陣表示o 設(shè)圖設(shè)圖G=G=（V V，E E）是一個（）是一個（m,nm,n）圖，則）圖，則圖圖G G即可按其各元素之間的關(guān)聯(lián)或鄰接關(guān)即可按其各元素之間的關(guān)聯(lián)或鄰接關(guān)系，用系，用關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣、鄰接矩陣鄰接矩陣

14、或其它方式表或其它方式表示。示。o 由于不論是用何種矩陣來表示，矩陣總是由于不論是用何種矩陣來表示，矩陣總是與與mm個點個點n n條邊（或分支）的某種排列次條邊（或分支）的某種排列次序有關(guān)，所以在論及圖的矩陣表示時，必序有關(guān)，所以在論及圖的矩陣表示時，必須預先繪出點和邊的排列次序。須預先繪出點和邊的排列次序。一、節(jié)點鄰接矩陣一、節(jié)點鄰接矩陣Do 節(jié)點鄰接矩陣節(jié)點鄰接矩陣D點與點間的分支數(shù)（邊數(shù)）點與點間的分支數(shù)（邊數(shù)） 如：如：G G（V V，E E），），V V = m,= m,E E = n= nijmnDd其他當0;,1Evjviijd 其中其中即，即，dij是節(jié)點是節(jié)點vi到到vj之間

15、是相連接的分支（或邊）的個數(shù)。之間是相連接的分支（或邊）的個數(shù)。節(jié)點鄰接矩陣Do 如圖：v1到v2有兩條邊相連所以d12=2，即：654321000000200000010000002000010100000020vvvvvvD654321vvvvvv節(jié)點鄰接矩陣Do D D 矩陣中，行反映矩陣中，行反映v vi i的入度，列反映的入度，列反映v vj j的的出度。出度。 有向圖的有向圖的D D矩陣不對稱。矩陣不對稱。 無向圖的無向圖的D D矩陣對稱。矩陣對稱。關(guān)聯(lián)矩陣A 定義 并令: 則稱Aa為網(wǎng)路圖G的完全關(guān)聯(lián)矩陣 nmijaAa011ija邊（或分支）出該節(jié)點）當（;,Eevvjki；邊

16、或分支進入該節(jié)點當Eevvjjk),(其它二、關(guān)聯(lián)矩陣二、關(guān)聯(lián)矩陣A110000000111001000001110000000110100000001111000000011Aa654321vvvvvv987654321eeeeeeeee關(guān)聯(lián)矩陣AA矩陣中，行對應網(wǎng)路圖G的各個節(jié)點 列對應網(wǎng)路圖G的各條邊（或分支）。如，上圖的完全關(guān)聯(lián)矩陣為：關(guān)聯(lián)矩陣的秩定理o 1.關(guān)聯(lián)矩陣的秩定理： 若網(wǎng)路圖G（V，E）， V =m ，E =n，若Aa是其完全關(guān)聯(lián)矩陣，則Aa的秩為m-1.補充知識補充知識秩秩o 向量組的秩：向量組 中的極大無關(guān)組的向量個數(shù)唯一確定，叫做這個向量組的秩。o 相關(guān)：若中有一向量

17、可以經(jīng)其余的向量線性表示，這個向量組就叫做線性相關(guān)。 充要條件：m,21111221200mmmmkkkkkkkk否則：為線性無關(guān)為不全為零的數(shù)即時才有上述結(jié)論 矩陣的秩：矩陣矩陣的秩：矩陣 的行秩或列秩定的行秩或列秩定義為義為A A的秩的秩nmijaA)(補充知識補充知識秩秩根據(jù)關(guān)聯(lián)矩陣的秩定理可知：把根據(jù)關(guān)聯(lián)矩陣的秩定理可知：把A Aa a矩陣矩陣中的任意一行去掉，所剩下中的任意一行去掉，所剩下m-1m-1行均線性行均線性獨立。把這（獨立。把這（m-1m-1）n n的矩陣稱為的矩陣稱為基本關(guān)基本關(guān)聯(lián)矩陣聯(lián)矩陣，簡稱關(guān)聯(lián)矩陣，簡稱關(guān)聯(lián)矩陣A A補充知識補充知識秩秩如上例 1111000000

18、01011000000011100000100111110000011A關(guān)聯(lián)矩陣的秩定理關(guān)聯(lián)矩陣的秩定理o 關(guān)聯(lián)矩陣等價于關(guān)聯(lián)矩陣等價于G G（網(wǎng)絡(luò)圖）。（網(wǎng)絡(luò)圖）。G G的性質(zhì)的性質(zhì)可以通過可以通過A A的運算獲得。改變的運算獲得。改變G G 中的節(jié)點中的節(jié)點或邊的排列次序，相當于對或邊的排列次序，相當于對A A的行或列進的行或列進行調(diào)換。行調(diào)換。o 也就是說，從也就是說，從A A（關(guān)聯(lián)矩陣）可知通風網(wǎng)（關(guān)聯(lián)矩陣）可知通風網(wǎng)路中的每一個節(jié)點連著那些風路，風向如路中的每一個節(jié)點連著那些風路，風向如何等。何等。關(guān)聯(lián)矩陣的秩定理關(guān)聯(lián)矩陣的秩定理o 對于任一通風網(wǎng)路，有風量矩陣對于任一通風網(wǎng)路，有風

19、量矩陣Q，即，即),(21nqqqQ0TAQ其中其中QT表示表示Q的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣當矩陣當矩陣A和和Q的排列順序相同時，風量平的排列順序相同時，風量平衡方程衡方程 可表示為：可表示為： 1289111100000001011000000011100000000111110000011TqqqqAQ8123435647891290qqqqqqqqqqqqqqq關(guān)聯(lián)矩陣的秩定理關(guān)聯(lián)矩陣的秩定理如上例o 既然既然A A 包含了網(wǎng)路圖包含了網(wǎng)路圖G G中的所有信息，就中的所有信息，就可以從可以從A A 中決定哪些邊是樹，哪些邊是余中決定哪些邊是樹，哪些邊是余樹，因此，圖論中還有一個定理。樹，因此，

20、圖論中還有一個定理。o 2.2.關(guān)聯(lián)矩陣樹定理：有關(guān)聯(lián)矩陣樹定理：有mm個節(jié)點的網(wǎng)絡(luò)圖個節(jié)點的網(wǎng)絡(luò)圖G G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣A A。它的（。它的（m-1m-1）個列向量線）個列向量線性無關(guān)的充要條件性無關(guān)的充要條件 是這些列與網(wǎng)路圖是這些列與網(wǎng)路圖G G的的樹支相對應。樹支相對應。關(guān)聯(lián)矩陣樹定理關(guān)聯(lián)矩陣樹定理o 由這個定理可知，A（關(guān)聯(lián)矩陣）可以分為余支和樹支的兩個子矩陣，即）（如上：nmAAT, 1. 0det是對應樹支的子矩陣是對應余支的子矩陣；其中ATAL,LTAAA并且(1,1)(1,1)TLAmmAmnm關(guān)聯(lián)矩陣樹定理123456(,)11001100001000010000100

21、0110000100011100100001det10LTTAA AvvvvvvA 且876429531eeeeeeeee2467813596,9(5,9),(5,5),(5,4,LTLTmnAAAEe e e e eEe e e e 如上例：）若選擇則網(wǎng)路圖含樹的數(shù)目定理網(wǎng)路圖含樹的數(shù)目定理o 一個網(wǎng)路圖一個網(wǎng)路圖G G所包含的樹的形式不是唯一所包含的樹的形式不是唯一的的 ，樹的個數(shù)可由下面的定理來計算：，樹的個數(shù)可由下面的定理來計算：o 3.3.網(wǎng)路圖含樹的數(shù)目定理：若網(wǎng)路圖含樹的數(shù)目定理：若A A是網(wǎng)路圖是網(wǎng)路圖G G的關(guān)聯(lián)矩陣，則該圖所包含樹的數(shù)目是：的關(guān)聯(lián)矩陣，則該圖所包含樹的數(shù)目是

22、：)det(TAA網(wǎng)路圖含樹的數(shù)目定理101110001100110101110110001010TAA2111318113 由于上圖要算太復雜，用一個較簡單的圖形加以說明：三、回路矩陣三、回路矩陣B 1.定義：對于G（V，E），有m個節(jié)點、n條邊（分支），S個回路，()ai jBbsn011bij同在回路之上，且方向相je反在回路之上，且方向相ej其它則稱有向網(wǎng)路圖G的完全回路矩陣。回路方向一般取順時針方向。即其中回路矩陣回路矩陣B41235110000000001101100000011000000000011001110100bbBabbb987654321eeeeeeeee如上面的（如

23、上面的（6，9）圖。）圖?；芈肪仃嚮芈肪仃嘊o 完全回路矩陣完全回路矩陣BaBa共有共有S S 行，實踐中可以看行，實踐中可以看出，即使中等規(guī)模的通風網(wǎng)路，其出，即使中等規(guī)模的通風網(wǎng)路，其S S也相也相當大，但在網(wǎng)路分析中我們并不需要列出當大，但在網(wǎng)路分析中我們并不需要列出系統(tǒng)圖中的全部回路，只需列出一個線性系統(tǒng)圖中的全部回路，只需列出一個線性無關(guān)的回路矩陣，即找出無關(guān)的回路矩陣，即找出BaBa的秩，便可的秩，便可滿足要求。滿足要求。o 故要學習回路矩陣的秩定理，以導出相關(guān)故要學習回路矩陣的秩定理，以導出相關(guān)的風壓平衡定理。的風壓平衡定理?；芈肪仃囍榷ɡ砘芈肪仃囍榷ɡ? 2、回路矩陣秩定理：網(wǎng)

24、路圖、回路矩陣秩定理：網(wǎng)路圖G G（V V，E E），），V V =mm，E E =n n。其完全回路矩。其完全回路矩陣陣 B Ba a的秩為（的秩為（n-m+1n-m+1） 。o 將滿秩的回路矩陣稱為將滿秩的回路矩陣稱為基本回路矩陣基本回路矩陣，簡稱回路矩陣簡稱回路矩陣B B。 回路矩陣回路矩陣風壓平衡方程風壓平衡方程o 對任一通風網(wǎng)路有風壓矩陣：對任一通風網(wǎng)路有風壓矩陣：o 則當則當H與與B的列排列次序相同時，可用下的列排列次序相同時，可用下式表示風壓平衡方程：式表示風壓平衡方程： ),(21nhhhH0TBHo構(gòu)造基本回路的方法構(gòu)造基本回路的方法通常是先找出一個樹，對于選定的通常是先找出

25、一個樹，對于選定的樹每增加一條余支即可構(gòu)成一個基本回路。這種方法可保樹每增加一條余支即可構(gòu)成一個基本回路。這種方法可保證所選擇的（證所選擇的（n-m+1） 個回路都是滿秩的個回路都是滿秩的 ?；芈肪仃囷L壓平衡方程回路矩陣風壓平衡方程o 由于構(gòu)成回路矩陣由于構(gòu)成回路矩陣B的邊有余支和樹支兩的邊有余支和樹支兩部分，即部分，即(,)LTBB BLTBBBB其中是 的余支子矩陣；是 的樹支子矩陣回路矩陣回路矩陣風壓平衡方程風壓平衡方程o 只要只要B中余支的邊（分支）和方向選得中余支的邊（分支）和方向選得合適，則合適，則BL必為必為單位矩陣單位矩陣I，即，即B=（I，BT），即使選得不合適，亦可通過初等

26、），即使選得不合適，亦可通過初等變換將變換將BL變成變成I。1000001000001000001000001I回路矩陣風壓平衡方程913582467100010000010001110001000100000100001hhhhhhhhh 976428531eeeeeeeee( ,)TTB I BH如右圖中：回路矩陣風壓平衡方程12346756390hhhhhhhhhh四、割集矩陣Co 傳統(tǒng)的風量平衡定律：即任一時刻任一節(jié)點的風量代數(shù)和為零。10ijniq廣義風量平衡定律：通風網(wǎng)路中，任一時刻其任一割集的風量代數(shù)和也為零。那么，這里所說的割集是什么呢 ？割集的概念o 2.割集的概念 設(shè)C是通

27、風網(wǎng)路圖G中某些邊的集合。此集合滿足下列兩條件，則稱C為G的割集將這些邊（或分支）去掉，則網(wǎng)圖G分成兩個相互獨立的部分 ，即形成兩個子圖。若C 集合中， 去掉一條分支或邊，則G就連通。若給割集規(guī)定方向，則稱為有向割集，其中的邊（或分支）分為：與割集線同向邊和反向邊兩類。割集的形成過程1156723463128416478 , , , , Ce e e eCe e eCe e eCe e e e e尋找割集的一般方法o 2.尋找割集的一般方法： 按照概念，割集是將一個連通圖分割成兩部分的最小邊的集合，即如果從G中，放回割集中的一條邊，則G（網(wǎng)路圖）就可以連通。那么在前面講過的內(nèi)容中，哪個概念具有

28、此特性呢？通常是先找出一棵樹，對應每一個樹支就可以得到一個基本或獨立的割集Ci。割集矩陣o 3.割集矩陣設(shè)圖G（V，E）是一個連通的（m,n）圖，則圖中各邊（或分支）與各割集間的關(guān)系，可以用矩陣 來表示（q為割集數(shù)），矩陣C稱為圖G的割集矩陣。) 1()(mqCCnqij01Cij中時包含于割集當邊ijCe中時不包含于割集當邊ijCe；中。不包含于當分支方向相反中，且與包含于當分支方向相同；中，且與包含于當分支ijiijiijijCeCCeCCeC, 0, 1, 1割集矩陣其中Cij有：（1）對無向圖：（2）對有向圖:割集矩陣秩定理o 若通風網(wǎng)路圖G=（V，E）是一個（m,n）圖，則其基 本割集矩陣的秩為（m-1）。 因此，矩陣中只有m-1行向量（割集）是線性無關(guān)的。 亦即稱m-1行的割集矩陣為圖G的獨立割集(Ck)矩陣。割集矩陣秩定理o 根據(jù)：o 1、矩陣秩定理o 2、尋找割集方法中對應一個樹支就可以得到一個m-1個基本割集（或獨立割集）的原理?？芍簅 個樹的每一個樹支上割一下，就能得到獨立的割集矩陣。654321eeeeee321110100101010101101CCCCk),(),(11010010101011100132153LTLkC