离散数学实验

博客搬家的时候忘记搬过来了,还好Coding上有存档。因为写程序的时候写了好几个版本,不知道哪个是最后版本了,所以可能有些小错误,仅供参考。

实验1:通过真值表计算主范式

要求输入命题变元的数量n和真值表,输出两种主范式。对于一个命题公式P,枚举所有命题变元的0-1组合。如果变元数为n, 需要枚举 $ 2^{n} $ 个组合。实际上就是 $[0,2^{n-1}]$ 中每一个十进制数的二进制表示(用位运算的方法)。其中二进制枚举是这个程序的重点,可以使用DFS或者直接枚举$[0,2^{n-1}]$中的数字然后通过位运算处理实现。

实验2:判断二元关系的基本性质

思路

判断五种性质就要知道原集合和关系集合,关系集合是原集合与自己的笛卡尔积的子集。就比如原集合是$A={1,2,3}$,那么

$$A^2 = A × A =\left\{ \\ <1,1>,<1,2>,<1,3>, \\ <2,1>,<2,2>,<2,3>, \\ <3,1>,<3,2>,<3,3> \right\}$$

现有关系二元组集合 $R ⊆ A^2 $,需要判断 $R$ 是否满足自反性、对称性、传递性、反自反性、反对称性 。

概念

  • 自反性:对于原来集合上的所有元素 $x_i$,都满足 $<x_i,x_i>$ 在关系集合中。
  • 对称性:$R$ 是原集合上的关系,对于每一个 $<x,y> \in R$,一定有 $<y,x> \in R$。
  • 传递性:$R$ 是原集合上的关系,如果 $<x,y> \in R$,$<y,z> \in R$,则有 $<x,z> \in R$。
  • 反自反性:对于原来集合上的所有元素 $x_i$,$<x_i,x_i>$ 都不在关系集合中。
  • 反对称性:如果 $<x,y> \in R$ 且有 $<x,y> \in R$,则必有 $x=y$

五种性质的判断

自反性

对于原来集合上的所有元素 $x_i$,都满足 $<x_i,x_i>$ 在关系集合中。

遍历原来集合上的元素,如果有一个元素不满足上面的条件就不满足这个性质,如果遍历结束之后没有一组不满足,则说明有这个性质。

对称性

$R$ 是原集合上的关系,对于每一个 $<x,y> \in R$,一定有 $<y,x> \in R$。

枚举每一个 $<x_i, y_i> \in R$,首先判断 $x_i$ 和 $y_i$ 是否都是原集合中的元素,如果是的话,需要判断 $<y_i, x_i> \in R$ 是否成立,如果不成立,则不具备对称性。在遍历完每个二元组之后如果还没有发现不符合的情况,则说明具备这个性质。

传递性

$R$ 是原集合上的关系,如果 $<x,y> \in R$,$<y,z> \in R$,则有 $<x,z> \in R$。

枚举每一个 $<x_i, y_i> \in R$,如果 $x_i$ 和 $y_i$ 都是原集合中的元素,那么我们需要去找一个对应的 $z_i$ 使得 $<y_i,z_i> \in R$,然后再判断是否有$<x_i,z_i> \in R$。

邻接矩阵或者邻接表实现。

反自反性

对于原来集合上的所有元素 $x_i$,$<x_i,x_i>$ 都不在关系集合中。

遍历原来集合上的元素,如果有一个元素不满足上面的条件就不满足这个性质,如果遍历结束之后没有一组不满足,则说明有这个性质。

和自反性类似。

反对称性

如果 $<x,y> \in R$ 且有 $<x,y> \in R$,则必有 $x=y$。

枚举每一个 $<x,y> \in R$,如果有 $<y,x> \in R$ 但是 $x ≠ y$,则不满足条件。枚举完所有二元组之后没有发现任何一组不满足条件则说明具有反对称性。

代码

Python版

C++版

闭包算法

老师讲过闭包之后写的。

实验3:盖住关系的求取与格的判定

我至今还记得这个实验每次写出一个版本都被室友Hack一下,最终老老实实写了暴力。

思路

  • 根据定义求盖住关系,根据盖住关系建图,对于盖住关系中的每一个 $<u, v>$,说明 $u$ 是 $v$ 的儿子,$v$ 是 $u$ 的父亲,建立两张图,这个关系分别对应正向图和反向图的两条边。
  • 判断格的时候,枚举每一个 $<u, v>$ ,在正向图中求他们的最近公共祖先(LCA),统计LCA的个数,当且仅当每个 $<u, v>$ 的LCA的个数为一时,盖住关系为格。
  • 如果是格,判断是否是有补格。枚举每一个 $u$,检测是否有 $v$ 满足正向图中的LCA为最大元素,反向图中的LCA为最小元素。

渐进时间复杂度

  • 求盖住关系 $\Theta(n^3), n = ||A||$
  • 判断是否为格 $\Theta(n^3), n$ 为 $ COV_A $ 中涉及到的 $A$ 中元素的个数(使用map离散化需要乘以 $\lg n$)
  • 判断是否为有补格 $\Theta(n^3), n$ 为 $ COV_A $ 中涉及到的 $A$ 中元素的个数(使用map离散化需要乘以 $\lg n$)

代码

实验4:图的生成及欧拉路的确定

判断 $n$ 个点的无向图能否被一笔画。要求:给定 $n$ 个节点的无向图,进行欧拉图和半欧拉图的判断,如果是则输出欧拉路。

建图方法

  • 邻接矩阵:矩阵 $G_{n \times n}, n$ 为节点个数,$G_{ij} = 1$ 表示一个节点 $i$ 和 $j$ 之间有一个有向边相连,显然如果 $G_{ij} = G_{ji} = 1$ 表示这个边是无向的。如果 $G_{ij} = 0$ 表示没有边相连。空间复杂度 $O(||V||^2)$ 。
  • 邻接表(常用):使用 $n$ 个列表记录每个点的邻接边集合。空间复杂度 $O(||E||)$。对于稀疏图来说邻接表比较节省空间,遍历时也更快。

连通性判断

  • 方法一:求可达性矩阵,渐进时间复杂度 $\Theta(n^4), n = ||V||$。
  • 方法二:BFS/DFS求联通块(并查集思想),对任意一个节点开始搜索并把搜索到的节点做标记,搜完之后标记如果覆盖所有的点就说明是联通的,渐进时间复杂度 $\Theta(n), n = ||V||$。

欧拉路的判定

在建图时统计每个节点的度数,保存在 deg 数组里。deg[i] 表示第 i 个节点的度数。统计完之后对 deg 数组做遍历,统计奇数的个数,如果为零说明有欧拉路(是半欧拉图),如果为二说明有欧拉回路(是欧拉图),否则就不是半欧拉图。

输出欧拉路

  • BFS:使用father数组记录路径,每次搜索完成之后递归打印。判断搜索结束的条件是已经走过的边数与图的边数相等。
  • DFS:使用栈记录路径,每次搜索完一条路径之后把栈打印出来。

渐进时间复杂度

  • 连通性判断(搜索) $\Theta(n), n = ||V||$
  • 欧拉路的判定 $\Theta(n), n = ||V||$
  • 输出欧拉路和欧拉回路具体看图的结构,不是多项式的时间复杂度

代码

 

说点什么

avatar
50
  Subscribe  
提醒