图论复习题及答案

图论复习题及答案（共4篇）

图论复习题及答案 篇1

《离散数学》图论部分习题

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

16.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.

课本中二句解释及习题答案的商榷 篇2

关键词：what、 that、 one of+名词（复数）…+复数动词、the（only） one of+名词（复数）…+单数动词。

一、普通高中课程标准实验教科书（必修2）课本中第5页阅读和听力一文中有这样一句型：An opinion is what someone believes is true but has not been proved.

该句（人教出版社）必修2参考译文是：看法是人们相信是真实的但是未经证实。笔者查阅好多中学教材全解对该句的注释和人教出版社注释相同，都认为what引导的从句是表语从句，An opinion为主句的主语，is为系动词，what引导的从句是表语从句，在what引导的从句中含有由but连接的两个并列句，并解释what引导名词性从句时，what在从句中可以充当主语、宾语、表语等成分。例如：

What he said is true. 他说的是事实。

What made her upset is that she didn’t pass the exam.

她没有通过考试使她非常难过。

笔者认为该句型解释值得商榷。还得从that和what这两个词论起，that为从属连词引导名词性从句，不担任成分。例如：

She said（that）she would come. 她说她要来。（见《现代高级英汉双解辞典》第1141页）

The trouble is that we are short of money. 困难的是我们缺钱。（见《现代高级英汉双解辞典》第1141页）

The truth was that we never saw him.事实是我们从未见过他。（见《大英汉词典》第1558页）。

The reason was that he was afraid.原因是他害怕。（见《新标准中学生英语词汇用法全解》第1435页）。

She said she had bought a new car.她说她买了一辆新车。（见《外研社实用英汉词典》第1015页）。

What he says is not important. 他所说的话不重要。（见《现代高级英汉双解辞典》第1248页）

He is not what he used to be. 他已不是过去的他了。（见《外研社实用英汉词典》第1084页）

This is what I want to know. 这正是我们要知道的。（见《新标准中学生英语词汇用法全解》第1580页）。

根据以上例句笔者认为该句主语为An opinion，is为系动词，后面连接了一个省略从属连词that的表语从句，what引导的主语从句为表语从句的主语，what（相当于the thing that）在主语从句中充当believes的宾语,is true为表语从句的谓语（系表结构），but连接的两个并列句。假如把what视为表语从句的引导词，在从句中充当believes的宾语，那么is true作何解释？如该句没有is true，what从句当然为表语从句的引导词，what在表语从句中充当believes的宾语。或者假若is true是to be true也可视为表语从句引导词what的宾补（believe sth（to be）adj。

二、该书第4页Discovering useful structure练习4,（9小题）：

It’s one of the few places which is known for its good food. （划线部分为该书参考书18页所给汉译英答案）。

笔者认为1. 在“one of+名复数名词+关系代词who/that/which”引导的从句结构中，关系代词who/that/which的先行词是靠近它的复数名词而不是one，因此，从句应该是复数形式。

2. 但是当one前有the only等修饰时，关系代词的先行词是one，而不是靠近它的复数名词，因此从句的动词应是单数形式。例如：

The Great Wall is one of the world_famous buildings that draw lots of visitors.

长城是吸引大批游客的世界著名建筑之一。

The Great Wall is the only one of the buildings on the earth that is seen from the moon. 长城是地球上唯一能从月球上看到的建筑物。

He is one of the boy students who are always ready to help others.

他是乐于助人的男同学之一。

He is the only one of the students who comes from the south.

他是惟一来自南方的学生。

【考例】 He is the only one of the students who_____a winner of scholarship for three years.（2002年上海市普通高等学校春季招生英语试题）

A.is B.are C.have beenD.has been答案：D

解析：当one前有the only，just the等修饰时,谓语动词与one保持一致,故答案为D。

【考例】I wonder whether the soldier is one ofthose who____abroad to keep peace.（南通上市高三第一次調研测试。）

A.has been sentB.have been sent

C.have sentD.has sent答案：B

解析：关系代词who指代的先行词是those，所以助动词用have，战士是被派送到国外维和的，所以用被动语态。

【考例】Oscar Gold Prize is the only one of the film prizes____offered to any Chinese actor or actress by far. 答案：D

A. which is notB. that have not beenC. that has not D. that has not been答案：D

解析：当one前有the only，just the等修饰时,谓语动词与one保持一致,故答案为D。

【考例】Oscar Gold Prize is one of the film prizes_______offered to any Chinese actor or actress so far.

A. which is notB. that have not beenC. that has not D. that has not been答案：B

解析：当先行词的one前无the only，just the等修饰时,of后面的复数名词是先行词,,从句的谓语动词用复数，故答案为B。

根据以上例句，笔者认为18页所给汉译英参考答案which is应为which are。以上两处看法 ，是否正确，敬请编辑及同行指正。

参考文献:

1.《大英汉词典》

2.《外研社实用英汉词典》

3.《现代高级英汉双解辞典》

图论复习题及答案 篇3

关键词：耗时；模型；企业物流；评价

中图分类号：F274 文献标识码：A 文章编号：1002-3100(2007)11-0099-03

Abstract: A consuming-time model for enterprise logistics performance measurement is put forward with fuzzy graph theory. The model consists of multi-directioned fuzzy graph and the generalized fuzzy matrix. The consuming-time relation among all the steps of enterprise logistics performance measurement is described by the model clearly and quantitatively. The model is also helpful for controlling the time of enterprise logistics performance measurement.

Key words: consuming-time; model; enterprise logistics; measurement

0引言

企业物流绩效评价工作必须控制在一定的时间之内，这样才能保证评价结果的时效性。然而，评价各环节之间具有可逆性、交叉性和反复性，通过一般方法，难以计算评价耗费的时间。鉴于此，本文运用模糊图论的基本理论，建立了企业物流绩效评价耗时模型，该模型包括评价过程的多重有向模糊图和广义模糊矩阵。多重有向模糊图对评价各环节之间的关系进行了直观的描述，广义模糊矩阵对评价各环节耗费的时间进行了定量的描述。通过该模型，可以定量计算评价工作总的耗费时间，为控制评价实施工作的时间提供了依据。

1企业物流绩效评价过程分析

1.1企业物流绩效评价过程。企业物流绩效评价的主要目的是为了提高企业物流的绩效水平，使企业物流获得持续改进，而不仅仅是监测企业物流的变化。企业物流所处的环境是动态变化的，企业物流的成功与否取决于其能否满足各物流相关部门的需要。因此，企业物流绩效评价不能以自我为中心，还需要考虑顾客、供应商和其他股东的利益和意见。在评价时，要注重持续改进企业物流的竞争能力。因此，企业物流绩效评价的评价实施过程应遵循以下原则：评价指标应与企业物流战略直接相联系[1]；评价指标要反映企业物流客观形势的变化[2]；评价应是一个闭环反馈系统[3]；评价不仅能监测企业物流绩效，而且能促进企业物流绩效持续改进[4]。

企业物流绩效评价过程可分为以下九个步骤：

步骤1：成立评价工作组织机构。企业物流绩效评价组织机构由企业中高层管理人员、各职能部门负责人和若干评价咨询专家组成。

步骤2：收集与核实评价资料。评价资料包括企业内部与物流相关的资料。

步骤3：确定企业物流战略目标。在充分调查的基础上，确定企业物流战略目标。

步骤4：分解企业物流战略目标。将企业物流战略目标分解成企业物流业务流程目标。

步骤5：建立企业物流绩效评价指标体系。根据企业物流战略目标及其业务流程目标和企业物流绩效评价模型建立企业物流战略级绩效评价指标，再将战略级绩效评价指标分解成战术级评价指标。

步骤6：测量评价指标值。对战术级评价指标值进行测量。

步骤7：评价计算。通过一定的评价方法对测量结果进行评价。

步骤8：撰写评价报告。将评价结果与企业物流战略目标和评价标准进行比较，产生绩效评价报告。

步骤9：确定企业物流绩效改进措施。企业物流管理者根据绩效评价报告，提出绩效改进措施。

企业物流绩效评价过程见图1。

需要说明的是，企业物流绩效评价是一个不断调整的动态反馈过程，随着获取的绩效信息越来越全面，该过程应作相应的调整和完善。另外，应定期地检查评价方法和评价模型是否适用企业物流新的环境和新的评价目标，从而对评价过程进行适当的调整。通过企业物流绩效进行评价，可以及时掌握企业物流绩效的全面状况，从而提高企业物流的绩效水平，使企业物流得到可持续发展。

1.2企业物流绩效评价过程分析。企业物流绩效评价过程各环节之间具有可逆性、交叉性和反复性。可逆性是指评价过程的某个环节不能正常进行时，应该对该环节的上一个环节进行修改完善。评价过程的可逆性体现在以下方面：（1）“收集与核实评价资料”环节不能有效地进行时，则必须重新确定“评价工作组织机构”，将对企业物流业务熟悉的人员充实到评价工作组织机构中去。（2）“分解企业物流战略目标”环节不能有效地进行时，则“确定企业物流战略目标”环节有误，必须重新分析企业物流状况，正确界定企业物流战略目标。（3）当某个评价指标值不易测量时，则应修改完善企业物流绩效评价指标体系，使评价指标体系中每个指标值都能被有效地测量到。（4）当评价结果与企业物流战略目标相比较，存在较大出入时，则可能选用了不合适的评价计算方法，因此，必须重新确定评价计算方法，再进行评价计算。（5）如果不能根据评价报告提出企业物流绩效改进措施时，则必须重新撰写评价报告。

评价实施过程的交叉性指的是评价过程的某个环节的耗时是受若干个相关环节的影响，而该若干个相关环节又可能影响其它某个环节的耗时。评价过程的交叉性体现在以下方面：（1）企业物流绩效评价指标体系是根据企业物流战略目标、企业物流战略目标业务流程目标和企业物流绩效评价模型等三者建立的。（2）评价指标值是根据评价指标体系所列出的评价指标从收集到的企业物流绩效评价相关资料中获取的。（3）评价计算是根据收集到的评价指标值，结合评价指标体系的层次结构，选择合适的评价计算方法进行的。（4）评价报告是根据评价资料、企业物流战略目标、企业物流业务流程目标和评价计算结果等撰写的。（5）企业物流绩效改进的依据是企业物流战略目标、企业物流业务流程目标、企业物流绩效评价指标体系和评价报告。

评价过程的反复性是指评价过程是一个不断调整的动态反馈过程。

2企业物流绩效评价耗时模型

2.1理论依据[5]

图2通过二重有向模糊图直观地描述了评价过程各环节之间的关系；公式（7）通过广义模糊矩阵定量地描述评价过程各个环节的耗时，评价过程总的耗费时间是广义模糊矩阵中各个时间的累加值，对评价实施时间的控制必须从评价实施各个环节所耗用的时间入手。

3结论

运用模糊图论的基本理论，建立了评价耗时模型，该模型首先对企业物流绩效评价评价各环节之间的关系进行了直观的描述，接着对评价各环节耗费的时间进行了定量的描述。通过该模型，可以定量计算评价工作总的耗费时间，为控制评价实施工作的时间提供了依据。

参考文献：

[1] M. Bourne, J. Mills, M. Wilcox, A. Neely, K. Platts. Designing, implementing and updating performance measurement systems[J]. International Journal of Operations & Production Management, 2000,20(7):754-771.

[2] G. B. Davies. Strategies for information requirements determination[J]. IBM Systems Journal, 1982,21(1):4-30.

[3] B. M. Beamon, T.M.Ware. A process quality model for the analysis, improvement and control of supply chain systems[J]. Logistics Information Management, 1998,11(2):105-113.

[4] M. Bourne, J. Mills, M. Wilcox, A. Neely, K. Platts. Designing, implementing and updating performance measurement systems[J]. International Journal of Operations & Production Management, 2000,20(7):754-771.

[5] 何新贵. 模糊知识处理的理论与技术[M]. 北京：国防工业出版社，1998:98-101.

图论复习题及答案 篇4

摘 要：如果列车发生晚点就需要启动列车运行调整，对列车的区间运行时分和到发时间进行合理的改变和调整，从而使列车的正点率得以提升，这就是所谓的列车运行调整。本文与我国的铁路运行现状和发展趋势相结合，将调整列车运行的图论模型提了出来，并且选择C语言的方式对启发式算法进行编制，对算例进行求解，最终分析并且比较了算例。

关键词：高速旅客列车；运行调整；启发式算法

中图分类号： U29 文献标识码： A 文章编号： 1673-1069（2016）12-149-2

0 引言

调整列车运行的最为主要的目的就是确保列车能够最大限度地依据计划时间表进行运行，作为一个非常复杂的问题，调整列车运行的工作需要对很多因素进行综合考虑，其从本质上来说是一个超大规模的组合优化问题。因为列车运行调整问题具有较广的涉及范围和较多的涉及因素，所以必须要深入和细致地研究其中存在的各种问题。与此同时，在运营模式和运行调整等各方面我国的铁路列车都存在着一定的特殊性，因此不可以对国外的研究成果进行全盘利用，需要与我国的国情相结合，制定与我国铁路情况相适应的列车运行调整技术。

1 高速旅客列车运行调整问题的图论模型

在2002年Caprara提出了关于调整列车运行问题的相关算法和图论模型，同时其有效地完善了传统列车的运行图。Caprara的基本思路为：将一个非循环有向多边图建立起来，对其中的虚拟的终端节点和虚拟的源节点进行设置，从虚拟的源节点中驶出每列列车，最终达到虚拟终端节点，也就是采用到达和出发两条线对列车运行图中车站一条线进行表达，通过时间轴的方式给出到达出发线。因为用分钟为单位表示一整天，也就是1到1440，采用1440个点的方式对到达和出发线进行划分，这样每个线上特定的点就能够将车站内列车的通行、停止和到达情况准确地反映出来。可以通过一条有向弧表示每列列车的运行情况，每条弧主要包括终止弧集合、区间弧集合、车站弧集合和起始弧集合。在有向图中包含了相关的每辆列车的可行性约束，这样通过可有向图就能够将每列列车的在具体的运行区间的晚点情况和到发晚点情况清楚地观察到，从而更好地开展高速旅客列车的运行调整工作。

2 高速旅客列车运行调整问题的算法研究

2.1 高速旅客列车运行调整问题的启发式算法

不同的晚点列车在列车运行调整中在调整优选级方面存在着一定的差异，在恢复正点运行的要求方面不同等级的列车也存在着一定的差异。比如，普通列车和特快列车具有相同时分的晚点情况，这时候就需要对特快列车进行优先调整，确保其能够以最快的速度实现恢复正点运行。调整列车运行的问题属于一个非常难的问题，而且其与列车运行图的编制问题并不相同，往往要很短的时间进行求解。所以必须要采用具有较高精度和较快捷速度的近似算法对列车的运行调整问题进行计算。本文修改了传统的贪婪算法，将一种新的求解算法提了出来。在这种算法中需要输入的已知参数主要包括列车等级信息、列车的到发间隔时分、列车的晚点信息以及列车的计划时刻表等，在各站各列车的最优到发时间是列车运行调整的目标输出，高速旅客列车运行调整启发式算法主要包括以下的求解流程：①初始化处理。要将已知的各项参数输入进去。②将发生晚点的车站和首次晚点的列车确定下来，并且要将首次晚点的列车影响的其他相关列车确定下来。③在确定满足首次晚点列车和首次晚点的列车影响的其他相关列车的越行车对，同时对交换发车顺序进行合理的调整，并且将发车时间确定下来。④以计划运行时分和最小运行时分等为根据将需要“赶点”运行的列车确定下来。如果不符合终止条件，就要返回到第二步中，如若不然，就需要将运算停止，选择现在的最优解作为最终解，并且将运算结果输出，最终形成科学的列车运行调整方案。

2.2 高速旅客列车运行调整的优化对策分析

在调整列车运行的时候必须要严格遵循以下的原则：①在每个站点都要调整在本站经过的列车的到发时间。晚点列车只会对后续各站和本站的列车产生影响，而利用区间调整冗余的方式则能够减少这种影响。②先旅客列车后货物列车是调整列车运行的优先级。要先对重点列车、快速列车、正点列车和离终点站远的列车进行先行调整，然后再对一般列车、低速列车、晚点列车和离终点站近的列车进行调整。③列车具有固定不变的优先级，而且运行的情况一般不会出现在同等级别的列车之间，而低级别的列车会被高级别的列车越行。④对列车在每站的到发时间进行调整，利用慢行和赶点的方式在区间运行时控制晚点时间。

3 高速旅客列车运行调整问题的算例求解

3.1 列车的晚点信息

以晚点情况为根据共计加3个参数设置了出来：i指的是首次晚点的时间，j指的是该区间初始晚点的列车，wd指的是列车晚点的时间。在区间运行的时候列车多出计划运行时间的实际运行时间用晚点时间wd来表示。通过计算和求解列车晚点时间wd、该区间初始晚点的列车j、首次晚点发生的区间i，这样就要能够将目标函数值和相应的晚点列车时刻表计算出来。

3.2 列车的晚点分析

在这里通过几组晚点数据分析讨论上述的数学模型，同时总结相应的晚点数据所导致的影响。在wd分别为25分钟、15分钟和5分钟，j=3，i=2的情况下，就能够将目标函数值和相应的晚点时刻表计算出来。目标函数值在晚点时间不断增大的同时也会变得越来越大，目标函数值在wd在大于15分钟的情况下会呈现出一种线性增长的趋势；wd在小于15分钟的情况下具有越来越多的受影响的列车，然而却不会影响到后续的高等级列车，而且应不应该影响到后续的高等级列车，这时候目标函数就会具有越来越快的增长速度，其增长趋势呈抛物线状。

通过上述的已知条件进行分析，我们可以发现当中等级列车具有较少的晚点时间时，不会影响到后续的高等级列车和其他的中等级列车，如果中等级列车具有较多的晚点时间时，因为越行的情况不能出现在同等级列车中，因此会影响到后续的中等级列车。如果同等级列车具有过大的晚点时间，就会影响到后续的高等级列车，然而在不断推进站点的同时，高等级列车差不多能够恢复到正点。如果高等级列车出现晚点，因为其具有较快的速度，因此基本上不会影响到后续的列车或者只会产生较小的影响。如果中等级列车的后行高等级列车出现晚点的情况，那么在这种情况下中速列车也不会被高等级列车提前越行。从整体上来看，对上述高速旅客列车调整的结果进行分析，我们认为这种算法能够对

区间和站间的冗余时间进行有效利用，从而更好地调整列车，并且进一步地降低后续列车和晚点列车本身的晚点损失。

4 结语

本文通过一种比较直观的方式将列车运行问题的图论模型提了出来，随后与我国铁路运行现状相结合，建立了初步的整数规划模型。通过对给定算例的启发式算法进行编制，就可以对区间和站间的冗余时间进行有效利用，从而科学合理地调整列车，确保列车能够尽可能的恢复正点。在本文中主要对双线自动闭塞的单方向高速旅客列车进行了考虑，所以下一步工作的主要目标就是解决单线列车的运行调整问题。

参 考 文 献

[1] 蔡涛.高速铁路列车运行调整优化模型研究[J].铁道运输与经济，2016（03）.

[2] 刘莉，王长林.城市轨道交通列车运行调整的粒子群算法研究[J].铁路计算机应用，2013（06）.

[3] 陈雍君，周磊山.基于序优化方法的列车运行调整算法研究[J].铁道学报，2010（03）.

[4] 张翠平，曹成铉，滕宇蛟，刘苏庆，陈磊.列车运行调整问题的图论模型与启发式算法[J].科学技术与工程，2010（10）：2560-2564+2573.

[5] 石雨.客运专线列车运行调整的策略、模型与算法[D].北京交通大学，2010.