离散数学实验二柏超宇

1、实 验 报 告（2015 / 2016 学年 第 二 学期）课程名称离散数学实验名称集合上二元关系性质判定的实现实验时间2016年4月26日指导单位计算机科学与技术系指导教师罗卫兰学生姓名柏超宇班级学号Q15010125学院(系)贝尔英才学院专 业信息科技英才班实 验 报 告实验名称集合上二元关系性质判定的实现指导教师罗卫兰实验类型实验学时4实验时间4.26一、 实验目的和要求正确判定任意二元关系的自反性、对称性、传递性、反自反性和反对称性。二、实验环境(实验设备)硬件：电脑软件：操作系统：Windows 7编程软件：Dev C+三、实验原理及内容首先输入关系中包含元素的个数，其次输入各个元素

2、的关系，以0 0结束，随后根据矩阵的性质和相应矩阵运算得出该二元关系具有的性质。1、问题引入一个有n个顶点的有向图的传递闭包为：有向图中的初始路径可达情况可以参见其邻接矩阵A，邻接矩阵中Ai,j表示i到j是否直接可达，若直接可达，则Ai,j记为1，否则记为0；两个有向图中i到j有路径表示从i点开始经过其他点（或者不经过其他点）能够到达j点，如果i到j有路径，则将Ti,j设置为1，否则设置为0；有向图的传递闭包表示从邻接矩阵A出发，求的所有节点间的路径可达情况，该矩阵就为所要求的传递闭包矩阵。例如：有向图为：由该有向图可以得到初始的邻接矩阵为：那么warshall传递闭包算法的目的就是由邻接矩阵

3、出发，进行探索求出最终的传递闭包：2、动态规划求解思路动态规划将问题分段，本例warshall算法是通过一系列n阶矩阵r（k）来构造最终阶段n阶传递闭包矩阵r（n）    R(k) 由它的前趋 R(k-1) 计算得到（分级推进计算）。    R(0) 该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的任意顶点出发的路径不含有中间顶点，此即邻接矩阵。    R(1) 允许路径中包含第1个顶点（本例编号 1）作为中间顶点。    R(2) 允许路径

4、中包含前2个顶点（本例编号1 2）作为中间顶点。    R(k) 允许路径中包含前k个顶点作为中间顶点。    R(n) 允许路径中包含全部 n 个顶点作为中间顶点。    每个后继矩阵 R(k) 对其前趋 R(k-1) 来说，在路径上允许增加一个顶点， 因此有可能包含更多的1（增加前为1的在增加后依然为1）。3、具体的算法描述1 warshall（A1.n,1.n2 r(0)<-A;3 for(k=1;k<=n;k+)4 for(i=1;i<=n

5、;i+)5 for(j=1;j<=n;j+)6 r(k)i,j=r(k-1)i,j or(r(k-1)i,k and r(k-1)k,j);7 return r(n); 其他几个性质的代码 ：int zifan()int flag1=1;for(i=1;i<=n;i+)if(aii!=1)flag1=0;break;return flag1;int fanzifan()int flag2=1;for(i=1;i<=n;i+)if(aii=1)flag2=0;break;return flag2;int duichen()int flag3=1;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(aij!=aji)flag3=0;break;return flag3; 最后我们可以通过返回flag来确定该矩阵具有的相应性质。 四、实验小结（包括问题和解决方法、心得体会、意见与建议等）