关系是一个集合与另一个集合的笛卡尔积的子集。一个关系包含了它所定义的集合中各元素的有序对。
什么是偏序关系？
如果集合 A 上的关系 R 满足以下条件，则称其为偏序关系：
- 自反关系：对于所有 a ∈ A，都有 ∈ R，即对集合 A 中所有的 a，都满足 aRa。
- 反对称关系：对于所有 a, b ∈ A，如果 ∈ R，则 ∉ R 或者 a = b。
- 传递关系：对于所有 a, b, c ∈ A，如果 ∈ R 且 ∈ R，则 ∈ R。
其中 R 是 (A x A) 的子集，即集合 A 与其自身的笛卡尔积。
示例：
> 考虑集合 A = {a, b}
> 关系 R = {(a, a), (b, b), (a, b), (b, a)} 不是偏序关系，因为对于元组，存在元组，但是
> 关系 R = {(a, a), (a, b), (b, b)} 是一个偏序关系。
偏序关系的性质：
偏序关系具有以下几个性质：
- 非空集合上的空关系永远不是偏序关系。
- 非空集合上的全关系永远不是偏序关系。
- 最小的偏序关系将只包含形如 aRa 的元组（即自反元组）。
如何验证偏序关系？
识别或验证给定关系是否为偏序关系的过程如下：
- 检查该关系是否是自反的。
- 检查该关系是否是反对称的。
- 检查该关系是否是传递的。
让我们通过下面的图解来更好地理解。
图解说明：
> 考虑集合 R = {(1, 1), (1, 3), (1, 4), (2, 2), (2, 1), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (4, 3)}
>
> 存在元组 (1, 1), (2, 2), (3, 3), (4, 4)：
> ⇒ 这满足了自反性条件。
>
> 传递性条件也得到了满足。
>
> 对于元组 (4, 3)：
> ⇒ 关系 (3, 4) 存在
> ⇒ 这不满足反对称性条件。
> 所以该关系不是反对称的。
>
> 因此，这不是一个偏序关系。
下面是用于检查给定关系是否为偏序关系的代码：
C++
// C++ code to check if a relation is partial order
#include
using namespace std;
// Class to define a relation
class Relation {
public:
bool checkPartialOrder(set A,
set<pair > R)
{
bool transitive = checkTransitive(R);
bool antisymmetric = checkAntiSymmetric(R);
bool reflexive = checkReflexive(A, R);
return (transitive && antisymmetric && reflexive);
}
// Function to check transitive relation
bool checkTransitive(set<pair > R)
{
// Empty relation is always transitive
if (R.size() == 0) {
return true;
}
// Create a dictionary to store tuple
// as key value pair
map<int, set > tup;
// Creating dictionary of relation
// where (a) is key and (b) is value
for (auto i = R.begin(); i != R.end(); i++) {
if (tup.find(i->first) == tup.end()) {
set temp;
temp.insert(i->second);
tup.insert(
pair<int, set >(i->first, temp));
}
else {
tup.at(i->first).insert(i->second);
}
}
for (auto a = tup.begin(); a != tup.end(); a++) {
// Set of all b‘s related with a
set allbin_aRb = tup.at(a->first);
// Taking all c‘s from each b one by one
for (int b : allbin_aRb) {
if (tup.find(b) != tup.end()
&& a->first != b) {
// Set of all c‘s related with b
set allcin_bRc = tup.at(b);
// All c‘s related with each b must be
// subset of all b‘s related with a
for (int c : allcin_bRc) {
if (allbin_aRb.find(c)
== allbin_aRb.end()) {
return false;
}
}
}
}
}
// For all aRb and bRc there exist aRc
// in relation R
return true;
}
// Function to check antisymmetric relation
bool checkAntiSymmetric(set<pair > R)
{
// Empty relation is always anti-symmetric
if (R.size() == 0) {
return true;
}
for (auto i = R.begin(); i != R.end(); i++) {
if (i->second != i->first) {
// Not a aRa tuple
// making a mirror tuple
auto temp = make_pair(i->second, i->first);
if (R.find(temp) != R.end()) {
// If bRa tuple exists
// in relation R
return false;
}
}
}
// bRa tuples does not exist
// for all aRb in relation R