离散作业第7章

发布 2023-05-16 13:57:28 阅读 1723

第7章。

1)证明:在任何有向完全图中,所有结点入度的平方之和等于所有结点的出度平方之和。

6)证明:简单图的最大度小于结点数。

1)在无向图中,从结点到结点有一条长度为偶数的通路,从结点到结点又有一条长度为奇数的通路,则在中必有一条长度为奇数的回路。

2)若无向图中恰有两个奇数度的结点,则这两个结点间必有一条路。

3)若图是不连通的,则的补图是连通的。

4)当且仅当的一条边不包含在的闭迹中时,才是的割边。

7)在图7-2.9中给出了一个有向图,试求,及。此有向图对应的关系是否可传递的?如果不是可传递的,试求此图的传递闭包。

图7-2.9

9)一个有向图是单侧连通的,当且仅当它有一条经过每一结点的路。

10)试证明徒弟每一个结点和每一条边,都只包含于一个弱分图中。

1)求出图7-3.9中有向图的邻接矩阵,找出从到长度为2和4的路,用计算,和来验证这个结论。

图7-3.9

2)对于邻接矩阵的简单有向图,它的距离矩阵定义如下:,如果,对所有的,这里是使的最小正整数。

确定由图7-3.9所示的有向图的距离矩阵,并指出是什么意义?

3)在图7-3.10中给出了一个有向图,试求该图的邻接矩阵,并求出可达性矩阵和距离矩阵。

图7-3.10

4)写出如图3.11所示的图的完全关联的矩阵,并验证其秩是否如定理7-3.2所述。

图7-3.11

5)找一种9个,9个,9个的圆形排列,使由字母组成的长度为3的27个字的每个字出现一次。

6)a)画一个有一条欧拉回路和一条汉密尔顿回路的图。

b)画一个有一条欧拉回路,但没有一条汉密尔顿回路的图。

c)画一个没有一条欧拉回路,但有一条汉密尔顿回路的图。

9)证明如具有汉密尔顿路,则对于的每一个真子集有。

1)证明:若是每一个面至少由条边围成的连通平面图,则,这里,分别是图的边数和结点数。

5)如果可能的话,画出图7-5.8各图的平面图象,否则说明它包含一个与或在2度结点内同构的子图。

图7-5.8

3)用韦尔奇鲍威尔法对图7-6.6各图着色,求图的着色数。

ab)图 7-6.6

4)证明:若图是自对偶的,则。

7)a)一个完全图的边涂上红色或蓝色。证明:对任何一种随意涂边的方法,总有一个完全图的所有边被涂上红色,或者一个的所有边被涂上蓝色。

b)证明:六个人的人群中,或者有三个人互相认识或者有三个人彼此陌生。

c)对于各结点的完全图的边,随意涂上红色或蓝色,证明:如果有6条或更多条红色的边关联于一个结点,则存在着一个各边都是红色的或者一个蓝色的。如果有4条或更多条蓝色的边关联于一个结点,则存在一个红色的或者存在一个蓝色的。

2)一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点。

3)一棵树有个结点度数为2,个结点度数为3…,个结点度数为,问它有几个度数为1的结点。

4)设和是连通图的两棵生成树,是在不在中的一条边,证明存在边,它在中但不在中,使得和都是的生成树。

5)给定权1,4,9,16,25,36,49,64,81,100。求。

a)构造一颗最优二叉树。

b)构造一颗最优三叉树。

c)说明如何构造一颗最优t叉树。

6)构造一个与英文字母对应的前缀码,并画出该前缀码对应的二叉树,再用此六个字母构成一个英文短语,写出此短语的编码信息。

离散作业第3章

第3章3 1 6 6 确定下列集合的幂集。a b c d e 3 给定自然数集合n的下列子集 a,bcd求下列集合 a a b cd b a b cd c b ac d ab d。5 证明 对任意集合a,b,c,有。a ab ca bc b ab c ac b。c ab c ac bc 1 设a,b...

第7章作业

1 试述进油路节流调速回路与回油路节流调速回路的不同之处。2 液压系统中,当工件部件停止运动后,使泵卸荷有什么好处?试画出三种典型的卸荷回路。3 容积调速回路有哪些?各有什么特点?4 如图所示的液压系统,可以实现快进 工进 快退 停止的工作循环要求。1 说出图中标有序号的液压元件的名称。2 填出电磁...

第7章 作业

作业 1.某系统采用8255a不断检测8个开关k7 k0的通 断状态,实时在发光二极管led7 led0上显示其结果。开关闭合时,相应的led亮 开关断开时,相应的led灭。如图所示。请编写程序段实现之。2.如果8255采用方式0,a口输出,b口输入,c1口输入,c2口输出,请画出此芯片与cpu和外...