流體網(wǎng)絡(luò)題庫介紹

1、第一章流體網(wǎng)絡(luò)的基本概念與拓?fù)潢P(guān)系 名詞解釋：，還是城市集中供熱系統(tǒng)（包括輸送管路、各種調(diào)節(jié)閥門、，以及城市煤氣輸送系統(tǒng)、自來水供應(yīng)系統(tǒng)、集中空調(diào)系統(tǒng)等各種有 它們都有一共同的特點(diǎn)， 那就是它們都是由輸送流體的管路、各種調(diào)流體管路連接在一起形成流體網(wǎng)絡(luò)。只考慮流體管路的幾何連接拓?fù)潢P(guān)系。為此，將管路稱1. 流體網(wǎng)絡(luò)：無論是礦井的通風(fēng)系統(tǒng)（包括有風(fēng)流流動(dòng)的井巷通道、調(diào)節(jié)風(fēng)量分配用的構(gòu)筑 物、作為通風(fēng)動(dòng)力的風(fēng)機(jī)等等） 作為動(dòng)力的泵站等等） 流體流動(dòng)的管路系統(tǒng)， 節(jié)設(shè)施及動(dòng)力設(shè)施構(gòu)成，2. 分支：拋開流體網(wǎng)絡(luò)的各種屬性， 之為分支。3. 節(jié)點(diǎn)：三條以上分支的連接點(diǎn)稱之為節(jié)點(diǎn)；有時(shí)為研究問題方便， 將

2、管路的某種屬性的交變點(diǎn)也稱為節(jié)點(diǎn)，也就是說兩條物理屬性不同的分支的交點(diǎn)也稱之為節(jié)點(diǎn)；還有一類分支， 其一端與其他分支相連接， 而另一端是自由的， 不與任何分支相連接， 將這類端點(diǎn)也稱為節(jié) 點(diǎn)。4. 圖：將流體網(wǎng)絡(luò)中的節(jié)點(diǎn)和分支的集合稱為圖，記為G =（V,E），式中，V表示節(jié)點(diǎn)的集合, m為節(jié)點(diǎn)數(shù)，； e表示分支集合，E，Q，e2I,門為5有向圖：分支ek對(duì)應(yīng)著的兩個(gè)節(jié)點(diǎn)分別為vi和Vj。當(dāng)流體流動(dòng)的方向是 WVj，此時(shí)將分支ek寫Q二S ,Vj ,圖g稱為有向圖6. 無向圖:當(dāng)流體流動(dòng)方向尚未確定，或者流體流動(dòng)方向與我們所研究的問題無關(guān)時(shí)，網(wǎng)絡(luò)分支 可寫成禪Vi,Vj.,也可寫成ek - V

3、j,v，圖g稱為無向圖。7. 關(guān)聯(lián):在圖G =（VE）中，如果節(jié)點(diǎn)Vi是分支ek的一個(gè)節(jié)點(diǎn)，則稱分支ek和節(jié)點(diǎn)Vi相關(guān)聯(lián)。8. 鄰接:對(duì)于節(jié)點(diǎn)Vi和Vj ,若Vi，Vj ： E，則稱vi和Vj是鄰接的。9子圖;對(duì)圖G = V, E和G = V , E來說，若有V V和E E ,則稱圖G 是 G的一個(gè)子圖。10.出度:對(duì)有向圖G = V，E，定義：E v =爪=Vi,VjE其中，Ek表示以比為始節(jié)點(diǎn)的有向分支的集合，稱做Vi節(jié)點(diǎn)的出邊，出邊數(shù)稱為節(jié)點(diǎn)的出度，用i表示。11.真子圖：對(duì)圖G = V,E和G二V,E來說，若V V或E E，則稱G圖是G 的一個(gè)真子圖。12.入度：對(duì)有向圖G=ME ），

4、定義：EW ）上j ej, -（VjN戸EE=Vi）表示以Vi為末節(jié)點(diǎn)的有向分支的集合，稱做Vi節(jié)點(diǎn)的入邊，入邊數(shù)稱為節(jié)點(diǎn)的入度，13.出鄰點(diǎn)：用E飛V表示。定義有向圖中當(dāng)Vi分別為始末節(jié)點(diǎn)時(shí)與 Vi相鄰接的節(jié)點(diǎn)集合： V）Vj(Vi,Vj 忙 e將V M稱做節(jié)點(diǎn)W的出鄰點(diǎn)。14. 入鄰點(diǎn)：定義有向圖中當(dāng) V分別為始末節(jié)點(diǎn)時(shí)與 Vi相鄰接的節(jié)點(diǎn)集合：V_Vi E VW稱做節(jié)點(diǎn)Vi的入鄰點(diǎn)。15. 并聯(lián)分支：在有向圖G =（V，E）中，如果q二Vi，Vj - E, ej二V,Vj . E，則稱ej和q為并聯(lián) 分支。16. 串聯(lián)分支：在有向圖G =（V，E）中，如果ej = Vi，Vj E，即二V

5、jM E，并且E（V ） = 2e ej ，則稱ej和ejk為聯(lián)分支。17. 源點(diǎn)：在有向圖G = V,E中，將入度為o的節(jié)點(diǎn)稱為網(wǎng)絡(luò)的源點(diǎn)，源點(diǎn)的集合用V G表示。18. 余樹：已知一連通圖G = V,E，Gt = V Gt ,Etg是一樹型圖，如果V Et =V則稱圖Gt = V，Et是圖G = V,E的一棵生成樹。將圖 v，E_Et稱為樹的余樹，記作T。19.樹支；樹T中的分支稱為樹支，樹支集合記為Et。20.余支：余樹中的分支稱為余支，余支集合記為El。21. 平面網(wǎng)絡(luò)圖：如果網(wǎng)絡(luò)圖G能夠畫在平面S上，且除節(jié)點(diǎn)處之外任何兩條分支均不相交,則稱圖G為平面網(wǎng)絡(luò)圖。22. 柱面網(wǎng)絡(luò)圖：如果一

6、個(gè)非平面網(wǎng)絡(luò)圖可以被嵌入在柱面上，稱其為柱面網(wǎng)絡(luò)圖。23. 最大平面圖：設(shè)圖 G是無并聯(lián)分支的平面圖，Vi，Vj是不相鄰的任意兩節(jié)點(diǎn)，若不能在Vi ,Vj間增加1條分支而不破壞圖的平面性時(shí)，則稱圖G是最大平面圖。24. 生成樹：已知一連通圖 G hV,E，Gt FV Gt ,EtG是一樹型圖，如果V Et二V則稱圖Gt二V,Et是圖G二V,E的一棵生成樹。25. 路徑：已知 G =（V,E ）, m = V，n = E，G= （V；E）, m= V，E，GW G， 對(duì)E 和V 進(jìn)行適當(dāng)?shù)恼闻判蚝?，如果下式成立EE1,E2,Ei,En?口 G二 V 1,V2 , V2,V3 , Vi,V i

7、1 , Vn,Vn 1則稱八為路徑。26. 通路：如果G二V,E是有向圖，并有下式成立：EE 1, E【2,E【i,En?二 1,V 2 , V 2,V 3 , Vi,V i 1廠，V n ,V n 1 ?則稱子圖G為通路。27. 回路：始末節(jié)點(diǎn)重合的路徑構(gòu)成一回路。28. 連通圖：若圖G = （V ,E）中的兩節(jié)點(diǎn)Vj和vj之間至少存在一條路徑，則稱vi和vj是連通的。如果圖G的任意兩節(jié)點(diǎn)都是連通的，則稱圖 G是連通圖。29. 節(jié)點(diǎn)的度：對(duì)無向圖 G =（V, E）,定義：E（Vi ）= 可=（Vi，Vj） E,Vi E V,Vj V,其中，E Vi表示與y關(guān)聯(lián)的分支集合，叫做節(jié)點(diǎn)的關(guān)聯(lián)分支

8、，關(guān)聯(lián)分支數(shù)稱為節(jié)點(diǎn)的度,用E（vJ表示;簡答：1. 簡述樹的基本性質(zhì)。對(duì)于圖G=（V,E）， V=m， E=n，下面5個(gè)命題是相互等價(jià)的：（1）G是樹；（2）G的任意兩節(jié)點(diǎn)間有且僅有一條路徑；（3）G不含回路，有m -1條分支；（4）G是連通的且有 m-1條分支；（5）G是無回路的圖，但在 G中的任意兩節(jié)點(diǎn)間增加一條分支有且僅有一條回路。 推論1-1 :設(shè)G是樹，且G的節(jié)點(diǎn)數(shù)2,貝U G中至少有兩個(gè)節(jié)點(diǎn)的度等于 1。 推論1-2：圖G有生成樹的充分必要條件是 G為連通圖。2. 寫出右圖中的全部通路和獨(dú)立通路。其全部通路共有8條，分別如下：R 二總 ； R =仏,e5,e5,e3；1尹/ R3

9、 = $(5,6 ?；巳二 G,e4,e2,e3h.c I y qR5 = , a ,eg 6 f ；i1”-wLjd16 - *0 , e4 , e5 , e9 p?；R7亠色金但?；R8 - O,e8,e9而其獨(dú)立通路為：rJgg h R2，色，邑, ； P3=E,e5，色hR4 = e7,e4,e2,e3;l5 - e7, e8 , e9 P。共有5個(gè)，在獨(dú)立通路中帶下劃線的分支表示前面通路所沒有出現(xiàn)過的分支3已知：圖G=( V，E)，|V|=m，|E|=n。若生成樹為 T ,分別寫出|T|， 獨(dú)立通路個(gè)數(shù)，基本回路個(gè)數(shù)，基本割集個(gè)數(shù)及送|E(Vj p。Vj tVm-1, n-m+2,

10、n-m+1, m-1,2n第二章 流體網(wǎng)絡(luò)圖的矩陣表示 名詞解釋1. 節(jié)點(diǎn)鄰接矩陣：對(duì)無向圖G = (V, E)， V = w ,，Vm，E = ei ,e2 / ,en ，構(gòu)造 m = V階方陣A =(aj)m%，其中aj = . e) = W ,vj e E，稱矩陣A是圖G的節(jié)點(diǎn)鄰 接矩陣。2. 基本回路矩陣：將滿秩的回路矩陣稱為基本回路矩陣。3. 割集：設(shè)G=(V,E)是連通圖，S E，G-S是非連通圖，E是S的真子集E S。 如果G - E 是連通圖，則稱 S是圖G的一個(gè)割集。4. 基本割集：T是有向連通圖G的樹，是T的任一樹支，對(duì)應(yīng)于e有一有向割集S,S不含有除 8以外別的樹支，而且

11、使得它的方向與e,一致，這樣得一組割集 S1 S2;； Sm-1稱為基本割集。5. 基本關(guān)聯(lián)矩陣：圖G = (V,E),m = V , n = E。B是G的完全關(guān)聯(lián)矩陣，則 B的秩 rank B二m -1。從圖G的關(guān)聯(lián)矩陣B中，去掉與節(jié)點(diǎn)vk對(duì)應(yīng)的一行，得行向量線性無 關(guān)的m -1 n的矩陣B%，稱BVk為對(duì)應(yīng)于節(jié)點(diǎn)vk的基本關(guān)聯(lián)矩陣。6、有向圖的完全關(guān)聯(lián)矩陣：有向圖G =（V,E）, V二Mm, E =久僉,en ?,m = V , n = E ,構(gòu)造一個(gè)節(jié)點(diǎn)和分支相互連接的矩陣8 = （bj味刈，其中1,=（w,Vk 廬 E ；bj =-1,=（Vk,y 廬 E ；0, （ViM嚴(yán) E）稱

12、B為有向圖G的完全關(guān)聯(lián)矩陣。7、 有向圖的完全回路矩陣：對(duì)于有向網(wǎng)路圖 G=（V,E），V w,V2,，Vm?，E =仏，曳, , m = V ， n = E ,用矩陣表示的s個(gè)回路為C = （q人妙。其中,1,給w Ci，且同向）Cj = * 一1, w Ci，但反向）.0,（e Ci .8、割集矩陣：設(shè)S1,S2/Sk是圖G=（V,E）的割集，矩陣S=（Sj）“，其中1, （ejSi,且同向；S = “ -1, （ej e S,但反向）0,世Si .則稱S為割集矩陣。9、 基本割集矩陣：基本割集S1,S2,，Smd對(duì)應(yīng)的割集矩陣稱為基本割集矩陣Sf。10、通路矩陣：流體網(wǎng)絡(luò)G =：V,E之

13、源點(diǎn)V G與匯點(diǎn)V G之間的全部通路R,P2,，PS（ s為網(wǎng)絡(luò)的全部通路數(shù)）的矩陣表示是P=（pj s輸，其中1, jR）；Pj P，（ej 更 P ）.2.簡答題1. 流體絡(luò)圖用矩陣表示時(shí)，常用的矩陣有哪些？寫出各矩陣中元素的表達(dá)式（定義式）1）節(jié)點(diǎn)鄰接矩陣 A = （aj人冊(cè)的元素是：aj = S = g ,Vj W E2）關(guān)聯(lián)矩陣與基本關(guān)聯(lián)矩陣。完全關(guān)聯(lián)矩陣 B= （bj）mn1,6 =M，Vk 廬 E ；$ =* -1, =(Vk,w )乏 E )0,Vi,vJ更 E .從圖G的關(guān)聯(lián)矩陣b中，去掉與節(jié)點(diǎn)Vk對(duì)應(yīng)的一行，得行向量線性無關(guān)的 m-1 n的矩陣Bv ,稱Bv為對(duì)應(yīng)于節(jié)點(diǎn)Vk

14、的基本關(guān)聯(lián)矩陣。vkVk3)回路矩陣與基本回路矩陣。用矩陣表示的S個(gè)回路為C = (q人n。其中，1,乏G,且同向；q = -1, ej C,，但反向；稱C為有向圖G的完全回路矩陣。將滿秩的回路矩陣稱.0,芒 G )為基本回路矩陣，有時(shí)也簡稱回路矩陣。4)割集矩陣與基本割集矩陣。設(shè)S1,S2/ ,Sk是圖G=(V,E)的割集，矩陣” 1, (ejSj,且同向)S =(Sij )k呦，其中. 1,j e s,但反向)則稱S為割集矩陣，基本割集0,6 更 s)S,S2,，Sm對(duì)應(yīng)的割集矩陣稱為基本割集矩陣 Sf。T是有向連通圖G的樹，e是T的 任一樹支，對(duì)應(yīng)于e有一有向割集s,s不含有除e以外別的

15、樹支，而且使得它的方向與 e 致，這樣得一組割集 S1,S2/ ,Sm稱為基本割集。5)通路矩陣。s：n，其中P=0GPi)；(ej P).2、簡述關(guān)聯(lián)矩陣的性質(zhì)。關(guān)聯(lián)矩陣性質(zhì)如下：(1 )每一列有2個(gè)非0元素，分別為+1和-1，從列中得知每條分支聯(lián)接在那兩個(gè)節(jié)點(diǎn)上，并 有關(guān)系式：bij bkj =1-1=0, q 二 Vj,VkE(2)從B的行可知網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的出邊和入邊，并有關(guān)n遲 4 = E% i (bj =0= (v m 盧 E ；yn遼 _bj = Ep h 山 VO, =(Vk,w 盧 E ；j2nZbj=|e+(w +E(Vi)=E(Vj|)(ej=(Vi,Vk)EEj 4計(jì)

16、算題1對(duì)于圖1所示的網(wǎng)絡(luò)圖。(1) 寫出節(jié)點(diǎn)鄰接矩陣 A;(2) 寫出基本關(guān)聯(lián)矩陣 B;(3 )禾9用節(jié)點(diǎn)鄰接矩陣計(jì)算 VL V6的通路總數(shù)；(4)利用U矩陣展開法確定vlv6的全部通路;(5 )求以分支編號(hào)為權(quán)的最小樹；(6 )寫出基于所求最小樹的基本回路矩陣C。(7 )寫出基于所求最小樹的基本割集矩陣So圖1z010000 001100(1)A =000110000010000001000000丿m-1 W 二 a1m 二 3k1 0 0 0 0 0 0-1110000 B6 = 0 -1 0 110 00 0 -1 0 -11 02 0 0-1 0 -11(4)U = Ae I 二1 0

17、 0 0 00 1 e，es 0 0001e5e400001000001ey000001U6,1= eie2e4 e7 e1e2e5e6e7 e1e3e6e7(5)加邊法 T=e1,e2,e3,e4,e7e1e2 e3e4e5 e6e7C1 _0C =I1-101001C2000-1110 一e1e2e3e4e5e6e7S1 -10000001S20100-110(7) S = S300101-10S40001010S5 0000001 _第三章排序與搜索一名詞解釋1、著色:所謂分支著色就是對(duì)分支做標(biāo)記。2. 尋邊尋邊就是在未被著色的分支集合E中搜尋始節(jié)點(diǎn)為va的分支。二簡答題1、常用的排序方

18、法有哪些？氣泡排序、選擇排序、插入排序、shell排序、快速排序2、簡述對(duì)排序效率的評(píng)價(jià)包括哪些方面？3、平均情況下的速度；(1) 最好和最壞情況下的速度；(2) 算法是否正態(tài)；(3) 對(duì)權(quán)重相同的分支是否重新排列。3、簡述寬度優(yōu)先搜索與深度優(yōu)先搜索的不同點(diǎn)1) 尋邊確定的分支是按隊(duì)列方式進(jìn)行存儲(chǔ)，而不是按堆棧方式進(jìn)行存儲(chǔ)；2) 深度優(yōu)先搜索的尋邊是將一個(gè)滿足尋邊條件的分支壓入堆棧，而寬度優(yōu)先搜索的尋邊是 將所有滿足搜索條件的分支順序壓入堆棧中，執(zhí)行先進(jìn)先出，后進(jìn)后出的原則。3) 深度優(yōu)先搜索堆棧存儲(chǔ)的是搜索起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的一條路徑，而寬度優(yōu)先搜索隊(duì)列 儲(chǔ)器記錄的則不是路徑。三、計(jì)算題1、

19、寫出用深度優(yōu)先搜索法(DFS)確定圖1中v1iV6的全部通路的過程。圖11、序 號(hào)Vaek =(Va,Vb) E E進(jìn)退棧棧P著色分支搜 索1v1e1pushe1e1e12v2e2pushe1,e2e1,e2e23v3e4pushe1,e2,e4e1,e2,e4e44v5e7pushe1,e2,e4,e7e1,e2,e4,e7e75v6(V6,Vb)更 Epope1,e2,e4e1,e2,e4,e7e76v5(V5,Vb)更 Epope1,e2e1,e2,e4,e7e47v3e5pushe1,e2,e5e1,e2,e4,e7,e5e58v4e6pushe1,e2,e5,e6e1,e2,e4,e

20、7,e5,e6e69v5e7pushe1,e2,e5,e6,e7e1,e2,e4,e7,e5,e6,e7e710v6(V6M)更 Epope1,e2,e5,e6e1,e2,e4,e7,e5,e6,e7e711v5MM)芒 Epope1,e2,e5e1,e2,e4,e7,e5,e6,e7e611v4Zb)更 Epope1,e2e1,e2,e4,e7,e5,e6,e7e512v3Mm)更 Epope1e1,e2,e4,e7,e5,e6,e7e213v2e3pushe1,e3e1,e2,e4,e7,e5,e6,e7,e3e314v4e6pushe1,e3,e6e1,e2,e4,e7,e5,e6,e7

21、,e3,e6e615v5e7pushe1,e3,e6,e7e1,e2,e4,e7,e5,e6,e7,e3,e6,e7e716v6(V6,vJ 更 E所求通路如表中下劃線所示。第四章連通圖、最小樹、回路、生成樹的算法1名詞解釋1最小樹如果給連通圖的各分支賦予某種權(quán)重，那末樹枝總權(quán)重最小的樹叫做最小樹。2、邊割設(shè)S V是圖G = V,E中的節(jié)點(diǎn)集合V的一個(gè)非空子集，S二V S，是S的補(bǔ)集，節(jié)點(diǎn)V便分成s和S兩個(gè)部分，對(duì)于一個(gè)節(jié)點(diǎn)屬于S而另一個(gè)節(jié)點(diǎn)屬于 S的所有分支的集合稱為邊割，用Q表示Q = $ q m：Vj,Vj ,vS,vr Sz3、子圖多項(xiàng)式為了說明該方法先引進(jìn)子圖多項(xiàng)式的概念，對(duì)于某一子

22、圖Gs,定義子圖多項(xiàng)式如下：nPSa262 亠 亠 anen = ae其中系數(shù)1 (e, EG)a = 即是路徑Pi的分支，也是路徑 P的分支，即Va, Vb Pi* Pj，把路徑中的分支按由 Z 到Z的連接順序賦給方向，如果 Va, Vb Pi，而Vb,Va Pj，那末分支Va, Vb 是角聯(lián)分支。2 簡答題1子網(wǎng)與子圖間有何區(qū)別？子網(wǎng)與子圖在本書有不同的含義，子圖是由圖中的任意一部分分支組成，分支數(shù)量可以是1;而子網(wǎng)則必須是連通的子圖，除了分支數(shù)要大于等于 2以外，還要滿足去掉子網(wǎng)后的網(wǎng)絡(luò)與 子網(wǎng)有而且必須僅有兩個(gè)交點(diǎn)。2、寫出角聯(lián)分支七元組。如圖所示。圖中，O是節(jié)點(diǎn)集合，表示有任意多個(gè)節(jié)

23、點(diǎn)，也可以是0個(gè)。通常把角聯(lián)結(jié)構(gòu)寫成：日=（pl,Pr,Pd，z,z,3,3 ）3、簡述網(wǎng)絡(luò)簡化的意義。網(wǎng)絡(luò)自動(dòng)簡化技術(shù)是分析流體網(wǎng)絡(luò)的強(qiáng)有利工具。網(wǎng)絡(luò)簡化對(duì)提高計(jì)算程序的運(yùn)算速度以及降低計(jì)算機(jī)內(nèi)存占有量也具有重要意義。在流體網(wǎng)絡(luò)分流按需調(diào)節(jié)通路法、計(jì)算機(jī)自動(dòng)識(shí)別角聯(lián)結(jié)構(gòu)等方面都涉及到通路的計(jì)算問題，有時(shí)分支增加1條有可能導(dǎo)致通路總數(shù)的成倍增加，所以對(duì)網(wǎng)絡(luò)進(jìn)行自動(dòng)簡化處理具有非常重要的意義。4、簡述流體網(wǎng)絡(luò)中常見的網(wǎng)絡(luò)優(yōu)化問題。最短路、極值流、最小樹。3計(jì)算題1、對(duì)于圖所示的流體網(wǎng)絡(luò)圖，寫出網(wǎng)絡(luò)簡化的過程。1第一層：并聯(lián)P 比弘占,* ； P v1o,v1e16,e17 ?第二層：串聯(lián)S Vs

24、,v7 二：P V5,V6 .eg?第三層：角聯(lián)D Vg,V13 = 02,G3,G4,G5,P V10.V12，気，!； D V? “金(4 忌忌第四層：串聯(lián)S V2,V7 =01,D Vg,V13，屛；S V2.V7 = D V2.V5 ,S V5.V7 /第五層：并聯(lián)P V2 . V7 = lS V2 . V7 . S V2 . V7 f第六層：串聯(lián)S V1,V8 ie,P V2.V72、女口圖所示的流體網(wǎng)絡(luò)，寫出確定角聯(lián)分支、角聯(lián)結(jié)構(gòu)的過程。 角聯(lián)結(jié)構(gòu)1：e2,e4, e3,e7,e6,e9, e5, v2,v7,v3,v5角聯(lián)拮構(gòu)2：e2,e4, e3,e8,eg, e5, e6,

25、v2,v7,v3, v6角聯(lián)結(jié)構(gòu)3：e2,e54e6, e3,e86(e7, v2,v6, v4, v58、9/t6 / / wJ3Y2-13、010000、001100已知節(jié)點(diǎn)鄰接矩陣 A =00011000001000000110000(1)(2)第十一章流1、 名1、靈敏度當(dāng)某支路支i的流量IE R 0流量q,變e7ese3e2e2,e4 ,e3,e6,e5,v3,v4,v2,v5 體網(wǎng)絡(luò)的靈敏性與可靠性分析詞解釋的流阻 打發(fā)生訂j的變化時(shí)，網(wǎng)絡(luò)中任一分值q,也相應(yīng)地發(fā)生一個(gè)土qi的變化，當(dāng)時(shí):d帕弋弓即為分支的化相對(duì)于分支 j的流阻變化的靈敏度。(1) 畫出對(duì)應(yīng)的流體網(wǎng)絡(luò)圖；(2) 確定網(wǎng)絡(luò)中的角