离散数学实验指导书_工程认证(实验6：洒水车路线问题)

2020/12/2
计算机学院
3
▪ 设有一个八个结点的有 向图（图2 ），其结点分
别记为三位二进制数
{000，001，010，011，
100，101，110，111}，
设 ai∈{0 ， 1> ， 从 结 点 a1a2a3可引出两条有向边， 其 终 点 分 别 是 a2a30 以 及 a2a31 。 该 两 条 边 分 别 记 为a1a2a30和a1a2a31。
R(x,y):x比y聪明 ▪ ～xy(P(x)Q(y)R(x,y)) 或者 xy(P(x) Q(y)～ R(x,y)) 完全答对： 16人 基本答对： 18人 完全答错：
25
原因分析：对命题的设定不正确，逻辑混淆。
2020/12/2
计算机学院
12
▪ 4、两个不相等的实数间，必存在第三个实数。 ▪ 解 ： 设 ： R(x):x 是 实 数 ； P(x,y,z):x ＜ z＜ y ；
人的狗 ▪ x（P(x)∧～Q(x)）或者 ▪ ～ x（ P(x) → Q(x)）
完全答对： 42人 基本答对： 0人
完全答错：17
原因分析： 逻辑谓词的存在量词没有写，对这
句话理解有偏差。
2020/12/2
计算机学院
14
第二大题：计算题
▪ 1、用公式转换法求（p→q∧r）∧(～p→(～ q∧～r) ) 的主合取范式和主析取范式。
e9e3e6e13e10e5e11e7e15e14e12e8是 一条欧拉回路，这16个二进制数可写成对应的 二进制数序列01111。把这个序列排成环状,即 与所求的鼓轮相对应。
2020/12/2
计算机学院
7
上面的例子，我们可以把它推广到鼓轮具有n个触

2018/10/21 计算机学院 10/98
定理13.1 无向连通图G＝<V，E>是欧拉图当 且仅当G的所有结点的度数都为偶数。 证明： “” 设G是Euler图，则G必然存在一条包含所有 边（也包含所有结点）的回路C，对uV，u必 然在C中出现一次（可出现多次），每出现u一次， 都关联着G中的两条边，而当u又重复出现时，它 又关联着G中的另外的两条边，（为什么？） 因而u每出现一次，都将使得结点u的度数增加 2度，若u在通路中重复出现j次，则deg(u)＝2j。 即u的度数必为偶数。
“” ：
⑴若 G没有奇度数结点，则结论显然成立； ⑵若 G 有两个奇度数结点 u 和 v，则 G+uv是 Euler 图，从 而存在Euler回路 C。从C中去掉边uv，则得到一条简 单道路 L （起点 u 和终点 v ），且包含了 G 的全部边， 即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是 G 中每条欧拉通 路的端点。
“” ：
⑴若 G没有奇度数结点，则结论显然成立； ⑵若 G 有两个奇度数结点 u 和 v，则 G+uv是 Euler 图，从 而存在Euler回路 C。从C中去掉边uv，则得到一条简 单道路 L （起点 u 和终点 v ），且包含了 G 的全部边， 即L是一条Euler道路。 注意：若有两个奇度数结点，则它们是 G 中每条欧拉通 路的端点。
例13.2
V1 V2 V3 V4 V5 V2 V3 V1 V1 V4
(a)
(b)
现在，我们是 V5 不是已经解决 了哥尼斯堡七 V2 V4 桥问题？ (c)
V3
由定理13.1及推论13.1.1容易看出：
a) 是欧拉图；
b) 不是欧拉图，但存在欧拉道路； c) 既不是欧拉图，也不存在欧拉道路。

离散数学A(II)课程实验题（代数） hj120828一、基本要求：1、可选用C或C++等编程语言或平台进行编程实验，不可直接选用非自编算法库内容。

2、实验内容可在课程提供的实验题中选，或自己设计问题与相关算法题。

3、按时间及任务要求提交实验中完成的程序代码、可执行程序、程序开发说明文档，内容包括实验数据与结果等。

二、代数结构部分题1、设V1=<{a1, a2}, max >和V2=<{b1, b2}, min >是两个数系统, 其中max (x, y)表示x与y 中较大的数；min (x, y)表示x与y中较小的数。

max和min可以看作二元运算。

输入a1, a2， b1, b2为整数, 考虑积代数V1 × V2.（1）设积代数中的二元运算为*运算，输出它的运算表（2）输出积代数的单位元和零元2、设代数系统V1=<A, •>、V2=<A, ∗>、 V3=<A, ⊙>、 V4=<A, △>，A={ x|x∈Z,1≤x≤20}，a•b= 2a+b，a∗b=max(a, b)，a⊙b=(a+b) mod8 + 2，a△b=min(a-b)，试设计算法并编程实验，要求：（1）试判断V1、V2、V3、V4是否为代数系统。

（2）试判断这些代数系统是否有左单位元与右单位元、零元，如存在，请求出。

（3）试分别判断代数系统中的运算是否满足交换律、结合律、幂等律、分配律、吸收律。

（4）试判断这些代数系统之间是否可以建立同态、同构映射，如存在，试建立。

3、设Klein四元群<G, *>，其中G={e,a,b,c}，*运算表示如下，试设计算法并编程验证<G, *>是群。

*e a b cE e a b ca a e c bb bc e aC c b a e4、试设计算法并编程求出模6加群<Z6,+6>的子群。

离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。

许多应用问题都是一个求无向连通图的最小生成树问题。

例如寻找在城市之间铺设光缆的最好方案问题等等。

解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。

本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。

概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。