离散数学实验指导书(2011-5-16).doc

离散数学离散数学 实验指导书 姜楠姜楠 焉德军焉德军 李笑牛李笑牛 （校内自编教材）（校内自编教材） 大连民族学院 计算机科学与工程学院计算机科学与工程学院 20112011 年年 3 3 月月 1 前前 言言 通常人们对离散数学教学的认识就是概念、定理、公式和解题。但是，离散数 学不仅仅是这些，还有实验。在理论教学过程中，学生的活动只是“智力活动”， 或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课 并在纸上做题目。这样，对多数学生而言，离散数学的发现探索活动没有能够真正 开展起来。 离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小 组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机， 让学生主动参与发展、探究、解决问题，从中获得离散数学研究、解决实际问题的 过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实 验课程教学进行研究具有重要意义。 利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有 效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。知识经济时代 对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。在 教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对 离散数学教学的需求是一致的。 目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方 面研究的人员更少，人们更重视离散数学理论课程教学的研究，忽视了离散数学实 验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构 等课程的有机联系。因而我准备进行离散数学实验课程教学的研究与探索，以便更 好的做好离散数学课程的教学改革工作。 本课程主要包括四个部分：集合与关系、图论、代数系统、数理逻辑。要求学 生了解算法，理解运用 C 或 C+语言把书中的部分内容的算法编写出能在计算机上 运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。 2 目目 录录 前 言 1 第一章 集合 3 实验一 集合的运算 3 实验二 求集合的笛卡儿乘积 6 第二章 关系 7 实验三 判断关系 R 的性质 7 实验四 判断关系 R 是否为等价关系 10 实验五 求等价类 11 实验六 由两个已知关系通过合成构造新的关系 12 实验七 关系的闭包运算 13 实验八 求关系个数的运算 14 实验九 求自反关系和对称关系的运算 15 实验十 求集合 A 上所有等价关系和偏序关系 16 二、求集合 A 上的所有偏序关系 17 实验十一 求满射函数 18 第三章 图论 19 实验十二 求可达矩阵的Warshall算法 19 实验十三 最小生成树的 Kruskal 算法 20 实验十四 判别图的连通性 21 实验十五 求无向图中顶点的度数 23 实验十六 求有向图中顶点的度数 24 第四章 代数系统 25 实验十七 判断是否为代数系统的算法 25 实验十八 判断是否为群的算法 26 第五章 数理逻辑 28 实验十九 构造合式公式的真值表 28 3 第一章第一章 集合集合 实验一实验一 集合的运算集合的运算 一、求集合的并集一、求集合的并集 1 1、实验类型：、实验类型：操作性 2 2、实验目的、实验目的 通过编程实现求给定集合 A 和 B 的并集 C（C=AB）的运算。 3 3、 实验内容实验内容 已知所给集合 A 和 B，求 A 与 B 的并集 C（C=AB） 。 4 4、实验原理、实验原理 因为并集的定义为：C=x|xAxB，所以，只要将集合 A 与 B 合在一起就 得到了并集 C。但是，在一个集合中，同样的元素没必要出现两次或两次以上，所 以，在将集合 A 送入并集 C 后，应将集合 B 中与 A 中相同的元素删除，再将集合 B 送入并集 C 之中。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turbocurboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习集合运算中交集的定义，实验由一人一组完成。所编程序能够通过编译， 并能够实现求两个给定集合的交集。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 集合 B 的元素个数送 M，集合 A 的元素个数送 N。 （2） AC。 （3） 1i。 （4） 若 i M,则结束。 （5） 否则，对于 j=1，2，.，n，判断：bi=aj，若相等，则转（7） 。 （6） 否则，biC。 （7） i+1i，转（4） 。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求给定集合 A 和 B 的并集。 （3）写出实验结束时的程序清单及运行结果及实验总结。 4 二、求集合的交集二、求集合的交集 1 1、实验类型：、实验类型：操作性 2 2、实验目的、实验目的 通过编程实现求给定集合 A 和 B 的交集 C（C=AB）的运算。 3 3、实验内容、实验内容 已知所给集合 A 和 B，求 A 与 B 的交集 C（C=AB） 4 4、实验原理、实验原理 根据交集的定义：C=x|xAxB，我们将集合 A 的各个元素与集合 B 的元 素进行比较，若在集合 B 中存在某个元素并和集合 A 中一元素相等，则将该元素送 入交集 C 之中。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习集合运算中并集的定义，实验由一人一组完成。所编程序能够通过编译， 并能够实现求两个给定集合的并集。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 将集合 A 的元素送 N。 （2） 1i （3） 若 iN,则结束。 （4） 否则，将 ai与集合 B 中的每个元素进行比较，若 ai与集合 B 中所有元素 均不相同，则转（6） 。 （5） 否则，aiC。 （6） i+1i，转（3） 。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序给定集合 A 和 B 的交集。 （3）写出实验结束时的程序清单及运行结果及实验总结。 5 三、求集合的差集三、求集合的差集 1 1、实验类型：、实验类型：操作性 2 2、实验目的、实验目的 通过编程实现求给定集合 A 和 B 的差集 C（C=A-B）的运算。 3 3、实验内容、实验内容 已知所给集合 A 和 B，求 A 与 B 的差集 C（C=A-B） 。 4 4、实验原理、实验原理 差集 C 的定义：差集 C=x|xAxB，即对于集合 A 中的元素 ai，若不存在 bjB（j=1，2，m） ，使得 ai=bj，则 ai 差集 C。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习集合运算中差集的定义，实验由一人一组完成。所编程序能够通过编译， 并能够实现求两个给定集合的差集。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 将集合 A 的元素个数送 N。 （2） 1i。 （3） iN，则结束。 （4） 否则，将 ai与集合 B 中的每个元素相比较，若 ai 与集合 B 中的某个元素 相同，则转（6） 。 （5） 否则，aiC。 （6） i+1i，转（3） 。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序给定集合 A 和 B 的差集。 （3）写出实验结束时的程序清单及运行结果及实验总结。 6 实验二实验二 求集合的笛卡儿乘积求集合的笛卡儿乘积 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过编程实现求给定集合 A 和 B 的笛卡儿乘积 C（C=AB）的运算。 3 3、实验内容、实验内容 已知所给集合 A 和 B，求 A 与 B 的笛卡儿乘积 C（C=AB） 。 4 4、实验原理、实验原理 笛卡儿乘积是以有序偶为元素组成的集合，它的定义为 C=|xAyB。 所以，欲求笛卡儿乘积。只需取尽由集合 A 的元素及集合 B 的元素，并构成序偶 送入 C 之中即可。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习笛卡儿乘积的定义，实验由一人一组完成。所编程序能够通过编译，并能 够实现求两个给定集合的笛卡儿乘积。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 将集合 A 的元素个数送入 N。 （2） 将集合 B 的元素个数送入 M。 （3） 1i。 （4） 若 iN,则结束。 （5） 1j。 （6） 若 jM，则转（9） 。 （7） C。 （8） j+1j，转（6） 。 （9） i+1i，转（4） 。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序给定集合 A 和 B 的交集。 （3）写出实验结束时的程序清单及运行结果及实验总结。 9 9、思考题、思考题 如何编程实现求有限个集合（集合的个数大于 2）的笛卡尔乘积。 7 第二章第二章 关系关系 实验三实验三 判断关系判断关系 R 的性质的性质 一、判断关系一、判断关系 R 是否为自反关系是否为自反关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学 生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3 3、实验内容、实验内容 已知关系 R 由关系矩阵 M 给出，要求判断由 M 表示的这个关系是否为自反关 系。 4 4、实验原理、实验原理 从给定的关系矩阵来断判关系 R 是否为自反是很容易的。若 M（R 的关系矩阵） 的主对角线元素均为 1，则 R 是自反关系；若 M（R 的关系矩阵）的主对角线元素 均为 0，则 R 是反自反关系；若 M（R 的关系矩阵）的主对角线元素既有 1 又有 0， 则 R 既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序 给出。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现 对给定集合上的关系自反性质的判定。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 输入关系矩阵 M（M 为 n 阶方阵） 。 （2） 判断自反性，对于 i=1，2，.，n；若存在 mii=0，则 R 不是自反的； 若存在 mii=1，则 R 是自反的；否则 R 既不是自反关系也不是反自反 关系。 （3） 输出判断结果。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序判断给定集合上的关系是否为自反的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8 二、二、 判断关系判断关系 R 是否为对称关系是否为对称关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学 生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3 3、实验内容、实验内容 已知关系 R 由关系矩阵 M 给出，要求判断由 M 表示的这个关系是否为对称关 系。 4 4、实验原理、实验原理 从给定的关系矩阵来判断关系 R 是否为对称是很容易的。若 M（R 的关系矩阵） 为对称矩阵，则 R 是对称关系；若 M 为反对称矩阵，则 R 是反对称关系。因为 R 为 对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给 出。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现 对给定集合上的关系对称性质的判定。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 输入关系矩阵 M（M 为 n 阶方阵） ； （2） 判断对称性，对于 i=2，3，.，n；j=1，2,，i-1，若存在 mij=mji，则 R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序判断给定集合上的关系是否为对称的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 9 三、三、 判关系判关系 R 是否为可传递关系是否为可传递关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现对给定集合上的关系是否为传递关系的判断，加深学 生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3 3、实验内容、实验内容 已知关系 R 由关系矩阵 M 给出，要求判断由 M 表示的这个关系是否为传递关 系。 4 4、实验原理、实验原理 一个关系 R 的可传递性定义告诉我们，若关系 R 是可传递的，则必有： mik=1mkj=1 mij=1。这个式子也可改写成为： mij =0 mik =0mkj=0。我们可 以根据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要 条件，所以，本算法也可以作为判等价关系算法的子程序给出。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现 对给定集合上的关系传递性质的判定。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）设计出类 c 的算法并编写一个程序判断给定集合上的关系是否为传递的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8 8、思考题、思考题 写出另一种判断关系传递性的算法，即在 M(RR)中，若任意rij=1 ，则 MR 中相应的元素rij=1，并据此设计出关系传递性质判断的程序。 10 实验四实验四 判断关系判断关系 R 是否为等价关系是否为等价关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关 系的判断，加深学生对关系性质的理解，掌握用矩阵来判断等价关系的方法。 3 3、实验内容、实验内容 给定 R 的关系矩阵，据此判断所给关系 R 是否为等价关系。 4 4、实验原理、实验原理 设 R 为非空集合 A 上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系的性质，实验由几个人一组完成。所编程序能够通过编译，并能够实 现对给定集合上的关系性质的判定。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序判断给定集合上的关系是否为等价关系。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8 8、思考题、思考题 （1）设计一个程序，求出对给定的有限集合的所有划分。 （2）集合 X=a,b,c,d,e,f,并且 X 中有关系 R=, ，,，编程求解 R 的关系矩阵及 X 对 R 的商集。 11 实验五实验五 求等价类求等价类 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关 系的判断，加深学生对等价关系和等价类的理解，掌握求等价类的方法。 3 3、实验内容、实验内容 给定一个集合1，2，n，及其上的一个等价关系 R，求 R 上的等价类。 4 4、实验原理、实验原理 给定任意关系，欲判断 R 是否为等价关系，可用实验八所给出的程序。但是， 如果给定一个等价关系，那么它的关系矩阵必为对称矩阵。为了节省存储空间，只 要存放关系矩阵的一半就可以了（另一半与这一半相同） 。我们可以用一维数组来存 放关系矩阵的下三角矩阵（包括主对角线在内） ，具体对应关系如下： 根据等价类的定义可知，等价类内的各元素之间均有 R 关系，所以在构造等价 类时，只要依据所给关系矩阵，把所有相互有 R 关系的各元素归为一类就可以了。 在输出时，把每一类显示在同一行上。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习等价关系和等价类的定义，实验由几个人一组完成。所编程序能够通过编 译，并能够实现求出给定集合上等价关系的等价类。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求出给定集合上的等价关系的等价类。 （3）写出实验结束时的程序清单及运行结果及实验总结。 12 实验六实验六 由两个已知关系通过合成构造新的关系由两个已知关系通过合成构造新的关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求对给定的关系的合成关系，加深学生对合成关系运 算的理解。 3 3、实验内容、实验内容 设关系 A 是从集合 X=1，2，.，n到集合 Y=1，2，m的二元关系， 而关系 B 是从集合 Y 到集合 Z=1，2，.，p的二元关系，求 A 与 B 的合成关系 C。 4 4、实验原理、实验原理 由关系合成的定义可知：A B=|有 yY 使A 且B。若 用关系矩阵来表示关系，则关系的合成运算类似于数值矩阵的乘法。不同的是用 “”代替乘，用“”代替加。其中， 00=0，00=0，01=1，01=0，10=1，10=0，11=1，11=1 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系合成的定义，实验由一人一组完成。所编程序能够通过编译，并能够 实现求给定集合上的关系的合成的运算。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）设计出类 c 的算法并编写一个程序求出给定的两个关系的合成关系。 （3）写出实验结束时的程序清单及运行结果及实验总结。 13 实验七实验七 关系的闭包运算关系的闭包运算 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的 概念的理解。 3 3、实验内容、实验内容 给定关系 R，求 R 的自反闭包及 R 的对称闭包。 4 4、实验原理、实验原理 若关系 R 的关系矩阵为 M，而自反闭包为 A（即 r（R）=A） ，对称闭包为 B（即 S（R）=B） ，则 A=MI B=MMT 其中，I 为恒等矩阵，MT为 M 的转置矩阵。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系闭包的定义，实验由几人一组完成。所编程序能够通过编译，并能够 实现求出给定关系的闭包的运算。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求出给定关系的闭包。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8 8、思考题、思考题 设计出求关系 R 的传递闭包的 Warshall 算法的程序。 14 实验八实验八 求关系个数的运算求关系个数的运算 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求给定集合上关系的个数，加深学生对关系概念的理 解。 3 3、实验内容、实验内容 给定一个 4 元素集合 A，求出 A 上所有不同的关系并显示出来。 4 4、实验原理、实验原理 设A,B为集合,AB的任何子集所定义的二元关系叫做从 A 到 B 的二元关系, 当 A=B 时则叫做 A上的二元关系. 关系的计数：若|A|=n, |B|=m, |AB|=nm, AB 的子集有 2nm 个。所以从 A 到 B 有 2nm 个不同的二元关系. |A|=n, A 上有个不同的二元关系. 2 2n 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系的定义，实验由几人一组完成。所编程序能够通过编译，能够实现求 出给定的 4 元素集合 A 上所有不同的二元关系并显示出来。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 算法并编写一个程序求出给定的 4 元素集合 A 上所有不同的二元关系。 （3）显示所有求出的二元关系。 （4）写出实验结束时的程序清单及运行结果及实验总结。 8 8、思考题、思考题 设计出求 n 个元素集合 A 上所有不同关系的程序。 15 实验九实验九 求自反关系和对称关系的运算求自反关系和对称关系的运算 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求给定集合上所有不同的自反关系和对称关系，加深 学生对关系性质的理解。 3 3、实验内容、实验内容 给定一个 5 元素集合 A，求出 A 上所有不同的自反关系、对称关系和传递关系 并显示出来。 4 4、实验原理、实验原理 设 R 为集合 A 上的关系，如果对 A 中每一 x,都有 xRx,那么 R 是自反的。即 A 上 的关系 R 是自反的（Reflexive） ；若xy(x,yARR),则称 R 为 A 上对称的(symmetric)关系；若 xyz(x,y,zARRR),则称 R 是 A 上的传递关系。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习关系性质的定义，实验由几人一组完成。所编程序能够通过编译，能够实 现求出给定的 5 元素集合 A 上所有不同的自反关系和对称关系并显示出来。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求出给定的 6 元素集合 A 上所有不同的自反关 系和对称关系。 （3）显示所有求出的自反关系和对称关系。 （4）写出实验结束时的程序清单及运行结果及实验总结。 16 实验十实验十 求集合求集合 A 上所有等价关系和偏序关系上所有等价关系和偏序关系 一、求集合一、求集合 A 上所有等价关系上所有等价关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求给定集合上所有不同的等价关系，加深学生对等价 关系定义及性质的理解。 3 3、实验内容、实验内容 给定一个 7 元素集合 A，求出 A 上所有不同的等价关系并显示出来。 4 4、实验原理、实验原理 设 R 为非空集合 A 上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习等价关系的定义和性质，实验由几人一组完成。所编程序能够通过编译， 能够实现求出给定的 7 元素集合 A 上所有不同的等价关系并显示出来。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求出给定的 7 元素集合 A 上所有不同的等价关 系。 （3）显示所有求出的等价关系。 （4）写出实验结束时的程序清单及运行结果及实验总结。 17 二、求集合二、求集合 A 上的所有偏序关系上的所有偏序关系 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求给定集合上所有不同的偏序关系，加深学生对偏序 关系定义及性质的理解。 3 3、实验内容、实验内容 给定一个 5 元素集合 A，求出 A 上所有不同的偏序关系并显示出来。 4 4、实验原理、实验原理 设 R 为非空集合 A 上的关系，如果 R 是自反的、反对称的和传递的, 则称 R 为 A 上的偏序关系。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习偏序关系的定义和性质，实验由几人一组完成。所编程序能够通过编译， 能够实现求出给定的 5 元素集合 A 上所有不同的偏序关系并显示出来。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并编写一个程序求出给定的 5 元素集合 A 上所有不同的偏序关 系。 （3）显示所有求出的偏序关系。 （4）写出实验结束时的程序清单及运行结果及实验总结。 18 实验十一实验十一 求满射函数求满射函数 1 1、实验类型：、实验类型：操作性 2 2、实验目的、实验目的 通过算法设计并编程实现求出从集合 A 到 B 上的所有满射函数的个数，加深学 生对函数性质的理解。 3 3、实验内容、实验内容 设 A、B 为有限集合，且|A|=m，|B|=n，求出从集合 A 到 B 的所有满射函数个数。 4 4、实验原理、实验原理 从 A 到 B 的满射函数定义为：设 f : AB,若 ranf = B, 则称 f : AB是满射 的（或称为映到的） ，函数 f 为满射的必要条件是 |A|B|。否则就不是满射函数 了。对于所给的问题，可以使用公式： F=F=+ +.+.+ n n C m n 1n n C m n) 1( 2n n C m n)2( 1 ) 1( n1 n C m 1 来求得其解。但是在这儿，我们也可以使用计算机中常用的一种方法枚举法来 求解。 枚举法就是一个个的列出所有满足条件的函数，并将其记录下来，当枚举结束 时就可得到欲求函数的数目。对于上面提出的问题，相当于把 n 个不同的数字放到 m 个位置上去的所有不同的方法。其中，数字是可重复出现的，但是每个数字必须 都出现过至少一次才是满射函数。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 预习函数的定义和函数的性质，实验由几人一组完成。所设计的程序能够通过 编译，并能够实现求从集合 A 到 B 上的所有满射函数的个数。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）设计出类 c 的算法并编写一个程序求出从集合 A 到 B 上的所有满射函数的个数。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8 8、思考题、思考题 设计出一个类 c 的算法，并编写一个程序求出从集合 A 到 B 上的所有单射函数 19 的个数。 20 第三章第三章 图论图论 实验十二实验十二 求可达矩阵的求可达矩阵的WarshallWarshall算法算法 1 1、实验类型：、实验类型：操作性 2 2、实验目的、实验目的 通过算法设计并编程实现求出给定 n 个结点的图 G 的可达矩阵 P，加深学生对 可达矩阵的理解。 3 3、实验内容、实验内容 给定 n 个结点的图 G 的邻接矩阵 A，求 G 的可达矩阵 P。 4 4、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 5 5、实验要求、实验要求 复习图的矩阵表示部分的内容，实验由一人一组完成。所设计的程序能够通过 编译，并能够实现从给定 n 个结点的图 G 的邻接矩阵 A，求出 G 的可达矩阵 P 6 6、实验步骤及注意事项、实验步骤及注意事项 （1） 将图 G 的邻接矩阵送入 P（n，n）中。 （2） 1i。 （3） 1j。 （4） 对于 k=1，2，n，作：Pjk（PjiPik）Pjk （5） j+1j，若 jn，则转（4） 。 （6） i+1i，若 in，则转（3） ，否则结束。 7 7、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法并写出一个程序求给定 n 个结点的图 G 的可达矩阵 P （3）写出实验结束时的程序清单及运行结果及实验总结。 21 实验十三实验十三 最小生成树的最小生成树的 Kruskal 算法算法 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学 生对求最小生成树的 Kruskal 算法的理解。 3 3、实验内容、实验内容 给定无向连通加权图，编程设计求出其一棵最小生成树。 4 4、实验原理、实验原理 设所给定无向连通加权图具有 n 个结点，m 条边，首先，将各条边的权按从小 到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置 某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有 n-1 条 边时，我们所得到的就是一棵最小生成树。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译， 并能够求出给定无向连通加权图的一棵最小生成树。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1） 边依小到大顺序得 l1，l2，lm。 （2） 置初值：S，0i，1j。 （3） 若 i=n-1，则转（6） 。 （4） 若生成树边集 S 并入一条新的边 lj之后产生的回路，则 j+1j，并转 （4） 。 （5） 否则，i+1i；ljS（i） ；j+1j，转（3） 。 （6） 输出最小生成树 S。 （7） 结束。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。 （3）写出实验结束时的程序清单及运行结果及实验总结。 22 实验十四实验十四 判别图的连通性判别图的连通性 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现，使学生掌握利用计算机语言判别图的连通性的基本 方法。 3 3、实验内容、实验内容 给定 n 个结点的有向图的邻接矩阵，可判断该图是否为强连通的，单向连通的， 或弱连通的。 4 4、实验原理、实验原理 对于给定的邻接矩阵 A，我们可以用前面给出的可达矩阵 Warshall 算法求出 A 所表示的图的可达矩阵 P。对于可达矩阵 P 来说，如果 P 的所有元素均为 1，则所给 的有向图是强连通的；对于 P 的所有元素（除主对角线元素外）Pij来说，均有： Pij+Pji0，则所给有向图是单向连通的。当所给有向图既不是强连通的，又不是单 向连通的时候，我们改造邻接矩阵为：对于矩阵 A 中所有的元素（除主对角线的元 素外）aij，若 aij=1 或 aji=1，则 1aij且 1aji。对于这样改造之后所得到的新 的矩阵 A （A相当于原有向图忽略方向之后所得到的无向图的邻接矩阵） ，再用前 面所述的方法进行判断，当 P的所有元素（除主对角线的元素外）均为 1 时，原 有向图是弱连通图；否则，原有向图是不连通的。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习图的强连通、单向连通和弱连通的定义，实验由几人一组完成。所编程序 能够通过编译，并能够对给定 n 个结点的有向图的邻接矩阵，判断该图是否为强连 通的，单向连通的，或弱连通的。 7 7、实验步骤及注意事项、实验步骤及注意事项 （1）输入邻接矩阵 A（n，n） 。 （2）A（n，n）P（n，n） 。 （3）调用求可达矩阵子程序求出可达矩阵 P。 （4）调用强连通或单向连通子程序。 （5）若为强连通或单向连通的，则输出其标志，转结束；否则转（6） 。 （6）改造 A 阵为A ，且 A P（n,n） 。 23 （7）调用求可达矩阵子程序。 （8）调用判断连通或单向连通子程序。 （9）若为强连通的，则输出原有向图是弱连通的；否则输出原有向图是非连通的。 （10）结束。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法，并编写一个程序求出给定 n 个结点的有向图的邻接矩阵，据 此判断该图是否为强连通的，单向连通的，或弱连通的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 24 实验十五实验十五 求无向图中顶点的度数求无向图中顶点的度数 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求出给定无向图顶点的度数，加深学生对关联及度的 定义的理解。 3 3、实验内容、实验内容 给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 4 4、实验原理、实验原理 设无向图 G=, ek=(vi,vj)E, 称 vi , vj为 ek 的端点, ek与 vi (vj)关联。若 vi= vj，则称 ek 为环 loop. 无边关联的顶点称作孤立点. 若 vi vj, 则称 ek 与 vi (vj)的关 联次数为 1; 若 vi = vj, 则称 ek 与 vi 的关联次数为 2; 若 vi不是边 e 的端点, 则称 e 与 vi 的关联次数为 0。设 G=为无向图, vV,v 的度数(度) d(v)是 v 作为边的端 点次数之和。 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习无向图中关联和度的定义，实验由一人一组完成。所设计程序能够通过编 译；并能够根据给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法，并写一个程序求出给定无向图的各边所关联的顶点对的每个 顶点的度数。 （3）写出实验结束时的程序清单及运行结果及实验总结。 25 实验十六实验十六 求有向图中顶点的度数求有向图中顶点的度数 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现求出给定有向图顶点的度数，加深学生对关联及出度 和入度的定义的理解。 3 3、实验内容、实验内容 给定有向图的各边所关联的有序顶点对，编程设计求出每个顶点的入度和出度。 4 4、实验原理、实验原理 设有向图 D=, 其中 V 称为顶点集, 其元素称为顶点或结点; E 是 VV 的多重子集, 称为边集, 其元素称为有向边，简称边。对有向图. 设 ek = vi, vj 是有 向图的一条边, 又称 vi是 ek的始点, vj是 ek的终点, vi邻接到 vj, vj邻接于 vi。 v 的入度 d(v)是 v 作为边的终点次数之和；v 的出度 d+(v)是 v 作为边的始点次 数之和；v 的度数(度) d(v)是 v 作为边的端点次数之和。其中 d(v)= d+(v)+ d(v) 5 5、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 6 6、实验要求、实验要求 复习有向图中关联、邻接和入度及出度的定义，实验由一人一组完成。所设计 程序能够通过编译；并能够根据给定无向图的各边所关联的有序顶点对，编程设计 求出每个顶点的入度和出度。 8 8、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法，并写一个程序求出给定有向图的各边所关联的顶点对的每个 顶点的入度和出度。 （3）写出实验结束时的程序清单及运行结果及实验总结。 26 第四章第四章 代数系统代数系统 实验十七实验十七 判断是否为代数系统的算法判断是否为代数系统的算法 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现加深学生对代数系统的定义的理解。 3 3、实验内容、实验内容 给定一个数字集合 X=0，1，n，并给出一个运算*（*运算由运算表给 出） ，要求能够判断出： （1）是否为代数系统。 （2）* 运算是否是可交换的。 （3）* 运算是否是可结合的。 4 4、实验仪器设备或软件环境及工具、实验仪器设备或软件环境及工具 运行 Windows 或 Linux 操作系统的 PC 机，具有 gcc(Linux)、 Turboc、Vc(Windows)等 C 语言的编译环境。 5 5、实验要求、实验要求 复习代数系统的定义，实验由几人一组完成。所编程序能够通过编译，并能够 对给定的一个数字集合 X=0，1，n与一个运算*（*运算由运算表给出） ，判 断出是否为代数系统、* 运算是否是可交换的、* 运算是否是可结合的。 6 6、实验报告要求、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类 c 的算法，并编写一个程序判断出是否为代数系统、* 运算是否 是可交换的、* 运算是否是可结合的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 7 7、思考题、思考题 如果所给集合 X 由字母组成，如何编程判断是否为代数系统。 27 实验十八实验十八 判断是否为群的算法判断是否为群的算法 1 1、实验类型：、实验类型：设计性 2 2、实验目的、实验目的 通过算法设计并编程实现加深学生对半群、含幺半群和群的定义的理解。 3 3、实验内容、实验内容 给出一个代数系统，其中：G=1，2，n，* 运算由运算表矩阵给出， 要判断： （1）是否为半群； （2）是否为含幺半群； （3）是否为群。 4 4、实验原理、实验原理 对于代数系统，若*运算是可