本科博弈论2014年第一次作业

Homework one

Note:

1. You can write in Chinese or English, printed or hand written.

2. No late homework will be accepted. Please staple your homework and write your name and ID number on the cover.

3.The deadline is Oct.22.

3.4Hunting:Two hunters, players 1 and 2, can each choose to hunt a stag, which provides a rather large and tasty meal, or hunt a hare—also tasty, but much less filling. Hunting stags is challenging and requires mutual cooperation. If either hunts a stag alone, then the stag will get away, while hunting the stag together guarantees that the stag will be caught. Hunting hares is an individualistic enterprise that is not done in pairs, and whoever chooses to hunt a hare will catch one. The payoff from hunting a hare is 1, while the payoff to each from hunting a stag together is 3. The payoff from an unsuccessful stag hunt is 0.

Represent this game as a matrix.

3.7 Public Good Contribution: Three players live in a town, and each can choose to contribute to fund a streetlamp. The value of having the streetlamp is 3 for each player, and the value of not having it is 0. The mayor asks each player to contribute either 1 or nothing. If at least two players contribute then the lamp will be erected. If one player or no players contribute then the lamp will not be erected, in which case any person who contributed will not get his money back.

Write down the normal form of this game.

4.5 Iterated Elimination: In the following normal-form game, which strategy profiles survive iterated elimination of strictly dominated strategies?

4.7 Campaigning: Two candidates, 1 and 2, are running for office. Each has one of three choices in running his campaign: focus on the positive aspects of one’s own platform (call this a po sitive campaign [P]), focus on the positive aspects of one’s own platform while attacking one’s opponent’s campaign(call this a balanced campaign [B]), or finally focus only on attacking one’s opponent (call this a negative campaign [N]). All a candidate cares about is the probability of winning, so assume that if a candidate expects to win with probability π∈ [0, 1], then his payoff is π. The probability that a candidate wins depends on his choice of campaign and his opponent’s choice.

The probabilities of winning are given as follows:

If both choose the same campaign then each wins with probability 0.5. If candidate i uses a positive campaign while j ≠ i uses a balanced one then i loses for sure.

If candidate i uses a positive campaign while j ≠i uses a negative one then i wins with probability 0.3.

If candidate i uses a negative campaign while j ≠ i uses a balanced one then i wins with probability 0.6.

a. Model this story as a normal-form game. (It suffices to be specific about the payoff function of one player and to explain how the other player’s payoff function is different and why.)

b. Write down the game in matrix form.

c. What happens at each stage of elimination of strictly dominated strategies? Will this procedure lead to a clear prediction?

图论作业(1)

第三章 1.证明： 必要性： v 是连通图G 的割边， 则 ， 至少有两个连通 分支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V 的划分。 对于任意的u ∈V1, v ∈V2，如果割边e 不在某一条（u ，v ）路上，那么，该路也是连接G-e 中的u 与v 的路，这与u,v 处于G-v 的不同分支矛盾。 “充分性” 若e 不是图G 的割边，那么G-v 连通，因此在G-v 中存在u,v 路，当然也是G 中一条没有经过边e 的u,v 路。矛盾。 7.证明： v 是单图G 的割点，则G-v 至少两个连通分支。现任取 , 如果x,y 在G-v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，通过u ，可说明，x 与y 在G-v 的补图中连通。若x,y 在G-v 的不同分支中，则它们在G-v 的补图中邻接。所以，若v 是G 的割点，则v 不是其补图的割点。 9.连通图G 的一个子图B 称为是G 的一个块，如果(1), 它本身是块；(2), 若没有真包含B 的G 的块存在。 又由于对于阶数至少是3的 ()()G e G ωω->

图G是块当且仅当G无环并且任意两点都位于同一圈上。根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。得证。 16.（1） （2） （3）

第四章3. （1）既是欧拉闭迹又是哈密尔顿圈 （2） （3）

（4） 7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。。。。Cm，所以E（G）可以表示成C1，C2.。。Cm的并。 10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。 若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。。。。xm，Y中的所有点为y1，y2.。。。。yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。 12. 证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1

2014年4月份考试Java程序设计第一次作业及答案

2014年3月份考试Java程序设计第一次作业及答案 答案：一、单项选择题（50分，共 20 题，每小题 2.5 分） 1. D 2. C 3. B 4. A 5. D 6. A 7. D 8. B 9. B 10. A 11. A 12. A 13. D 14. A 15. C 16. C 17. C 18. D 19. B 20. A 二、判断题（50分，共 20 题，每小题 2.5 分） 1. √ 2. × 3. √ 4. × 5. √ 6. √ 7. √ 8. √ 9. √ 10. × 11.× 12. × 13. √ 14. × 15. × 16. √ 17. √ 18. × 19. √ 20. √ 一、单项选择题（本大题共50分，共 20 小题，每小题 2.5 分） 1. 在某类的子类中,下述方法中必须要实现的方法是（） A. Public double methoda(); B. Static void methoda (double d1) {} C. Public native double methoda(); D. Abstract public void methoda(); 2. 给定File f=new File("aa.txt");可以实现向文件尾部读写的是（） A. RandomAccessFile f1=new RandomAccessFile(f,"r"); B. RandomAccessFile f1=new RandomAccessFile(f,"a"); C. RandomAccessFile f1=new RandomAccessFile(f,"rw"); D. RandomAccessFile f1=new RandomAccessFile(f,"w"); 3. 以下由do-while语句构成的循环执行的次数是（） int k = 0; do { ++k; }while ( k < 1 ); A. 一次也不执行 B. 执行1次 C. 无限次 D. 有语法错,不能执行 4. 给定类Demo定义如下 下列描述中正确的是（） A. 新生成Demo对象时coumt的值为0 B. 新生成Demo对象时coumt的值未定义

电大离散数学作业答案(图论部分)

离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2018年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f}． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点度数之和等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且等于出度． 5．设G=是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1，则在G 中存在一条汉密尔顿路． 6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为W(G-V1)≤∣V 1∣． 7．设完全图K n 有n 个结点(n ≥2)，m 条边，当n 为奇数时，K n 中存在欧拉回路． 8．结点数v 与边数e 满足e=v-1关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i =5． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回

2014年上半年高级英语二第一次作业 answer

用户2013春入学专升本龙剑 课程高级英语（2） 测试2014年上半年高级英语二第一次作业 已开始14-4-20 上午10:10 已提交14-5-30 下午10:35 状态已完成 分数得348 分，满分300 分 已用时间204 小时 2 分钟。 说明 问题1 得0 分，满分5 分 Section A (5 points) Directions: Match each word in the left column with its synonym in the right column. 答案 问题所选匹配 1. appalled B. B. shocked and upset 2. crassly E. E. stupidly and bluntly 3. impoverished D. D. poverty-stricken 4. rueful C. C. inspiring pity or compassion 5. visceral A. A. instinctive 问题2 得60 分，满分60 分 Section B (20 points) Directions: There are 20 incomplete sentences in this section. For each sentence there are four Cho ices marked A, B, C and D. Choose the ONE that best completes the sentence. 6. We were most flattered to find that we had a wonderfully ________ audience for last night’s perf ormance. 答案 所选答案： A. responsive

图论大作业

《图论及其应用》大作业 指导老师郝荣霞 知行1503 徐鹏宇 15291200

2.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。 证明： 对奇点数k使用数学归纳法。 ①当k=1时，G是森林，且有且只有2个奇点 ?G只能为一颗树，且G的所有奇度顶点为两个1度顶点 ?G是一条路 ?满足题设 ②假设当k=t时，结论成立。接下来考虑k=t + 1时的情况。 在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。 由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。 ?则G–P是有2t个奇度顶点的森林 ?由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。 ?则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。 ?即证。

2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3 证明： 由定理2.9：τ（K n ）=n n-2 由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树） 现在需要求含有e 的生成树棵树， τ（含有e 的生成树棵树）=)1(2 1n 1-n 2-n n n ）（=2n n-3 τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-3

3.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。 证明： 设G 为不是块的连通图，由于G 连通且不是块 ?G 有割点 ①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知?G1,G2是块，且分别含一个割点v 。 ②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3 。 由于u ，v 是相距最远的两割点?G1和G3不含割点。 又由于G 连通，G1,G3为G 的一部分?故G1,G3连通。 ?G1，G3内无割点，且连通。 ?G1，G3是块，且分别含割点u ，v 。 ?即证

博弈论练习题2答案

博弈论练习题2答案

111111111111111111 博弈论练习题（四） 一、什么是子博弈精炼纳什均衡？ 答：将纳什均衡中包含的不可置信的威胁策略剔除出去。它要求参与者的决策在任何时点上都是最优的。由于剔除了不可置信的威胁，在许多情况下，精炼纳什均衡也就缩小了纳什均衡的个数。只有当参与人的策略在每一个子博弈中都构成纳什均衡叫做精炼纳什均衡。或者说，组成精炼纳什均衡的策略必须在每一个子博弈中都是最优的。 二、参与人的理性问题对动态博弈分析的影响是否比静态博弈的影响更大？为什么？ 答：正确，博弈论要求个体具有始终追求自身利益最大化的理性意识和理性能力的“自我”个体理性，这是静态博弈的范畴。除此之外，还要求相关的参与者具有层次较高的“交互理性”，要求不同个体之间在理性和行为方面具有一种“默契”。即，人们的自身利益的最大化不仅取决于自己的选择，还取决于与之相关的其他人的选择与行为，那么为了实现自己的最大利益，个体的理性决策就必须考虑他人的理性选择与行为。作

为博弈论的基础，交互理性是其基本的理性要求。博弈论还要求有关博弈的结构、各个博弈参与者的得益函数以及各个博弈参与者的理性等“知识”是所有博弈参与者之间的“共同知识”。也就是，每个博弈参与者不仅要首先明确自己和其他参与者所有可选的策略，还需知晓各种情况下自己最终的收益或其概率分布，并且每个博弈参与者都知道各个参与者掌握这些信息；更为重要的是，每个博弈参与者都知道所有参与者都是理性的，都知道其他博弈参与者知道所有参与者都是理性的，都知道其他博弈参与者知道其他博弈参与者知道所有博弈参与者都是理性的------。理性的共同知识假设是非合作博弈理论的一个非常重要和关键的假设，是实现交互理性和理性主义的纳什均衡的基本前提，这些，都是动态博弈的范畴。因此说，参与者理性问题对动态博弈的分析影响更大。 三、纳什均衡和精炼纳什均衡存在哪些问题？答：纳什均衡存在的问题： (1)不是所有博弈都存在纳什均衡如纯策略就不存在混合策略则一定会存在纳什均衡，它是通

电子科技大学-图论第一次作业

课本习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对"v i v j ? E ((a)),有f (v i v j,),=,u i,u j,?,E,((b)) (1￡ i ￡ 10, 1￡j ￡ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)

m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 非负整数组12121(,,,),,2n n n i i d d d d d d d m π==≥≥≥=∑L L 是图序列的充要条件是： ? 11 12312(1,1,,1,,,)d d n d d d d d π++=---L L 是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若δ≥2，则G 包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设V (G )={V 1，V 2,V 3,?V n },对于G 中的路V 1，V 2,V 3,?V n 若V k 与V 1邻接，则构成一个圈。若V i1，V i2,V i3,?V in 是一条路，由于δ≥2，因此，对于V in ，存在V ik 与之邻接，则V ik ，,?V in V ik 构成一个圈。 ● 17.证明：若G 不连通，则G ?连通。 证明：对于任意的u,v ∈(G ?),若u 与v 属于G 的不同连通分支，显然u 与v 在G ?中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点， 则u 与w ，v 与w 分别在G ?中连通，因此，u 与v 在G ?中连通。 ● 18.证明：若e ∈E(G),则w (G )≤w (G ?e )≤w (G )+1. 证明：若e 为G 的割边，则w (G ?e )= w (G )+1，若e 为G 的非割边，则w (G ?e )=w (G )，

博弈论基础作业及答案

博弈论基础作业及答案Last revision on 21 December 2020

博弈论基础作业 一、名词解释 纳什均衡占优战略均衡纯战略混合战略子博弈精炼纳什均衡 贝叶斯纳什均衡精炼贝叶斯纳什均衡共同知识 见PPT 二、问答题 1.举出囚徒困境和智猪博弈的现实例子并进行分析。 囚徒困境的例子：军备竞赛；中小学生减负；几个大企业之间的争相杀价等等； 以中小学生减负为例：在当前的高考制度下，给定其他学校对学生进行减负，一个学校最好不减负，因为这样做，可以带来比其他学校更高的升学率。给定其他学校不减负，这个学校的最佳应对也是不减负。否则自己的升学率就比其他学校低。因此，不论其他学校如何选择，这个学校的最佳选择都是不减负。每个学校都这样想，所以每个学校的最佳选择都是不减负，因此学生的负担越来越重。 请用同样的方法分析其他例子。 智猪博弈的例子：大企业开发新产品；小企业模仿；股市中，大户搜集分析信息，散户跟随大户的操作策略 以股市为例：给定散户搜集资料进行分析，大户的最佳选择是跟随。而给定散户跟随，大户的最佳选择是自己搜集资料进行分析。但是不论大户是选择分析还是跟随，散户的最佳选择都是跟随。因此如果大户和散户是聪明的，并且大户知道散户也是聪明的，那么大户就会预见到散户会跟随，而给定散户跟随，大户只有自己分析。 请用同样的方法分析其他例子。 2.请用博弈论来说明“破釜沉舟”和“穷寇勿追”的道理。 破釜沉舟是一个承诺行动。目的是要断绝自己的退路，让自己无路可退，让自己决一死战变得可以置信。也就是说与敌人对决时，只有决一死战，这样才可以取得胜利。否则，如果不破釜沉舟，那么遇到困难时，就很有可能退却，也就无法取得胜利。穷寇勿追就是要给对方一个退路，由于有退路，对方就不会殊死抵抗。否则，对方退无可退，只有坚决抵抗一条路，因而必然决一死战。自己也会付出更大的代价。

2014年南京大学网院会计学第一次作业标准答案(100分)

最新2014年南京大学网院会计学第一次作业标准答案（100分） 题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 某制造企业为增值税一般纳税人。本期外购原材料一批，发票注明买价20 000元，增值税 额为3 400元，入库前发生的挑选整理费为1 000元。则该批原材料的入账价值为（） a、20 000元 b、23 400元 c、21 000元 d、24 400元 题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 某企业刚刚建立时，权益总额为8 000万元，现发生一笔以银行存款200万元偿还银行借 款的经济业务，此时，该企业的资产总额为（） a、8 000万元 b、8 200万元 c、9 000万元 d、7 800万元 题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 凡为形成生产经营能力，在以后各期取得收益而发生的各种支出，即支出的效益与几个会 计年度相关的，应作为（） a、收益性支出 b、资本性支出 c、营业性支出 d、营业外支出 题号:4 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 填制原始凭证时应做到大小写数字符合规范，填写正确。如大写金额“壹仟零壹元伍角整”，

其小写应为（） a、1 001.50元 b、￥1 001.50 c、￥1 001.50元 d、￥1 001.5 题号:5 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 期末根据账簿记录，计算并记录出各账户的本期发生额和期末余额，在会计上称为（） a、对账 b、结账 c、调账 d、查账 题号:6 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 企业所拥有的资产从财产权利归属来看，一部分属于投资者，另一部分属于（） a、企业职工 b、债权人 c、债务人 d、企业法人 题号:7 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:3.45 公司、企业存在的下列会计行为不违反国家统一会计制度的是（） a、随意改变所有者权益的确认标准 b、推迟确认收入 c、随意调整利润分配方法

博弈论基础作业及答案

博弈论基础作业 一、名词解释 纳什均衡占优战略均衡纯战略混合战略子博弈精炼纳什均衡 贝叶斯纳什均衡精炼贝叶斯纳什均衡共同知识 见PPT 二、问答题 1.举出囚徒困境和智猪博弈的现实例子并进行分析。 囚徒困境的例子：军备竞赛；中小学生减负；几个大企业之间的争相杀价等等； 以中小学生减负为例：在当前的高考制度下，给定其他学校对学生进行减负，一个学校最好不减负，因为这样做，可以带来比其他学校更高的升学率。给定其他学校不减负，这个学校的最佳应对也是不减负。否则自己的升学率就比其他学校低。因此，不论其他学校如何选择，这个学校的最佳选择都是不减负。每个学校都这样想，所以每个学校的最佳选择都是不减负，因此学生的负担越来越重。 请用同样的方法分析其他例子。 智猪博弈的例子：大企业开发新产品；小企业模仿；股市中，大户搜集分析信息，散户跟随大户的操作策略 以股市为例：给定散户搜集资料进行分析，大户的最佳选择是跟随。而给定散户跟随，大户的最佳选择是自己搜集资料进行分析。但是不论大户是选择分析还是跟随，散户的最佳选择都是跟随。因此如果大户和散户是聪明的，并且大户知道散户也是聪明的，那么大户就会预见到散户会跟随，而给定散户跟随，大户只有自己分析。 请用同样的方法分析其他例子。 2.请用博弈论来说明“破釜沉舟”和“穷寇勿追”的道理。 破釜沉舟是一个承诺行动。目的是要断绝自己的退路，让自己无路可退，让自己决一死战变得可以置信。也就是说与敌人对决时，只有决一死战，这样才可以取得胜利。否则，如果不破釜沉舟，那么遇到困难时，就很有可能退却，也就无法取得胜利。穷寇勿追就是要给对方一个退路，由于有退路，对方就不会殊死抵抗。否则，对方退无可退，只有坚决抵抗一条路，因而必然决一死战。自己也会付出更大的代价。

图论第二次作业

第四章 3(1).有欧拉闭迹和H圈 (2).有欧拉闭迹但没有H圈 (3).有H圈无欧拉闭迹 (4).无欧拉闭迹且没有H圈 4：证：若G不是H图，由chvatal定理知，G度弱于某个图，故： = 这与题目已知条件相矛盾，故G是H图。 8：证：不失一般性，设G是连通图，是G的2k个奇点，连接，得到，则得到图，则是欧拉图，设C是中 的欧拉闭迹，删除C中的，即可得到k条边不重复的迹，使得 . 10(1)若G不是二连通图，那么G不连通或者有割点u，则w，故G是

非H图。 (2). 若G是具有二分类的偶图，且，若假设则，故 G是非H图。 11：设R是G中的H路，则对于每个真子集S，有w，又： w w，故w. 12：设u是G外一点，将u和G中的每个点连接得到图，则G的度序列为 ，故有题意知，不存在小于的正整数m，使得 ，故由Chvatal定理知，图是H图，则G有 H路。 15：(1)由图的闭包定义可知，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点加边得到。故图的闭包算法如下： 第一步：令； 第二步：在中求顶点，使得： 第三步：如果,则转到第四步；否则，停止，则可得到G 的闭包。 第四步：令，转到第二步。 复杂性分析：由其算法我们可得出其总运算量为： 故该算法能够在多项式时间内被解决，故该算法是一个好算法。 (2).设计算法如下： 第一步：在闭包构造中，将加入的边依次加入次序记为 ，在中任意取出一个H圈，令k=N;

第二步：若不在中，令；否则转到第三步。 第三步：设，令；求中两个相邻点u和v使得， u，v依序排列在上，且有：，令： 第四步：若k=1，转到第五步；否则，令k=k-1,转第二步； 第五步：停止。为G的H圈。 算法的复杂性分析：因为该算法进行了N次循环，每次循环中找到满足要求的邻接顶点u和v至多需要n-3次判断，所以总的运算量：N(n-3)。是一个好算法。 第五章 1：(1)证：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。 若划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又k方体的每个顶点度数为k,所以k方体是k正则偶图。所以由推论可知：k方体存在完美匹配。 (2).解K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹 配个数等于(2n-1)K 2n-2,如此推下去，可以归纳出K 2n 的不同完美匹配个数为： (2n-1)!!。同理，K n, n 的不同完美匹配个数为：(n)!。 2：若不然，设M 1与M 2 是树T的两个不同的完美匹配，那么M 1 ΔM 2 ≠Φ,且T[M 1 ΔM 2 ] 每个顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。故一棵树中最多只有一个完美匹配。 7：解：设 作如下四条路： 故其四个生成圈如下：

2014年4月份考试工程招投标第一次作业

2014年4月份考试工程招投标第一次作业 一、单项选择题（本大题共60分，共 20 小题，每小题 3 分） 1. 施工招标中，为了规范建筑市场有关各方的行为，《建筑法》和《招标投标法》明确规定，一个独 立合同发包的工作范围不可能是（）。 A. 全部工程招标 B. 单位工程招标 C. 特殊专业工程招标 D. 分项工程招标 2. 业主为防止投标者随意撤标或拒签正式合同而设置的保证金为（）。 A. 投标保证金 B. 履约保 证金 C. 担保保证金 D. 支付担保 3. 根据综合评估法完成评标后， ( )应当拟定一份“综合评估比较表”，连同书面评标报告提交招标人。 A. 投标人 B. 招标代理机构 C. 行政监督部门 D. 评标委员会 4. 采购的货物规格和标准统一、现货货源充足且价格变化幅度小的政府采购项目，经设区的市、自治 州以上人民政府财政部门同意后，可以采用( )的方式采购。 A. 竞争性谈判 B. 询价 C. 邀请招标 D. 公开招标 5. 按照《工程建设项目施工招标投标办法》的规定，招标人不履行与中标人订立的合同的，应当( ) 中标人的履约保证金。 A. 返还 B. 双倍返还 C. 返还并赔偿 D. 双倍返还并赔偿 6. （）是指招标人为了委托监理任务的完成，以法定方式吸引监理单位参加竞争，招标人从中选择 条件优越者的法律行为。 A. 建设工程勘察招标 B. 建设工程设计招标 C. 建设工程监理招标 D. 建 设工程材料设备招标 7. 建设项目总承包招投标，实际上就是（）。 A. 工程施工招投标 B. 项目全过程招投标 C. 勘查 设计招投标 D. 材料、设备供应招投标 8. 公平、公正、科学、诚实信用是（）。 A. 招标投标的原则 B. 评标的原则 C. 订立合同的原则 D. 监理活动的原则 9. 《工程建设项目施工招标投标办法》和《工程建设项目货物招标投标办法》均规定，投标保证金最 高不得超过( )万元人民币。 A. 50 B. 60 C. 80 D. 100 10. 根据《招标投标法》的规定，下列关于联合体投标的变更表述中不正确的是( )。 A. 联合体成员 的变更必须在投标截止时间之前得到招标人的同意 B. 联合体各方应当在招标人进行资格预审时，向 招标人提出组成联合体的申请 C. 招标人可通过相关法律规定强制要求资格预审合格的投标人组成联 合体 D. 通常情况下，变更后的联合体资质发生降低或影响到招标的竞争性，招标人有权拒绝 11. 根据不同的分类方式，工程项目招标具有不同的类型。按工程项目建设程序分类，下列不正确的 是（）。 A. 项目开发招标 B. 项目总承包招标 C. 勘察设计招标 D. 工程施工招标 12. 招标单位可以委托具有相应资质的中介机构代理招标，此招标代理机构是( )。 A. 行政机关 B. 国家机关隶属机构 C. 依法成立的组织 D. 依法成立的协会 13. 某建设项目发售招标文件时收取工本费500元，则在招投标结束后( )。 A. 招标文件及收费都不 退回 B. 退回招标文件，收费不退回 C. 不退回招标文件，收费退回 D. 招标文件及收费分别退回 14. 建设行政主管部门对招标文件是否有限制公平竞争的条件进行核查的，主要核查( )的不公正评标 条件。 A. 是否有针对材料供应商设立 B. 是否有针对外地区和外系统设立 C. 是否有针对联合体投 标者设立 D. 是否有针对一揽子交钥匙工程设立 15. 政府宏观指导、企业自主报价、竞争形成价格、加强动态管理是（）。 A. 是我国建筑市场的价 格机制 B. 是现代企业制度的价格体系 C. 是我国市场经济发展的方针 D. 是我国计划经济价格方针16. 对已完成施工图设计的小型工程，进行施工招标时，可采用( )合同。 A. 单价 B. 总价 C. 成本 加酬金 D. 综合单价 17. 甲、乙两个同一专业的施工单位分别具有该专业二、三级企业资质，甲、乙两个单位的项目经理 数量合计符合一级企业资质要求。甲、乙两单位组成联合体参加投标，则该联合体资质等级应为( )。 A. 一级 B. 二级 C. 三级 D. 暂定级 18. 《招标投标法》规定，招标投标的最大优点就是能够充分体现( )的市场竞争原则。 A. 公平、独立、自由 B. 公正、自由、客观 C. 公开、公平、公正 D. 公开、独立、客观 19. 评标委员会按规定请投标人对不明确的作出澄清的内容作为( )的组成部分。 A. 协议书 B. 专用 条件 C. 通用条件 D. 投标书 20. 下列各选项中，不属于工程建设施工项目投标文件内容的是( )。 A. 投标函 B. 投标报价 C. 技 术性能参数的详细描述 D. 施工组织设计 二、多项选择题（本大题共40分，共 10 小题，每小题 4 分）

博弈论作业及答案 浙江财经大学 张老师作业答案

第1次作业 1、考虑一个工作申请的博弈。两个学生同时向两家企业申请工作，每家企业只有一个工作岗位。工作申请规则如下：每个学生只能向其中一家企业申请工作；如果一家企业只有一个学生申请，该学生获得工作；如果一家企业有两个学生申请，则每个学生获得工作的概率为1/2。现在假定每家企业的工资满足：W1/2

图论第二次作业

图论第二次作业Newly compiled on November 23, 2020

图论第二次作业 一、 第四章 （1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下： （2）一个有Euler 闭迹但没有Hamilton 圈的图形如下： （3）一个有Hamilton 圈但没有Euler 闭迹的图形如下： （4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下： 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得 )()()()(21m C E C E C E G E ???=。 证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1≥G δ，则1G 含圈1C ，在去掉)(11C E G -的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2≥G δ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G -全为孤立点为止，于是得到)()()()(21m C E C E C E G E ???=。 证明：若 （1）G 不是二连通图，或者 （2）G 是具有二分类),(Y X 的偶图，这里Y X ≠， 则G 是非Hamilton 图。 证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)(≥-v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w ≤-)(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。 （2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ≠，在这里假设Y X ≤，则有X Y X G w >=-)(，也就是说：对于v(G)的非空顶点集S ，有：S S G w >-)(成立，则可以得出G 是非Hamilton 图。 设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。 证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1：

图论及应用第一章完整作业

习 题 1 1. 证明在n 阶连通图中 （1） 至少有n -1条边。 （2） 如果边数大于n -1，则至少有一条闭通道。 （3） 如恰有n -1条边，则至少有一个奇度点。 证明 (1) 若对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,矛盾！ 若G 中有1度顶点，对顶点数n 作数学归纳。 当n=2时，G 显然至少有一条边，结论成立。 设当n=k 时，结论成立， 当n=k+1时，设d(v)=1，则G-v 是k 阶连通图，因此至少有k-1条边，所以G 至少有k 条边。 (2) 考虑v 1→v 2→?→v n 的途径，若该途径是一条路，则长为n-1,但图G 的边数大于n-1,因此存在v i ,v j ,使得v i adgv j ,这样，v i →v i+1→?→v j 并上v i v j 构成一条闭通道；若该途径是一条非路，易知，图G 有闭通道。 (3) 若不然，对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,与已知矛盾！ 2. 设G 是n 阶完全图，试问 （1） 有多少条闭通道？ （2） 包含G 中某边e 的闭通道有多少？ （3） 任意两点间有多少条路？ 答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n -2)…1. 3. 证明图1-27中的两图不同构： 证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 图 1-27 图1-28

博弈论复习题及标准答案

囚徒困境说明个人的理性选择不一定是集体的理性选择。（√） 子博弈精炼纳什均衡不是一个纳什均衡。（×） 若一个博弈出现了皆大欢喜的结局，说明该博弈是一个合作的正和博弈。（ ) 博弈中知道越多的一方越有利。( ×） 纳什均衡一定是上策均衡。(×） 上策均衡一定是纳什均衡。（√） 在一个博弈中只可能存在一个纳什均衡。（×) 在一个博弈中博弈方可以有很多个。(√） 在一个博弈中如果存在多个纳什均衡则不存在上策均衡。 (√ ) 在博弈中纳什均衡是博弈双方能获得的最好结果。(×) 在博弈中如果某博弈方改变策略后得益增加则另一博弈方得益减少。（×）上策均衡是帕累托最优的均衡。 (×） 因为零和博弈中博弈方之间关系都是竞争性的、对立的，因此零和博弈就是非合作博弈。 （×) 在动态博弈中，因为后行动的博弈方可以先观察对方行为后再选择行为，因此总是有利的。（×） 在博弈中存在着先动优势和后动优势，所以后行动的人不一定总有利，例如:在斯塔克伯格模型中，企业就可能具有先动优势。 囚徒的困境博弈中两个囚徒之所以会处于困境，无法得到较理想的结果,是因为两囚徒都不在乎坐牢时间长短本身,只在乎不能比对方坐牢的时间更长。 (×) 纳什均衡即任一博弈方单独改变策略都只能得到更小利益的策略组合。（√ ) 不存在纯战略纳什均衡和存在惟一的纯战略纳什均衡,作为原博弈构成的有限次重复博弈，共同特点是重复博弈本质上不过是原博弈的简单重复,重复博弈的子博弈完美纳什均衡就是每次重复采用原博弈的纳什均衡。(√ ) 多个纯战略纳什均衡博弈的有限次重复博弈子博弈完美纳什均衡路径：两阶段都采用原博弈同一个纯战略纳什均衡,或者轮流采用不同纯战略纳什均衡，或者两次都采用混合战略纳什均衡，或者混合战略和纯战略轮流采用。（√) 如果阶段博弈G={Ａ1, A2,…,An; u1, ｕ2,…,un)具有多重Nash均衡，那么可能(但不必)存在重复博弈Ｇ(T)的子博弈完美均衡结局，其中对于任意的t

电子科技大学-图论第二次作业

习题四： 3.（1）画一个有Euler 闭迹和Hamilton圈的图； （2）画一个有Euler闭迹但没有Hamilton圈的图； （3）画一个有Hamilton圈但没有Euler闭迹的图； （4）画一个即没有Hamilton圈也没有Euler闭迹的图； 解：找到的图如下： (1)一个有Euler 闭迹和Hamilton圈的图； (2)一个有Euler闭迹但没有Hamilton圈的图； (3) 一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4.设n阶无向简单图G有m条边，证明:若,则是图。证明: G是H图。 若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G 度弱于某个.于是有：

2,1()()(2)(1)(1)2 11 1(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ??≤= +---+-??-??=+------- ? ?? -??≤+ ??? 这与条件矛盾！所以G 是H 图。 8.证明：若G 有 个奇点，则存在条边不重的迹 ,使得 . 证明：不失一般性，只就G 是连通图进行证明。设G=(n, m)是连通图。令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k): 12()() () ()k E G E Q E Q E Q = 10.证明：若： （1）不是二连通图，或者 （2）是具有二分类的偶图，这里 , 则是非Hamilton 图。 证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本 上的相关定理：若是Hamilton 图，则对于 的任意非空顶点集，有： ,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则是非Hamilton 图 (2)因为是具有二分类 的偶图，又因为 ，在这里假设 ,则有,也就是说：对于 的非空顶点集，有： 成 立，则可以得出则是非Hamilton 图。 11.证明：若有Hamilton 路，则对于V 的每个真子集S ，有 .

2014年9月份考试互联网及其应用第一次作业

2014年9月份考试互联网及其应用第一次作业 一、单项选择题（本大题共50分，共 20 小题，每小题 2.5 分） 1. Mica2的大小与以下哪个物体相似（）。 A. 笔记本电脑 B. 手机 C. 圆珠笔尖 D. 鼠标 2. 对OSPF协议叙述不正确的是：（） A. 在IGP协议类中，OSPF是IETF最推崇的协议 B. OSPF协议采用SPF算法计算最短路由 C. OSPF协议公开了各种规范，成为一个开放标准 D. OSPF协议采用矢量距离算法 3. TCP的可靠性采用的策略是（）。 A. 带重传的肯定确认技术 B. 数据重复传输技术 C. 数据确认技术 D. 信道可靠传输技术 4. IMAP是一下哪个协议的替代协议：（） A. SMTP TELNET B. POP C. FTP 5. 电子邮件地址wang@https://www.docsj.com/doc/ec284290.html,中没有包含的信息是( ) A. 发送邮件服务器 B. 接收邮件服务器 C. 邮件客户机 D. 邮箱所有者 6. 通过VPN传输的数据报在传输过程中，以下哪个描述不正确？（） A. 数据报首部被加密 B. 数据报数据被加密 C. 数据报作为数据被封装到一个新的数据报中 D. 使用了IP-IN-IP技术 7. 在OSI的七层参考模型中,工作在第三层以上的网间连接设备是( ) A. 集线器 B. 网关 C. 网桥 D. 中继器 8. RARP协议的作用是（） A. 已知源物理地址，解析源IP地址 B. 已知源IP地址，解析源物理地址 C. 已知目标物理地址，解析目标IP地址 D. 已知目标IP地址，解析目标物理地址 9. 以太网组播与物理地址的哪一个比特密切相关（） A. DF位 B. G/位 G/L位 C. MF位 10. 如果一个自治系统有3个路由器，R1、R2和R3。其中R1运行OSPF和HELLO，R2运行HELLO和RIP，R3运行RIP和OSPF。请问一下叙述哪个正确：（） A. R1、R2和R3两两可以交换路由信息 B. R2 和R3可以通过RIP协议交互信息