【离散数学实验报告】关系性质和闭包运算

您所在的位置：网站首页 › 传递闭包三种算法 › 【离散数学实验报告】关系性质和闭包运算

【离散数学实验报告】关系性质和闭包运算

2023-11-28 21:03| 来源: 网络整理| 查看: 265

目录实验报告一、实验目的：二、实验内容：三、实验原理：四、程序代码与实验结果：实验内容（1）关系性质的判断实验内容（2）关系的闭包运算实验内容（3）Warshall算法求关系的传递闭包六、实验总结

实验报告一、实验目的：

进一步理解关系的性质的基本概念，掌握用矩阵判断关系性质的方法。掌握关系闭包运算的方法，能够用矩阵实现关系的闭包运算。提高学生编写实验报告，总结实验结果的能力，培养学生的逻辑思维能力和算法设计思想。能够独立完成简单的算法设计和分析，进一步用他们来解决实际问题，帮助学生学习掌握C和C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。

二、实验内容：

（1）根据关系矩阵判断关系的性质（自反、反自反、对称、反对称、传递）。要求在给出关系矩阵的基础上，根据关系矩阵特点完成关系性质的判断。

（2）在给出关系矩阵的基础上，用矩阵的运算完成关系的闭包运算（自反闭包、对称闭包、传递闭包）

（3）在给出关系矩阵的基础上，用Washall算法完成关系的传递闭包。

（4）以上实验内容，每个内容一组程序和实验结果，程序与实验结果要对应。关系与关系矩阵自拟，但矩阵至少为4阶。关系的难易程度及实验的完成性为主要采分点。雷同实验结果将按零分处理。

三、实验原理：

实验内容（1）关系性质的判断原理

关系的性质关系矩阵的特点

自反性主对角线元素全为1

反自反性主对角线元素全为0

对称性对称矩阵

反对称性非主对角线上的元素等于1的，与之对称的元素等于0

传递性矩阵M2中1所在的位置，M中与之相对应位置均为1

实验内容（2）关系的闭包运算矩阵计算公式

自反闭包：

对称闭包：

传递闭包：，n为矩阵M的阶数

实验内容（3）Warshall算法求关系的传递闭包

参见书中124-126页

四、程序代码与实验结果：实验内容（1）关系性质的判断

程序代码：

#include #include using namespace std; void judge_properties(const vector& matrix) { // 判断关系矩阵的性质 int n = matrix.size(); bool reflexive = true; bool irreflexive = true; bool symmetric = true; bool antisymmetric = true; bool transitive = false; // 判断自反性和反自反性 for (int i = 0; i reflexive = false; } if (matrix[i][i] != 0) { irreflexive = false; } } // 判断对称性和反对称性 for (int i = 0; i if (matrix[i][j] != matrix[j][i]) { symmetric = false; } if (matrix[i][j] == 1 && matrix[j][i] == 1 && i != j) { antisymmetric = false; } } } // 判断传递性 vector transitive_closure(matrix); for (int k = 0; k for (int j = 0; j transitive = true; } // 输出结果 cout 0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1} }; judge_properties(matrix); return 0; }

实验结果：

关系性质：自反性：是反自反性：否对称性：是反对称性：否传递性：否实验内容（2）关系的闭包运算

程序代码：

#include #include using namespace std; vector reflexivity_closure(const vector& matrix) { // 计算自反闭包 int n = matrix.size(); vector reflexive_closure(matrix); for (int i = 0; i // 计算对称闭包 int n = matrix.size(); vector symmetric_closure(matrix); for (int i = 0; i symmetric_closure[i][j] = symmetric_closure[i][j] || symmetric_closure[j][i]; } } return symmetric_closure; } vector transitivity_closure(const vector& matrix) { // 计算传递闭包 int n = matrix.size(); vector transitive_closure(matrix); for (int k = 0; k for (int j = 0; j vector matrix = { {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1} }; vector R_reflexive = reflexivity_closure(matrix); vector R_symmetric = symmetry_closure(matrix); vector R_transitive = transitivity_closure(matrix); // 输出结果 cout cout cout cout for (int i = 0; i transitive_closure[i][j] = transitive_closure[i][j] || (transitive_closure[i][k] && transitive_closure[k][j]); } } } return transitive_closure; } int main() { vector matrix = { {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1} }; vector R_transitive_warshall = warshall(matrix); // 输出结果 cout cout

【本文地址】

【离散数学实验报告】关系性质和闭包运算

【离散数学实验报告】关系性质和闭包运算

今日新闻

推荐新闻