离散数学中R+算法的研究与实现1 IS NOT ONLY THE IMPORTANT CONTENT OF.pdf

离散数学中 R 算法的研究与实现1 潘煜 王中生 惠燕 西安工业大学 西安 710032 摘要 摘要 关系的传递闭包R 不但是离散数学集合论中的重要内容 也是计算机理论中重要的 研究工具 根据传递闭包的相关理论可以得到传递闭包的三种求解方法 进而通过分析可以 得到求解方法的数据结构 流程图等 然后通过计算机程序将其实现 关键词关键词 传递闭包 关系 Warshall 算法 中图分类号中图分类号 TP301 文献标识码 文献标识码 A Research and realization on R algorithm in discrete mathematics PAN Yu WANG Zhong Sheng HUI Yan Xi an Technological University Xi an 710032 China Abstract Transitive closure of the relationship R is not only the important content of the set theory in discrete mathematics but also a key research tool in computer theory According to the related theory of transitive closure we can get three methods to obtain it And further through analysizing we can obtain the data structures and flow chart then it can be implemented by computer program Key words transitive closure relationship Warshall algorithm 0 引言 关系的闭包一直是离散数学集合论中研究的热点 关系的传递闭包R 是关系的闭包中 的重要内容之一 它在图论 数据库 编译原理 计算机形式语言中都有重要的应用 任一序偶的集合可以确定一个二元关系 R 二元关系 R 可以通过集合 关系图 关系 矩阵三种形式来表示 而所谓关系的传递闭包 R 是指二元关系 R 通过闭包运算得到具有传 递性的一个新的二元关系 通过对传递闭包的定义的研究可知传递闭包的求解也可以通过集 合 关系矩阵等多种方式来完成 1 基于元素观察法的传递闭包运算 定义 设 R 是 X 上的二元关系 如果有另一个关系 R 满足 1 R 是可传递的 2 R R 3 对于任何可传递的关系 R 如果有 R R 就有 R R 则称关系 R 为 R 的传递闭包 通过研究定义可以得知 定义中第一点说明所求闭包必须具有传递性 第二点说明所 求的传递闭包 R 应包含给定关系 R 即 R 是在给定关系 R 的基础上进行的扩充 第三点表 明对于任一具有传递性的关系 R R 都是其子集 综合以上三点 R 是传递闭包运算作用在 R 后 产生的在 R 的基础上具有传递性的含元素数最少的二元关系集合 因此 可以通过 观察集合元素 对 R 进行序偶扩充得到传递闭包R 举例说明 A 1 2 3 R A A R 1 2 2 3 3 1 在求 R 时观 察关系集合 R 中的各元素通过添加元素得到传递闭包R 具体步骤如表 1 表 1 观察法求 R 的过程 被观察元素 需添加元素 扩充后 R 1 2 2 3 2 3 3 1 3 1 1 2 1 3 2 1 3 2 R 1 2 2 3 3 1 1 3 2 1 3 2 1 2 2 1 2 3 3 2 3 2 2 3 1 1 2 2 3 3 R 1 2 2 3 3 1 1 3 2 1 3 2 1 1 2 2 3 3 1作者简介 潘煜 1975 男 甘肃人 西安工业大学 博士生 讲师 主要研究方向为计算机网络 对于有限集合 A 的元素较少时 这种方法很容易就能得到 R 但是当 A 中的元素较多 时 随着不断的扩充需要添加的新元素太多 这种方法就不能胜任了且不便于在计算机中实 现 2 基于矩阵的传递闭包运算 关系有多种表示形式 如 将集合元素列举表示 用矩阵的形式标示 画关系图表示 但根据计算机位的特性 用关系的矩阵形式更便于研究及用计算机语言去实现 以矩阵为计 算工具去求解传递闭包 R 的方法有两种 2 1 根据 R 1 i i R U 定理 1 设 R 为 X 上的一个二元关系 则 R 1 i i R U R R2 R3 从定理可以看出通过对关系矩阵做复合运算再求其并集可以求得传递闭包 可问题是定 理 1 中 Ri的并运算是无穷的 这在计算机中实现时就是一个死循环 无法终止的 是不可 行 因此 可以引入定理 2 来解决 定理 2 设 X 是含有 n 个元素的集合 R 是 X 上的二元关系 则存在一个正整数 k n 使得 R R R2 R3 Rk 从定理 2 可以得知 Rk不是不确定 当 X 集合中元素个数是确定有限的时 必定会出现 Rk 1 Ri i k 因此 当 Rk 1 Ri i k 就可以成为求并运算的终止条件 即 通过复合运算 求出 R2 R3 直到出现 Rk 1 Ri i k 再将上述各个集合并在一起 在计算机中体系中传递闭包是重要的研究工具 如何在计算机中实现传递闭包使其能 得到进一步的应用也是一个值得关注的问题 通过分析可以得知要实现本方法可以将其数据 结构定义成数组或链 为了简便本文利用数组给出了求解中重要的一步关系矩阵的复合运算 用 C 语言实现的关键代码 include stdio h define N 100 main int i j s 0 k n r N N b N N c N N printf 请输入你的关系矩阵的阶 n n 100 n scanf d printf 请输入你的关系矩阵 n for i 0 i n i for j 0 j n j scanf d b i j r i j 计算关系矩阵的复合关系矩阵 for i 0 i n i for j 0 j n j for c i j 0 k 0 k n k c i j r k j b i k for i 0 i n i for j 0 j n j b i j c i j 2 2 根据 Warshall 算法 通过联合运用上述两个定理可以得到传递闭包的一种解法 但是不能确定要运行多少 次才能得到 Rk 1 Ri 这样在计算机实现时就给定义算法的数据结构和选择开发的语言带来 了一定的困难和限制 为了更便于计算机上的实现 可以采用运算次数确定的 Warshall 算法 Warshall 算法是 Warshall 在 1962 年提出的一个求关系的传递闭包的有效算法 在计算机实 现时可以先用流程图将 Warshall 算法表示出来 这样更便于选择任意的语言将其实现 具体 算法的流程如图 1Warshall 算法流程图所示 开始 设 R 的关系矩阵为 M 输入数组 A m n 初始化 i j k 1 i n Y N j m Y N A j i 1 Y k n Y A j k A j k A i k k k 1 N j j 1 k 1 N i i 1 结束 图 1Warshall 算法流程图 3 结束语 关系的传递闭包是关系闭包的重要部分 对于大部分研究者研究其侧重其在数学领域 的研究 但将其作为一种研究计算机理论的工具时 本文更侧重于其利用计算机语言实现其 求解的过程 参考文献 1 左孝凌 李为鑑 刘永才 离散数学 M 上海 上海科学技术文献出版社 1982 2 严蔚敏 吴伟民 数据结构 C 语言版 M 北京 清华大学出版社 1997 3 刘伟 曹先彬 对基于 MPN 的相似重复记录识别算法的改进