离散数学代码实现 二元关系的可传递性判断
离散数学的可传递性判断：
利用笨方法找：
利用矩阵表示方法，遍历这个矩阵如果遇到一个等于1的位置，记录位置，利用其纵坐标当下一个数的横坐标，在此横坐标下找到是1的位置，记录这个位置，在利用上一个数位置的横坐标和这个数的纵坐标找到一个新的位置，如果这个位置上是1，那么这个数就具有可传递性，然后继续遍历进行这个循环操作，知道检查到所有的数都对上了，这个二元关系才可说具有可传递性，有一个不符的都不是可传递性的二元关系。
例:
a1 a2 a3 a4 a5
a1 0 1 1 0 1
a2 0 0 1 0 1
a3 0 1 0 0 1
a4 0 1 0 0 0
a5 0 1 0 1 0
利用笨方法找：
利用矩阵表示方法，遍历这个矩阵如果遇到一个等于1的位置，记录位置，利用其纵坐标当下一个数的横坐标，在此横坐标下找到是1的位置，记录这个位置，在利用上一个数位置的横坐标和这个数的纵坐标找到一个新的位置，如果这个位置上是1，那么这个数就具有可传递性，然后继续遍历进行这个循环操作，知道检查到所有的数都对上了，这个二元关系才可说具有可传递性，有一个不符的都不是可传递性的二元关系。
例:
a1 a2 a3 a4 a5
a1 0 1 1 0 1
a2 0 0 1 0 1
a3 0 1 0 0 1
a4 0 1 0 0 0
a5 0 1 0 1 0
进行遍历的流程是这样的：开始找a11不是1，往下走a12是1，记录a12的纵坐标，当做横坐标进行遍历，第二行的第三个是1，记录a23的纵坐标和a12的横坐标找a13，查找a13是否为1，如果是1就继续进行下一步的遍历查找。直到遍历完或其中有找到的那个数不是1，不是的情况就说明这个二元关系不具有可传递性，遍历完，说明这个二元关系具有可传递性。
代码实现如下：
#include <iostream>
using namespace std;
const int MAXN = 100;
int A[MAXN][MAXN];
int main()
{
cout<<"请输入具有二元关系的两个集合的大小：";
int x , y ;
cin>>x>>y;
cout<<"请输入这两个集合的二元关系矩阵表示法：";
for(int i = 0 ; i < x ; i++)
for(int j = 0 ; j < y ; j++)
cin>>A[i][j];
int p = 0 ;
for(int i = 0 ; i < x ; i++)
{
for(int j = 0 ; j < y ; j++)
{
if( 1 == A[i][j] )
{
for(int k = 0 ; k < y ; k++)
{
if( 1 == A[j][k] && 1 != A[i][k] )
{
p = 1;
break;
}
}
}
}
}
if(p)
cout<<"这个二元关系不具备可传递性！";
else
cout<<"这个二元关系具备可传递性！";
}
利用或方法判断可传递性：
遍历流程：
a1 a2 a3 a4 a5
a1 0 1 1 0 1
a2 0 0 1 0 1
a3 0 1 0 0 1
a4 0 1 0 0 0
a5 0 1 0 1 0
遍历到a12为1了，利用第二行的或运算第一行的得到一个新的数组，利用这个新的数组与第一行进行比较，如果全对上了，说明这个数具有可传递性，如果有一个位置没对上的，说明这个数没有传递性。
代码实现如下：
#include <iostream>
using namespace std;
const int MAXN = 100;
int A[MAXN][MAXN];
int main()
{
cout<<"请输入具有二元关系的两个集合的大小：";
int x , y ;
cin>>x>>y;
cout<<"请输入这两个集合的二元关系矩阵表示法：";
for(int i = 0 ; i < x ; i++)
for(int j = 0 ; j < y ; j++)
cin>>A[i][j];
int p = 0;
int * jl = new int[y];
for(int i = 0 ; i < x ; i++)
{
for(int j = 0 ; j < y ; j++ )
{
if( 1 == A[i][j] )
{
int q = 0 ;
for(int k = 0 ; k < y ; k++)
{
jl[k] = A[i][k] | A[j][k];
}
for(int k = 0 ; k < y ; k++)
if( jl[k] == A[i][k] )
p++;
if( q != y )
{
p = 1 ;
break;
}
}
}
}
if(p)
cout<<"这个二元关系不具备可传递性！";
else
cout<<"这个二元关系具备可传递性！";
}
