下载文档原格式
第六章 离散时间和连续时间模型的仿真§1 状态变量6.1.1 状态变量的基本概念1) 状态变量集计算机仿真中必须搞清楚实体相互关系的规则。
计算机记录描述变量的过去值，根据相互关系规则，可计算描述变量的未来值。
状态变量集是所有描述变量的一个子集，只要知道这些变量的现在值和输入变量值，就可计算模型的所有描述变量未来值。
2）模型完全描述完全描述模型：假设模型具有描述变量n ααα,,,21 ，如果在任一时间t ，变量1α的值为1y ，变量2α的值为2y ，…，若实体的相互关系规则对任一未来时间 t ′（大于 t ）确定了值''2'1,,,ny y y 的唯一集，那么该模型是完全描述的。
模型完全描述的充要条件：如果各描述变量的各个值只在任一时间t 唯一确定所有这些变量在任一未来时间t ′的值，就说描述变量集的某个子集是状态变量集。
如果模型是完全描述的，n ααα,,,21 或它的真子集便是状态变量集。
模型是完全描述的充要条件是该模型的描述变量中存在状态变量集 例：二辆汽车面对而驶，V 1、V 26.1.2 状态变量的仿真性质1） 程序预置假设程序给出计算t ′时的''2'1,,,ny y y 的任务。
则仅需预置（也即是初始化）那些与状态变量有关的存储单元。
2） 重复操作假设给定t 时的n y y y ,,,21 值之后，因为丢失了第一次仿真操作的记录，要重复计算t ′时的''2'1,,,ny y y 值，只要与状态变量有关的单元，预置n y y y ,,,21 的相同值，则在不同计算机和不同时间作两次操作，结果仍然相同。
3） 程序中断和重新起动设计算t ′时的''2'1,,,ny y y 值之后，安排中断程序。
在某时间之后可以重新起动。
4） 程序恢复假设计算机在执行程序时发生事故，修复正常时，重新预置肯定将最终产生相同结果，但比从中断点重新起动要花费更多的时间。
第六章 图与网络图 一、选择1. 在图中用V 表示点，用E 表示边，如果有两个图G 1={V 1,E 1}和图G 2={V 2,E 2},若有V 1⊆V 2 ,E 1⊆ E 2，则称G 1 是G 2的一个（D ）A 偶图B 部分图C 完全图D 子图 2. 3. 在树图中，顶点有v 个，边有e 条，那么顶点和边的数量关系是（B ）A 、v =e B 、e ＝v -1 C 、v ＝e -14. 在图中用V 表示点，用E 表示边，如果有两个图G 1={V 1,E 1}和图G 2={V 2,E 2},若有V 1= V 2 ,E 1⊂ E 2，则称G 1 是G 2的一个（A ）A 部分图B 子图C 二分图5.完全偶图中V 1含m 个顶点，V 2含有n 个顶点，则其边数共（ C ）条。
A m+n B m-n C m ×n D m ÷n6. 任何树中必存在次为（ A ）的点A 1B 2C 3 D4 7．含有n 个顶点的完全图，其边数有（ B ）条。
A nB )1(21-n n C n(n-1) D n-18.具有n 个顶点的树的边数恰好为（A ）条。
A n-1条B n 条C )1(21-n n D n(n-1)9.在网络图中s →t 的最大流量（ C ）它的最小割集的容量。
A 大于 B 小于C 等于 D 无关10. 构成最大流问题的条件之一是（B ）A 、网络有一个始点v sB 、网络有一个始点v s 和一个终点v tC 、网络有一个终点v tD 无要求11. 下图中（C ）是完全二分图A BC D12.下面（D）是最短路问题A课程排序问题B 生产计划问题C 人力资源问题D选址问题13. 求网络图中任意两点之间的最短距离的方法是（C ）A求最小部分树B矩阵算法C Dijkstra算法D 破圈法14.下面（A）是矩阵算法求最短路问题A 小学生选校址问题B课程排序问题C 生产计划问题D 人力资源问题15.下面（A）是最大流问题。
A桥梁问题B设施布局问题C生产计划问题D以上都不是16.二、填空1.在图论中，称(无圈的) 连通图为树。
2.树是无圈连通图中边数最多的，在树图上只要任意再加上一条边，必定会出现（圈）。
3.在图中一般用点表示（研究的对象），用边表示这些（对象的联系）。
4.如果给图中的点和边赋以具体的含义和权数，把这样的图称为（网络图）5. .图G可以定义为点和边的集合，记作（G=[V,E] ）6.在图中，（链）是点可重复，边不可重复的。
7.在图中，（路）是点与边都不可以重复的。
8.如果边e的两个端点相重，称该边为（环）9.对无环、无多重边的图称为（简单图）10.与某一个点v i相关联的边的数目称为点v i的（次）11.对起点与终点相重合的链称为（圈）。
12.若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为（连通图）。
13. 若在一个图中，如果每一对顶点之间至少存在一条（链），称这样的图为连通图。
14.一个简单图中若任意两点之间均有边相连，称这样的图为（完全图）。
15. 一个（简单图）中若任意两点之间均有边相连，称这样的图为完全图。
16.对要研究的问题确定具体对象及这些对象间的性质联系，这就要对研究的问题建立（图的模型）17.（树）是无圈的连通图。
18.在树图中，称次为1的点为（悬挂点）19..如果G1是G2的部分图，又是树图，则称G1是G2的（部分树） 20.树枝总长最小的部分树，称为（最小支撑树）。
21.把图的所有点分成V 和-V 两个集合，则两个集合之间连线的最短边一定包含在（最小部分树）内。
22. (最短路问题)是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。
23.矩阵算法中D （k ）给出网络中任意两点直接到达，经过一个、两个、···，到（2k -1）个中间点时比较得到的最短距离。
24.设网络图有p 个点，则一般计算到不超过D （k ），k 的值按公式（ ），即计算结束。
25. 对图中每条边规定指向的图称为(有向图) 26. 有向图的边称为(弧)，记作(v i , v j )，27. 弧(v i , v j )的最大通过能力，称为该弧的(容量)，记为c(v i , v j ) ，或简记为 c ij 。
28. (流)是指加在网络各条弧上的一组负载量，对加在弧(v i , v j )上的负载量记作 f (v i , v j ) ，或简记作 f ij29. （割）是指将容量网络中的发点和收点分割开，并使s →t 的流中断的一组弧的集合。
30. （割的容量）是组成它的集合中各弧容量之和。
31.如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 s →t 的弧（称前向弧，记作μ+），存在f < c (非饱和)；所有指向为 t →s 的弧（称后向弧，记为μ -），存在f > 0(非零)，这样的链称（增广链）。
32.求网络最大流的方法是（标号算法）33.34.求网络的最大流，是指满足（容量限制条件）和（中间点平衡）的条件下，使)(f v 值达到最大。
三、判断1.图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。
（不正确）2.在任一图G 中，当点集V 确定后，树图是G 中边数最少的连通图。
（正确）3.如图中某点v i有若干个相邻点，与其距离最远的相邻点为vj，则边 [i,j]必不包含在最小支撑树内。
（正确） 4.如图中从v 1至各点均有唯一的最短路，则连接v 1至其他各点的最短路在去掉重复部分后，k p k ≤-<-2lg )1lg(1恰好构成该图的最小支撑树。
（正确）5. Dijkstra 算法提供了从网络图中某一点到其他点的最短距离。
（正确 ）6. 部分图不是子图，子图也不一定是部分图。
（不正确）7.树图的任意两个点之间有一条且仅有一条唯一通路。
（正确）8.一些重要的网络不能按数的结构设计。
（正确）9.. 一个图的最小部分树不唯一。
（正确）10. 不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。
（正确）11. D (k)中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。
（正确） 12.零流不是可行流。
（不正确）13. 在网络中 s →t 的最大流量等于它的最小割集的容量。
（正确） 14. 标号算法其本质是判断是否存在增广链，并找出增广链。
（正确）15.求最小费用流时，一方面通过增广链来调整流量，另一方面要找出每一步费用最小的增广链。
是最大流和最短路问题的综合求解。
（正确）四．名词解释1.环：如果边e 的两个端点相重，称该边为环。
2.多重边 如果两个点之间的边多于一条，称为具有多重边。
3.简单图 无环，无多重边的图称为简单图。
4.次 与某一个点i v 相关联的边的数目称为点i v 的次（也叫做度或线度）。
5.奇点 次为奇数的点称作奇点。
6.偶点 次数为偶数的点称作偶点。
7.孤立点 次数为0的点称作孤立点。
8.链 有些点和边的交替序列μ={}k k v e v e v,,,,,110⋅⋅⋅，若其中各边k e e e ,,,21⋅⋅⋅互不相同，且任意1,-t i v 和it v （k t ≤≤2）均相邻，称μ为链。
9.路 如果链中所有的顶点k v v v ,,,10⋅⋅⋅也不相同，这样的链称为路。
10.圈 对起点与终点相重合的链称作圈。
11.回路 起点与终点重合的路称作回路。
12.连通图 若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。
13.完全图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图。
含有n 个顶 点的完全图，其边数有条)1(212-=n n C n 。
14.偶图 如果图的顶点能分成两 个互不相交的非空集合1V 和2V ，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图）。
15.完全偶图：如果偶图的顶点集合1V ，2V 之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。
完全偶图中1V 含m 个顶点，2V 含n 个顶点，则其边数共m ·n 条。
16.网络图：如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图。
17.端点：若有边e 可表示为[]v v jie ,=,称v i 和v j是边e 的端点。
18.关联边：若有边e 可表示为[]v v j i e ,=，称边e 为点v i 或v j的关联边。
19.点相邻：若点v i，vj与同一条边关联，称点v i和vj相邻。
20.边相邻：若边e i和ej具有公共的端点，称边e i和ej相邻。
21.子图：图EV G 111,=和图EV G 222,=，如果有VV 21⊆和EE 21⊆,称G 1是G2的一个子图。
22.部分图：如果有VV 21=和EE 21⊂,称G 1是G2的一个部分图。
23.图的模型：对要研究的问题确定具体对象及这些对象间的性质联系，并用图的形式表示出来，这就是对研究的问题建立图的模型。
24.树图：是无圈的连通图。
这类图与大自然中数的特征相似，因而得名树图。
25.部分树：如果G 1是G2的部分图，又是树图，则称G 1是G2的部分树。
26.树枝：树图的各条边称为树枝27.最小部分树：假定各边均有权重，一般图G2含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。
28.弧：有向图上的连线是有规定指向的，称作弧。
记作),(v v ji表明方向是从v i 点指向vj点。
29.弧的容量：对网络上的每条弧),(v v ji都给出一个最大的通过能力，称为该弧的容量，简写cij30.网络的最大流：网络中从发点到收点之间允许通过的最大流量。
31.流：加在网络各条弧上的一组负载量。
记fij32.零流：若网络上所有的fij=0，这个流称为零流。
33.割：指将容量网络中的发点和收点分割开，并使t s →的流中断的一组弧的集合。
34．割的容量：是组成它的集合中的各弧的容量之和，用),(-V V c 表示。
35.增广链：如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为 s →t 的弧（称前向弧，记作μ+），存在f < c (非饱和)；所有指向为 t →s 的弧（称后向弧，记为μ-），存在f > 0(非零)，这样的链称增广链。
36.悬挂点：次为1的点为悬挂点。
37.悬挂边：与悬挂点关联的边称为悬挂边。
四、简答 2.2. 一些重要的网络不能按数的结构设计，这是为什么。
