第6章-图论(I)

习题11. 图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C++描述。

编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。

#include<iostream>using namespace std;int main(){double value=0;图 七桥问题for(int n=1;n<=10000 ;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<<n<<endl;break;}}计算π值的问题能精确求解吗编写程序，求解满足给定精度要求的π值#include <iostream>using namespace std;int main (){double a,b;double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。

为什么是6天呢任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。

习题一作者---寒江独钓1.证明：在n 阶连通图中(1) 至少有n-1条边；(2) 如果边数大于n-1，则至少有一条闭迹；(3) 如果恰有n-1条边，则至少有一个奇度点。

证明: (1) 若G 中没有1度顶点，由握手定理：()2()21v V G m d v n m n m n ∈=≥⇒≥⇒>-∑若G 中有1度顶点u ，对G 的顶点数作数学归纳。

当n=2时，结论显然；设结论对n=k 时成立。

当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k.(2) 考虑G 中途径：121:n n W v v v v -→→→→L若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。

于是：1i i j i v v v v +→→→→L 为G 中一闭途径，于是也就存在闭迹。

(3) 若不然，G 中顶点度数至少为2，于是由握手定理：()2()21v V G m d v n m n m n ∈=≥⇒≥⇒>-∑这与G 中恰有n-1条边矛盾！ 2.(1)2n −12n 2−12n −1 (2)2n−2−1(3) 2n−2。

证明:u 1的两个邻接点与v 1的两个邻接点状况不同。

所以，两图不同构。

4.证明下面两图同构。

u 1 v 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.指出4个顶点的非同构的所有简单图。

分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。

(a)v 2 v 3u 4u(b)6.证明:1)充分性:当G 是完全图时，每个顶点的度数都是n −1,共有n 个顶点，总的度数为n(n −1)，因此总的边数是n(n−1)2=(n 2). 2)必要性:因为G 是简单图,所以当G 是完全图的时候每个顶点的度数才达到最大:n −1.若G 不是完全图，则至少有一个顶点的度数小于n −1,这样的话，总的度数就要小于n (n −1)，因此总的边数小于(n 2)，矛盾。

6 事故树分析事故是安全管理的重要依据。

一方面，事故造成了人员伤害和财产损失，人类为此付出了血的代价；另一方面，事故这种偶然事件中都蕴涵必然的规律性。

为了不使事故重演，为了发现和认识事故中的必然规律，人类必须百倍珍惜事故过程中反映出的各种信息，通过分析其隐患、征兆、表象、关联等认识事故。

本章介绍的事故树分析是系统安全工程中的一种重要方法，它是通过对事故的演绎、推理，找到防止事故的措施和方法。

事故树分析（Fault Tree Analysis，简称FTA）也叫故障树分析或事故逻辑分析，是一种演绎分析方法。

6.1事故树分析基础6.1.1概述（1）事故树分析简介事故树分析是系统安全分析方法中得到广泛应用的一种方法。

该方法起源于美国贝尔电话研究所。

1961年华特逊在研究民兵式导弹发射控制系统的安全性评价时首先提出了这种方法。

接着，该所的A.B.门斯等人改进了这种方法，对预测导弹发射偶然事故做出了贡献。

后来，波音公司对FTA 进行了重要改革，使之能够利用计算机模拟。

1974年美国原子能委员会利用FTA对商业原子电站事故危险性进行评价，发表了著名的拉氏姆逊报告，引起世界各国关注。

事故树是由图论理论发展而来的。

在许多领域里，常牵涉到图的概念。

然而，图论中所研究的图，既不是通常的几何学中的图，也不是工程图。

它所研究的图是由一些顶点（节点）及边构成的图，通常称之为线图。

事故树是一种逻辑树图，树图是图论中的一种图，逻辑树图是用逻辑门联结的树图。

事故树中包含的事件一般的都是故障事件。

这些故障事件之间具有一定的逻辑关系，这种逻辑关系用相应的逻辑门来表达。

确切地说，事故树是演绎地表示故障事件发生原因及其逻辑关系的逻辑树图。

据研究，尽管世界上的事物千变万化，但是它们之间的逻辑关系却最终归结为三种：“与”、“或”、“非”。

相应地，表达这些逻辑关系的逻辑门为逻辑“与门”、逻辑“或门”、逻辑“非门”。

在事故树中，上一层故障事件是下一层故障事件造成的结果；下一层故障事件是引起上层故障事件的原因。

图论第二版答案【篇一：图论与代数结构第一二三章习题解答】厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

（或者利用度数为奇数的点的个数必须为偶数个） 2. 若存在孤立点，则m不超过kn-1的边数, 故m = (n-1)(n-2)/2, 与题设矛盾。

?－3. 记ai为结点vi的正度数，ai为结点vi的负度数，则nnnn? 2? 22－ai?[(n?1)?ai]?n(n?1)?2(n?1)ai＋ai－2， i?1i?1i?1i?1 nnn－2? 2 因为ai?cn?n(n?1)/2，所以ai?ai－ 2。

i?1i?1i?14. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的量, i = 1,2,3.以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点, 如果(a1,a2,a3)中某杯的水倒满另一杯得到( a’1, a’2, a’3 ) , 则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条： ( 8, 0, 0 ) ( 5, 0, 3 ) ( 5, 3, 0 ) ( 2, 3, 3 ) ( 2, 5,1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 1, 3 ) ( 4, 4, 0 )5. 可以。

???????6 若9个人中没有4个人相互认识，构造图g，每个点代表一个点，两个人相互认识则对应的两个点之间有边。

1）若可以找到点v，d(v)5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作k6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。