1、第一章 流体网络的基本概念与拓扑关系 名词解释 : 1.流体网络 : 无论是矿井的通风系统（包括有风流流动的井巷通道、调节风量分配用的构筑物、作为通风动力的风机等等），还是城市集中供热系统（包括输送管路、各种调节阀门、作为动力的泵站等等），以及城市煤气输送系统、自来水供应系统、集中空调系统等各种有流体流动的管路系统，它们都有一共同的特点，那就是它们都是由输送流体的管路、各种调节设施及动力设施构成，流体管路连接在一起形成流体网络。 2. 分支 : 抛开流体网络的各种属性，只考虑流体管路的几何连接拓扑关系。为此，将管路 称之为分支 。 3. 节点 : 三条以上分支的连接点称之为节点 ； 有时为研究
2、问题方便，将管路的某种属性的交变点也称为节点，也就是说两条物理属性不同的分支的交点也称之为节点；还有一类分支，其一端与其他分支相连接，而另一端是自由的，不与任何分支相连接，将这类端点也称为节点。 4. 图 : 将流体网络中的节点和分支的集合称为图，记为 ),( EVG ， 式中， V 表示节点的集合， mvvvV , 21 ， m 为节 点数， Vm ； E 表示分支集合， neeeE , 21 ， n 为分支数， En 5.有向图 : 分支 ke 对应着的两个节点分别为 iv 和 jv 。当流体流动的方向是 ji vv ，此时将分支 ke 写成 jik vve , ，图 G 称为有向图 6.
3、 无向图 : 当流体流动方向尚未确定，或者流体流动方向与我们所研究的问题无关时，网络分支 ke 即可写成 jik vve , ，也可写成 ijk vve , ，图 G 称为无向图。 7. 关联 : 在图 ),( EVG 中，如果节点 iv 是分支 ke 的一个节点，则称分支 ke 和节点 iv 相关联 。 8. 邻接 : 对于节点 iv 和 jv ，若 Evv ji , ，则称 iv 和 jv 是邻接的。 9 子图； 对图 EVG , 和 EVG , 来说，若有 VV 和 EE ，则称图 G 是 G 的一个子图 。 10. 出度： 对有向图 EVG , ，定义： EvveevE jiijiji
4、 ,， 其中， ivE 表示以 iv 为始节点的有向分支的集合，称做 iv 节点的出边，出边数称为节点的出度，用 ivE 表示。 11. 真子图：对图 EVG , 和 EVG , 来说，若 VV 或 EE ，则称 G 图是 G 的一个真子图。 12. 入度：对有向图 EVG , ，定义： EvveevE ijjijii ,， ivE 表示以 iv 为末节点的有向分支的集合，称做 iv 节点的入边，入边数称为节点的入度，用 ivE 表示。 13. 出邻点 ： 定义有向图中当 iv 分别为始末节点时与 iv 相邻接的节点集合： EvvvvV jiji ,，将 ivV 称做节点 iv 的出邻点。 1
5、4. 入邻点：定义有向图中当 iv 分别为始末节点时与 iv 相邻接的节点集合： EvvvvV ijji ,， ivV 称做节点 iv 的入邻点。 15. 并联分支： 在有向图 ),( EVG 中，如果 Evve jiij , ， Evve jiij , ，则称 ije 和 ije 为并联分支 。 16. 串联分支：在有向图 ),( EVG 中，如果 Evve jiij , ， Evve kjjk , ，并且 2jvE ，则称 ije 和 jke 为 联分支。 17. 源点 :在有向图 EVG , 中，将入度为 0的节点称为网络的源点，源点的集合用 GV 表示 。 18. 余树：已知一连通图
6、EVG , ， GEGVG TTT , 是一树型图，如果 VEV T 则称图 TT EVG , 是图 EVG , 的一棵生成树。将图 TEEV , 称为树的余树，记作 T 。 19. 树支； 树 T 中的分支称为树支，树支集合记为 TE 。 20. 余支：余树中的分支称为余支，余支集合记为 LE 。 21. 平面网络图：如果网络图 G 能够画在平面 S 上，且除节点处之外任何两条分支均不相交，则称图 G 为平面网络图。 22. 柱面 网络 图：如果一个非平面网络图可以被嵌入在柱面上，称其为柱面网络图。 23. 最大平面图：设图 G 是无并联分支的平面图， ji vv, 是不相邻的任意两节点，若
7、不能在ji vv, 间增加 1条分支而不破坏图的平面性时，则称图 G 是最大平面图。 24.生成树： 已知一连通图 EVG , ， GEGVG TTT , 是一树型图，如果 VEV T 则称图 TT EVG , 是图 EVG , 的一棵生成树。 25.路径：已知 EVG , ， Vm ， En ， EVG , ， Vm ， En ， GG ，对 E 和 V 进行适当的整形排序后，如果下式成立 1,1,3,2,2,1 ,2,1 nVnViViVVVVV nEiEEEE 则称子图 G为路径。 26.通路： 如果 EVG , 是有向图，并有下式成立： 1,1,3,2,2,1 ,2,1 nVnViVi
8、VVVVV nEiEEEE 则称子图 G 为通路。 27.回路： 始末节点重合的路径构成一回路。 28.连通图： 若图 ),( EVG 中的两节点 iv 和 jv 之间至少存在一条路径，则称 iv 和 jv 是连通的。如果图G 的任意两节点都是连通的，则称图 G 是连通图。 29.节点的度 :对无向图 EVG , ，定义： VvVvEvveevEjijiijiji ,其中， ivE 表示与 iv 关联的分支集合，叫做节点的关联分支，关联分支数称为节点的 度，用 ivE 表示 ； 简答： 1. 简述树的基本性质。 对于图 ),( EVG ， mV ， nE ，下面 5 个命题是相互等价的： （
9、1） G 是树； （ 2） G 的任意两节点间有且仅有一条路径； （ 3） G 不含回路，有 1m 条分支； （ 4） G 是连通的且有 1m 条分支； （ 5） G 是无回路的图，但在 G 中的任意两节点间增加一条分支有且仅有一条回路。 推论 1-1： 设 G 是树，且 G 的节点数 2，则 G 中至少有两个节点的度等于 1。 推论 1-2：图 G 有生成树的充分必要条件是 G 为连通图。 2.写出右图中的全部通路和独立通路。 其全部通路共有 8 条，分别如下： 3211 , eeeP ； 36512 , eeeeP ； 9513 , eeeP ； 32474 , eeeeP ； 36547
10、5 , eeeeeP ； 95476 , eeeeP ； 36877 , eeeeP ； 9878 , eeeP 。 而其独立通路为： 3211 , eeeP ； 36512 , eeeeP ； 9513 , eeeP ； 32474 , eeeeP ； 9875 , eeeP 。共有 5 个，在独立通路中带下划线的分支表示前面通路所没有出现过的分支 3 已知：图 G=（ V， E）， |V|=m， |E|=n。若生成树为 T，分别写出 |T|， 独立通路个数，基本回路个数，基本割集个数 及 Vv ii vE。 m-1, n-m+2, n-m+1, m-1, 2n 第二章 流体网络图的矩阵表示
11、 名词解释 1. 节点邻接矩阵 :对无向图 ),( EVG ， mvvvV , 21 ， neeeE , 21 ，构造Vm 阶方阵 mmija )(A ，其中 Evveea jikkij ,，称矩阵 A 是图 G 的节点邻接矩阵。 2. 基本回路矩阵 :将满秩的回路矩阵称为基本回路矩阵。 3. 割集 : 设 ),( EVG 是连通图， ES ， SG 是非连通图， E 是 S 的真子集 SE 。如果 EG 是连通图，则称 S 是图 G 的一个割集。 4.基本割集 : T是有向连通图 G的树， ie 是 T 的任一树支，对应于 ie 有一有向割集 S,S不含有除ei以外别的树支，而且使得它的方向
12、与 ei一致，这样得一组割集 S1 S2； Sm-1称为基本割集。 5.基本关联矩阵 :图 EnVmEVG ,),( 。 B 是 G 的完全关联矩阵，则 B 的秩 1 mrank B 。 从图 G 的关联矩阵 B 中，去掉与节点 kv 对应的一行，得行向量线性无关的 nm 1 的矩阵kvB，称kvB为对应于节点 kv 的基本关联矩阵。 6、 有向图的完全关联矩阵 :有向图 ),( EVG ， mvvvV , 21 ， neeeE , 21 ，Vm ， En ，构造一个节点和 分支 相互连接的矩阵 nmijb )(B ，其中 .,0;,1;,1EvvEvveEvvebkiikjkijij 称 B
13、 为有向图 G 的完全关联矩阵。 7、有向图的完全回路矩阵 :对于有向网路图 ),( EVG ， mvvvV , 21 ， neeeE , 21 , Vm ， En ，用矩阵表示的 s 个回路为 nsijc )(C 。其中， .,0;,1;,1ijijijijCeCeCec ，但反向，且同向8、割集矩阵 :设 kSSS , 21 是图 ),( EVG 的割集，矩阵 mkijs )(S ，其中 .,0;,1;,1ijijijijSeSeSes 但反向且同向则称 S 为割集矩阵 。 9、基本割集矩阵 :基本割集 121 , mSSS 对应的割集矩阵称为基本割集矩阵 fS 。 10、通路矩阵 :流体
14、网络 EVG , 之源点 GV 与汇点 GV 之间的全部通路sPPP , 21 （ s 为网络的全部通路数）的矩阵表示是 nsijp P ，其中 ).(,0 );(,1ijijij Pe Pep 2. 简答题 1. 流体络图用矩阵表示时，常用的矩阵有哪些？写出各矩阵中元素的表达式（定义式）。 1）节点邻接矩阵 mmija )(A 的元素是： Evveeajikkij ,2）关联矩阵与基本关联矩阵。完全关联矩阵 nmijb )(B 。 .,0;,1;,1EvvEvveEvvebkiikjkijij从图 G 的关联矩阵 B中，去掉与节点 kv 对应的一行，得行向量线性无关的 nm 1 的矩阵kvB
15、，称kvB为对应于节点 kv 的基本关联矩阵。 3）回路矩阵与基本回路矩阵。用矩阵表示的 s个回路为 nsijc )(C 。其中， .,0;,1;,1ijijijijCeCeCec ，但反向，且同向称 C为有 向图 G的完全回路矩阵。将满秩的回路矩阵称为基本回路矩阵，有时也简称回路矩阵。 4）割集矩阵与基本割集矩阵。设 kSSS , 21 是图 ),( EVG 的割集，矩阵mkijs )(S ，其中 .,0;,1;,1ijijijijSeSeSes 但反向且同向则称 S 为割集矩阵，基本割集121 , mSSS 对应的割集矩阵称为基本割集矩阵 fS 。 T 是有向连通图 G 的树， ie 是
16、T 的任一树支，对应于 ie 有一有向割集 S ,S 不含有除 ie 以外别的树支，而且使得它的方向与 ie 一致，这样得一组割集 121 , mSSS 称为基本割集。 5) 通路矩阵。 nsijp P，其中 ).(,0 );(,1ijijij Pe Pep 2、 简述关联矩阵的性质 。 关联矩阵性质如下： （ 1）每一列有 2个非 0元素，分别为 +1和 -1，从列中得知每条分支联接在那两个节点上，并有关系式： Evvebb kijkjij ,011 （ 2）从 B 的行可知网络中的每个节点的出边和入边，并有关 njkijiiiijnjikjijiijnjkijijiijEvvevEvEvE
17、bEvvebvEbEvvebvEb111.,;,0,;,0,计算题 1、对于图 1 所示的网络图。 （ 1）写出节点邻接矩阵 A； （ 2）写出基本关联矩阵 B； （ 3）利用节点邻接矩阵计算 v1 v6 的通路总数； （ 4）利用 U 矩阵展开法确定 v1 v6 的全部通路； （ 5）求以分支编号为权的最小树； （ 6）写出基于所求最小树的基本回路矩阵 C。 （ 7）写出基于所求最小树的基本割集矩阵 S。 图 1 (1)000000100000010000011000001100000010A(2)11-01-000011-01-00001101-00000111-00000016B (3)
18、311 1 mk kmaw v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 (4)100000100000100001000010000017645321eeeeeeeIAU e76317652174211,6 eeeeeeeeeeeeeu (5)加边法 T=e1,e2,e3,e4,e7 (6) 76543210111000001011021 eeeeeeeCCC (7) 76543211000000010100001101000110010000000154321eeeeeeeSSSSSS第三章排序与搜索 一 名词解释 1、着色 ： 所谓分支着色就是对分支做标记
19、 。 2寻边 寻边就是在未被着色的分支集合 E 中搜寻始节点为 va 的分支。 二 简答题 1、常用的排序方法有哪些？ 气泡排序、选择排序、插入排序、 shell 排序、快速排序 2、 简述对排序效率的评价包括 哪些方面？ 3、 平均情况下的速度； (1)最好和最坏情况下的速度； (2)算法是否正态； (3)对权重相同的分支是否重新排列。 3、 简述宽度优先搜索与深度优先搜索的不同点 1）寻边确定的分支是按队列方式进行存储，而不是按堆栈方式进行存储； 2）深度优先搜索的寻边是将一个满足寻边条件的分支压入堆栈，而宽度优先搜索的寻边是将所有满足搜索条件的分支顺序压入堆栈中，执行先进先出，后进后出的
20、原则。 3）深度优先搜索堆栈存储的是搜索起始节点到当前节点的一条路径，而宽度优先搜索队列储器记录的则不是路径。 三、计算题 1、写出 用深度优先搜索法（ DFS）确定图 1 中 v1 v6 的全部通路的过程。 图 1 1、 序号 av Evve bak ),(进退栈 栈 P 着色分支 搜索 1 v1 e1 push e1 e1 e1 2 v2 e2 push e1,e2 e1,e2 e2 3 v3 e4 push e1,e2,e4 e1,e2,e4 e4 4 v5 e7 push e1,e2,e4,e7 e1,e2,e4,e7 e7 5 v6 Evv b ),( 6 pop e1,e2,e4
21、e1,e2,e4,e7 e7 6 v5 Evv b ),( 5 pop e1,e2 e1,e2,e4,e7 e4 7 v3 e5 push e1,e2,e5 e1,e2,e4,e7,e5 e5 8 v4 e6 push e1,e2,e5,e6 e1,e2,e4,e7,e5,e6 e6 9 v5 e7 push e1,e2,e5,e6,e7 e1,e2,e4,e7,e5,e6,e7 e7 10 v6 Evvb ),( 6 pop e1,e2,e5,e6 e1,e2,e4,e7,e5,e6,e7 e7 11 v5 Evvb ),( 5 pop e1,e2,e5 e1,e2,e4,e7,e5,e6,
22、e7 e6 11 v4 Evvb ),( 4 pop e1,e2 e1,e2,e4,e7,e5,e6,e7 e5 12 v3 Evvb ),( 3 pop e1 e1,e2,e4,e7,e5,e6,e7 e2 13 v2 e3 push e1,e3 e1,e2,e4,e7,e5,e6,e7,e3 e3 14 v4 e6 push e1,e3,e6 e1,e2,e4,e7,e5,e6,e7,e3,e6 e6 15 v5 e7 push e1,e3,e6,e7 e1,e2,e4,e7,e5,e6,e7,e3,e6,e7 e7 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6
23、e7 16 v6 Evv b ),( 6 所求通路如表中下划线所示。 第四章连通图、最小树、回路、生成树的算法 1、名词解释 1、最小树 如果给连通图的各分支赋予某种权重，那末树枝总权重最小的树叫做最小树。 2、边割 设 VS 是图 EVG , 中的节点集合 V 的一个非空子集， SVS ，是 S 的补集，节点 V 便分成 S 和 S 两个部分，对于一个节点属于 S 而另一个节点属于 S 的所有分支的集合称为边割，用 表示 SvSvvveejijiijij ,3、 子图多项式 为了说明该方法先引进子图多项式的概念，对于某一子图 sG ，定义子图多项式如下： ni iinns eaeaeaeaP
24、 12211 其中系数 .,0 ;,1 其它 sii GEea 2.简答题 1、简述确定最小树的常用算法。 破圈法、边割法、 Kruskal 算法、 Dijkstra 算法。 2.简述破圈法及其适用情况。 破圈法的实质就是在图中任选一回路，然后将回路中权重最大的分支去掉，依此类推直至图中无回路。破圈法适合人工找最小树，程序法中由于涉及到找回路，所以效率不高一般不采用。 3.简述 Kruskal 算法的基本原理。 在图的连通性判别程序中，如果一个分支的两个节点均已存在于同一连通块中，则该分支加入后一定会形成一回路。将形成回路的分支去掉，则剩余的分支将构成最小树。 3计算题 第五章最短路与极值流的算法 1.名词解释 1.单一源汇流体网络 将 1 GVGV 的流体网络 EVG , 称为单一源汇流体网络 。
