偏序关系_如何证明一个关系是偏序关系

偏序关系

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

给定有限集上二元关系的关系矩阵，确定这个关系是否是偏序关系。

Input

多组测试数据，对于每组测试数据，第1行输入正整数n（1 <= n <= 100），第2行至第n+1行输入n行n列的关系矩阵。

Output

对于每组测试数据，若为偏序关系，则输出yes，反之，则输出no。

Sample Input

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 0 0 1
0 1 0 0
0 0 1 0
1 0 0 1

Sample Output

yes
no

Hint

偏序关系形式定义：设R是集合A上的一个二元关系，若R满足自反性、反对称性、传递性，则称R为A上的偏序关系。

Source

xry-fhf

 

这个题目要求判断集合的偏序关系。偏序关系的形式定义在题目下方已经给出，要满足自反性，反对称性，和传递性。

自反性在矩阵中的体现就是矩阵的对角线元素都是1.

反对称性在矩阵中的体现就是当且仅当关系矩阵中以主对角线对称的元素不能同时为1. 

而传递性的话就有点复杂，有两种方法判断传递性。

 

第一种就是利用（复合矩阵法）矩阵乘法，是线性代数中的一种方法。

思路：设M是R的关系矩阵，若M*M为M的子集，则R具有传递性。

判断方法：计算M*M，M*M为M的子集的意思是，在方阵对应的同行同列的位置，若对于M，该数为0，则对于M*M，该数必为零，否则R不具有传递性。即：若M中的a[i][j] == 0, 则必有M*M中的c[i][j] == 0。

 

第二种就是中途点判别法。

思路：利用矩阵表示方法，遍历这个矩阵如果遇到一个等于1的位置，记录位置，利用其纵坐标当下一个数的横坐标，在此横坐标下找到是1的位置，记录这个位置，再利用上一个数位置的横坐标和这个数的纵坐标找到一个新的位置，如果这个位置上是1，那么这个数就具有可传递性，然后继续遍历进行这个循环操作，知道检查到所有的数都对上了，这个二元关系才可说具有可传递性，有一个不符的都不是可传递性的二元关系。

代码实现起来或许有些费事，但是如果我们只判断不是偏序关系的情况那么代码就缩减了许多。

具体见AC代码。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, i, a[102][102], b, j, k;
    while(~scanf("%d", &n))
    {
        b = 0;//b作为判断是否满足偏序关系的一个标准
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                scanf("%d", &a[i][j]);//矩阵的输入
            }
        }
        for(i = 0; i < n && b != 1; i++)
        {
            if(a[i][i] == 0)//判断自反性，对角线元素都是1，否则break跳出循环
            {
                b = 1;
                break;
            }
            for(j = 0; j < n && b != 1; j++)//在满足自反性的条件下判断是否满足反对称性
            {
                if(i != j)//除去对角线元素
                {
                    if(a[i][j] == 1 && a[j][i] == 1)//以主对角线对称的元素不能同时为1
                    {
                        b = 1;//同时等于1跳出循环
                        break;
                    }
                    if(a[i][j])//这里利用的是第二种方法中途点判别法a[i][j]==1,将纵坐标j作为下一个元素的横坐标
                    {
                        for(k = 0; k < n; k++)
                        {
                            if(a[j][k])//a[j][k]==1
                            {
                                if(a[i][k] == 0)//如果这里a[i][k]==1则满足自反性关系继续遍历矩阵
                                {
                                    b = 1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        if(b)
        {
            printf("no\n");
        }
        else
        {
            printf("yes\n");
        }
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int n,i,k,j,a[101][101];
    while(scanf("%d",&n)!=EOF)
    {
        int f=1;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=1; i<=n; i++)
        {
            if(a[i][i]==0)
            {
                f=0;
                break;
            }
            for(j=1; j<=n; j++)
            {
                if(a[i][j]==1&&a[j][i]==1&&i!=j)
                {
                    f=0;
                    break;
                }
                if(a[i][j])
                {
                    for(k=1; k<=n; k++)
                    {
                        if(a[j][k]==1)
                        {
                            if(a[i][k]==0)
                            {
                                f=0;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if(f==1) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}