离散数学实验报告1.docx

《离散数学》
课程设计
学院软件学院
学生姓名孟庆汉
学号 0843042109 年级2008
指导教师冯伟森
评阅意见


提交日期 2009 年 12 月 25 日
《利用Warshall算法求二元关系的可传递闭包》
学生:孟庆汉指导老师:冯伟森
摘要:当集合的阶数n较大时,求二元关系的可传递闭包的工作量是相当庞大的。+的有效方法,可在计算机上编程实现。采用C语言函数写出这个算法。程序中用m[i][j]表示关系矩阵MR的第i行第j列元素,用||表示逻辑或计算。计算R+的函数名为Warshall,它的两个形式参数m和n分别表示关系矩阵M和矩阵的行数。函数的实现实际上是一个三重循环构成。
关键字:二元关系关系矩阵可传递闭包 Warshall算法三重循环
引言
《离散数学》是现代数学的一个重要分支,也是计算机科学与技术,电子信息技术,生物技术等的核心基础课程。二元关系是离散数学中重要的内容。世界上的事物都在一定范围内以某种方式互相联系,例如天体之间可以用的是同一星系来划分,人们之间可以用是否有共同的祖先来定血缘。类似的数学或者计算机科学中的研究对象也以各种不同的形式相互联系着,例如整数之间以大小,整除或同余等关系相互连接着,命题公式之间以是否有相同的主合取范式相联系,程序中两个变量可以用是否占有同一内存地址相联系。
总之,事物之间总是可以根据需要确定相应的关系。从数学的角度来看,这类联系就是某个集合中元素之间存在的关系。一个二元关系可能具有某种性质,也可能不具有这种性质。关系的闭包就是使一个二元关系变成具有指定性质的关系,并且还要满足最小性的条件。
数学原理
设A和B都是已知的集合,R是A到B的一个确定的二元关系,那么集合R就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合
设R是集合A上的二元关系:
∈A,都满足<x,x>∈R,则称R是自反的,或称R具有自反性,即
R在A上是自反的Û("x)((x∈A)→(<x,x>∈R))=1
,y∈A,如果<x,y>∈R,那么<y,x>∈R,则称关系R是对称的,或称R具有对称性,即
R在A上是对称的Û ("x)("y)((x∈A)∧(y∈A)∧(<x,y>∈R)→(<y,x>∈R))=1
,y,z∈A,如果<x,y>∈R且<y,z>∈R,那么<x,z>∈R,则称关系R是传递的,或称R具有传递性,即
R在A上是传递的Û ("x)("y)("z)[(x∈A)∧(y∈A)∧(z∈A)∧((<x,y>∈R)∧(<y,z>∈R)→(<x,z>∈R))]=1
设R是定义在A上的二元关系,若存在A上的关系R′满足:
R′是自反的(或对称的、或可传递的),
RÍ R′,
对A上任何其它满足1)和2)的关系R〞,都有:
R′Í R〞。(表明R′的最小性)
则称R′为R的自反闭包(或对称闭包、或传递闭包),分别记为r(R)(s(R)或t(R))。
Warshall算法的基本思想
对每个结点(从第一列开始),找出所有具有到此结点的有向边的结点(即该列中元素为1的所在行的结点),再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行(