二元关系
| 二元关系 |
数学上，二元关系用于讨论两个数学对象的联系。诸如算术中的「大于」及「等于」，几何学中的"相似"，或集合论中的"为...之元素"或"为...之子集"。二元关系有时会简称关系，但一般而言关系不必是二元的。
目录
简介
集合X与集合Y上的二元关系是R=(X,Y,G(R))，其中G(R)，称为R的图，是笛卡儿积X×Y的子集。若 (x,y) ∈G(R) ，则称x是R-关系于y，并记作xRy或R(x,y)。否则称x与y无关系R。但经常地我们把关系与其图等同起来，即：若R⊆X×Y，则R是一个关系。例如：有四件物件 {球，糖，车，枪} 及四个人 {甲，乙，丙，丁}。 若甲拥有球，乙拥有糖，及丁拥有车，即无人有枪及丙一无所有— 则二元关系"为...拥有"便是R=({球，糖，车，枪}, {甲，乙，丙，丁}, {(球,甲), (糖,乙), (车,丁)})。其中 R 的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人）组成的集合。比如有序对（球，甲）∈G(R)，所以我们可写作"球R甲"，表示球为甲所拥有。不同的关系可以有相同的图。以下的关系 ({球，糖，车，枪}, {甲，乙，丁}, {(球,甲), (糖,乙), (车,丁)} 中人人皆是物主，所以与R不同，但两者有相同的图。话虽如此，我们很多时候索性把R定义为G(R)， 而 "有序对 (x,y) ∈G(R)" 亦即是 "(x,y) ∈R"。二元关系可看作成二元函数，这种二元函数把输入元x∈X及y∈Y视为独立变量并求真伪值（即“有序对(x,y) 是或非二元关系中的一元”此一问题）。若X=Y，则称R为X上的关系。
评价
求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度；但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。反自反关系和自反关系的数目一样多。严格偏序（反自反的传递关系）的数目和偏序的一样多。全序即是那些同时是全预序的偏序。透过容斥原理的想法，可知那些既不是偏序也不是全预序的预序数目是：预序的数目，减去偏序的数目，再减去全预序的数目，最後加上全序的数目，即0, 0, 0, 3, 85, ...等价关系的数目是集合划分的数目，即贝尔数。各个二元关系之间可组成二元组（某关系及其补集），除了在n=0时，空关系的补集即其自身。那些不符合对称性的二元关系也可组成四元组（某关系、补集、逆、逆的补集）。[1]