中原工学院运筹学1

河南理工大学博士研究生入学考试
初试《系统工程》考试大纲
一、考试目的
通过考试，了解考生对系统工程主要知识点的掌握情况，以及对知识掌握的扎实程度，通过考试了解考生是否达到河南理工大学博士研究生入学初试的要求。

二、试卷满分及考试时间
试卷满分为100分，考试时间为180分钟。

三、答题方式
答题方式为闭卷、笔试。

四、参考书目
汪应洛，《系统工程》（第4版），机械工业出版社，2011。

五、考试内容
第一章系统工程概述
主要包括系统工程的产生及发展、研究对象、概念与特点、应用领域等内容。

第二章系统工程方法论
主要包括系统工程的基本工作过程、系统分析原理、创新思维与方案创造技术、系统工程方法论的新发展等内容。

第三章系统模型与模型化
主要包括系统模型与模型化概述、系统结构模型化技术、主成分分析及聚类分析、状态空间模型、系统工程模型技术的新进展等内容。

第四章系统仿真及系统动力学方法
主要包括系统仿真概述、系统动力学结构模型化原理、基本反馈回路的DYNAMO仿真分析、DYNAMO函数、Vensim_PLE仿真软件使用等内容。

第五章系统评价方法
主要包括系统评价原理、关联矩阵法、层次分析法、模糊综合评判法等内容。

第六章决策分析方法
主要包括管理决策概述、风险型决策分析、冲突分析等内容。

第七章战略研究与管理
主要包括战略研究与管理概述、战略研究方法论、企业战略管理面临的挑战、战略管理的发展趋势等内容。

赋予图均衡方向的欧拉图构造法和圈树分解法马冉;冯琪【摘要】The paper focuses on the problem of turning an arbitrary graph into a balanced digraph by providing each edge orientation and presents two methods to give a graph balanced orientation, namely Eulerian Construc- tion and Cycle-Tree Construction. A balanced digraph is a digraph wheve │ d ＋（v） - d- （v）│ ≤ 1 for each vertex of the digraph. The first method is Eulerian Construction based on the fact that a connected graph is an Eulerian graph if and only if it is even. The second method is to construct a cycle - tree decomposition by ap- plying the constructions of cycle and tree and give each edge orientation in G. Furthermore, the proof is pro- vided for the way to give an arbitrary graph balanced orientation.%提出了2种赋予任意一个图均衡方向的方法：欧拉图构造法和圈树分解法，第一种方法是欧拉图构造法：若给定的图是欧拉图，先找到欧拉环游后再顺着欧拉环游的方向给边赋予方向．若不是欧拉图，可以通过给此非欧拉图补充边得到欧拉图赋予边方向后，再删除添加的边即可得到均衡有向图．第二种方法是圈树分解法，分两步进行：先假设图G是一棵树，运用树的特殊结构给出了赋予树G均衡方向的算法，因为森林是多棵树的并，所以若G是森林，此算法也能赋予G均衡方向．最后结合圈上每个顶点的度都是偶数，给出了总算法并证明了此算法能给任意一个图赋予均衡方向．【期刊名称】《河南理工大学学报（自然科学版）》【年(卷),期】2012(031)002【总页数】3页(P232-234)【关键词】有向图;均衡方向;树;圈;欧拉图【作者】马冉;冯琪【作者单位】河南理工大学数学与信息科学学院,河南焦作454000;中原工学院理学院,郑州450007【正文语种】中文【中图分类】TP180 引言图论是运筹学特别是组合最优化的基础．人们研究图时发现为了更好的处理和研究交通、物流和各种循环比赛等问题时有必要对图的边赋予一个方向，边有方向的图即是有向图．若有向图D=(V，A)，则V是有向图D的顶点集，A是有向图D的弧集．若弧a=uv，则a的箭头从顶点u指向顶点v，称顶点v为弧a的头，顶点u为弧a的尾．以顶点v作为头的所有弧的数目称为v的入度，记为d-(v)；以顶点v作为尾的所有弧的数目称为v的出度，记为d+(v)．对于一个有向图来说，若对于它的每一个顶点v都满足︱d+(v)-d-(v)︱≤1.那么这个有向图就称为均衡有向图或平衡有向图．均衡有向图对交通和物流的研究意义重大．下面将证明任意一个图赋予适当方向后都可以成为均衡有向图，并给出了两种不同的赋予图均衡方向的方法：欧拉图构造法和圈树分解法．第一种方法是欧拉图构造法：若给定的图是欧拉图，先找到欧拉环游后再顺着欧拉环游的方向给边赋予方向，若不是欧拉图，可以通过给此非欧拉图补充边得到欧拉图，先找出欧拉环游并顺着欧拉环游的方向赋予边方向后，再删除添加的边即可得到原图所对的均衡有向图．第二种方法是圈树分解法，分两步进行：先假设图G是一棵树，运用树的特殊结构给出了赋予树G均衡方向的算法A1，因为森林是多棵树的并，所以若G是森林，此算法也能赋予G均衡方向．最后结合圈上每个顶点的度都是偶数，给出了总算法A并证明了此算法能给任意一个图赋予均衡方向．1 欧拉图构造法给定一个任意图G=(V，E)，从顶点集中找出所有度为奇数的顶点，根据握手定理及其推论，可以知道度为奇数的顶点数一定为偶数．不失一般性，假设图G中奇度顶点集合为S={v1，v2，…，v2k}．下面分两种情况讨论：(1)若k=0.k=0意味着此图中没有奇度顶点．因为一个连通图是欧拉图的充分必要条件是这个连通图中没有奇度顶点．所以可得出以下结论：(a)若G是连通图，则G是一个欧拉图；(b)若G不是连通图，则它的每一个连通分支都是一个欧拉图．对于(a)，因为欧拉图一定有欧拉环游，所以可以按照以下方法进行：先找出图G 的欧拉环游，只要沿着图G的欧拉环游的路径方向赋予图中边的方向，则根据欧拉图和欧拉环游的定义和性质，就可以给任意一条边赋予方向，因为每个顶点若有一个入弧肯定有一个出弧和它对应，所以对所有顶点来说，出度和入度相等，即每个顶点满足d+(v)=d-(v)，满足均衡有向图的条件，即图G被赋予了均衡方向．至于情形(b)，若G不是连通图，则它的每一个连通分支都是一个欧拉图．只要对图G的每一个连通分支都按照(a)的方法赋予方向后，则每个分支都被赋予了均衡方向，即图G就被赋予了均衡方向，变为一个均衡有向图．(2)若k≠0图G中有2 k个奇度顶点，所以此图一定不是欧拉图．那么可得出以下结论：(c)若G是连通图，则G不是一个欧拉图；(d)若G不是连通图，则至少存在一个连通分支不是一个欧拉图．对于情形(c)，因为奇度顶点集合为S={v1，v2，…，v2k}，所以若在图G中添加边E*={e1，e2，…，ek}，其中ei=v2i-1v2i，1≤i≤k，这样就得到了一个新图G*，并且在此新图G*中没有奇度顶点，新图G*又是一个连通图，则此新图G*就是一个欧拉图．转化为第一种情形即没有奇度顶点的时候，实施与情形(a)相同的方法即可赋予新图G*均衡方向，并且每个顶点满足d+(v)=d-(v)．赋予了新图均衡方向以后，再删除边E*及其边上的方向，则对于图G，每个偶度顶点仍旧满足d+(v)=d-(v)，每个奇度顶点满足︱d+(v)-d-(v)︱=1，满足均衡有向图的条件，则对图G赋予了均衡方向．至于(d)的情形，若G不是连通图，则至少存在一个连通分支不是一个欧拉图(否则，若每个连通分支都是欧拉图，则每个连通分支都没有奇度顶点，图G就没有奇度顶点，与图G有奇度顶点矛盾)．只需对每一个非欧拉分支实施与(c)相同的方法，对于每一个欧拉分支实施与(a)相同的方法就能使图G拥有均衡方向．通过以上讨论，给出以下定理，即定理1 欧拉图构造法能赋予任意一个图均衡方向．2 圈树分解法给定任意一个图G，分两步进行：先假设图G是一棵树，运用树的特殊结构给出了赋予树G均衡方向的算法A1，再结合圈的性质给出了任意一个图赋予均衡方向的算法A——圈树分解法，并证明此算法能给任意一个图赋予均衡方向．下面先给出赋予树G均衡方向的算法A1．算法A1步骤1：在图G中找出极长路P1，并顺着P1的方向给其边E(P1)赋予方向；步骤2：在剩余图G-P1-…-Pi-1中找出极长路Pi，并顺着此路的方向给边E(Pi)赋予方向；步骤3：若图G的所有边都有方向了，则算法停止；否则，令i-1=i，并返回步骤2．接下来将证明上述算法能赋予树G均衡方向．定理2 算法A1能赋予任意树G均衡方向．证明：用反证法．若实施算法A1后，在树G中存在一顶点v满足︱d+(v)-d-(v)︱>1，为方便叙述，不妨假设d+(v)=d-(v)+2，如图所示.假设顶点v的入弧(v3,v)和出弧(v,v4)是在极长路Pi-2上，出弧(v,v1)在极长路Pi-1上，出弧(v,v2)在极长路Pi上，若将v的一个出弧(v,v2)改为入弧(v2,v)，则Pi-1路长可以增加1，这与所选择的Pi-1是极长路矛盾，故结论成立．因为森林是多棵树的并，所以可以得到以下推论.推论若G是森林，算法A1也能赋予G均衡方向．下面给出赋予任意一个图均衡方向的A——圈树分解法步骤1：在图G中找出一个圈C1，并沿着C1的方向给其边E(C1)赋予方向；步骤2：在剩余图G-C1-…-Ci-1中找出一个圈Ci，并顺着此圈的方向给边E(Ci)赋予方向；步骤3：若图G的所有边都有方向了，则算法停止；否则，令i-1=i，并返回步骤2；若剩余图中没有圈了，即剩余图为树或森林了，转用算法A1．定理3 算法A能赋予任意一个图均衡方向．证明：根据圈的结构和性质，当沿着任意一个圈给圈上的边赋予方向时，此圈上每个顶点都满足d+(v)=d-(v)，所以当找完图G中所有的圈并赋予方向后，圈上的每个顶点的出度都等于入度，接着再根据算法A1赋予完方向后对于它的每一个顶点v都满足均衡方向的条件︱d+(v)-d-(v)︱≤1，所以此时得到的有向图就是一个均衡有向图．证毕．参考文献：[1] BONDY J A, Murty U S R, Graph Theory[M], Springer San Francisco, 2008.[2] ZHANG XIANZHAO, ZHANG YUZHONG, CAO ZHIGANG, et al. Approximation schemes for scheduling a batching machine with nonidentical job sizes[J]. Journal of Systems Science and Complexity,2007(20): 592-600.[3] YUAN JINJIANG, SHANG WEIPING. A PTAS for P-batch Scheduling with pj = p to Minimize Total Weighted Completion Time[J]. Journal of Industrial and Management Optimization, 2005, 1: 353-358.[4] DENG XIAOTIE, ZHANG YUZHONG. Minimizing mean completion timein a batch processing system, Algorithmica, 2004，38: 513-528.[5] 张洪瑞,王力工.用超广义线图构造整谱图[J].动乱学学报,2011,15(1)：124-128.[6] 孔敏,汤进,罗斌.基于拉普拉斯图的谱特征的图像聚类研究[J].中国科学技术大学学报,2007,37(9)：16-17.[7] 钟富胜,张春元.Parsons图的谱性质[J].信息工程大学学报,2003,4(4)：11-13.[8] 郭夕敬,张寿传,杨必中.Hopf箭图与Hopf代数[J].数学杂志,2008,28(1)：31-34.[9] 姚香娟,李学良.关于有向整谱图的若干存在性问题[J].数学研究,2002,3(3)：41-42.[10] 景占策,侯耀平.图类αka,a/βCP(b)中的整谱图[J].数学的实践与认识,2008(19)：27-28.[11] 马冉，姚景景，郑玉歌．工件带链约束和尺寸的并行批排序[J]，河南理工大学学报:自然科学版，2011,30(4)：502-504．。