二元关系

数学上，二元关系（英语：Binary relation，或简称关系）用于讨论两种物件的连系。诸如算术中的“大于”及“等于”、几何学中的“相似”或集合论中的“为……之元素”、“为……之子集”。集合 X {displaystyle X} 与集合 Y {displaystyle Y} 上的二元关系是 R = ( X , Y , G ( R ) ) {displaystyle R=(X,Y,G(R))} ，当中 G ( R ) {displaystyle G(R)} ，称为 R {displaystyle R} 的图，是笛卡儿积 X × Y {displaystyle Xtimes Y} 的子集。若 ( x , y ) ∈ G ( R ) {displaystyle (x,y)in G(R)} 则称 x {displaystyle x} 与 y {displaystyle y} 有关系 R {displaystyle R} ，并记作 x R y {displaystyle xRy} 或 R ( x , y ) {displaystyle R(x,y)} 。但经常地我们把关系与其图等价起来，即若 R ⊆ X × Y {displaystyle Rsubseteq Xtimes Y} 则 R {displaystyle R} 是一个关系。例子：有四件物件{球，糖，车，枪}及四个人{甲，乙，丙，丁}。若甲拥有球， 乙拥有糖，及丁拥有车－即无人有枪及丙一无所有－则二元关系为“……拥有……”便是其中 R {displaystyle R} 的首项是物件的集合，次项是人的集合，而末项是由有序对（物件，主人） 组成的集合。比如有序对（球，甲）以球 R {displaystyle R} 甲表示， 代表球为甲拥有。不同的关系可以有相同的图。以下的关系中人人皆是物主，所以与 R {displaystyle R} 不同，但两者有相同的图。话虽如此，我们很多时候索性把 R {displaystyle R} 定义为 G ( R ) {displaystyle G(R)} 而“有序对 ( x , y ) ∈ G ( R ) {displaystyle (x,y)in G(R)} ”亦即是“ ( x , y ) ∈ R {displaystyle (x,y)in R} ”。二元关系可看作成二元函数，这种二元函数把输入元 x ∈ X {displaystyle xin X} 及 y ∈ Y {displaystyle yin Y} 视为独立变数并求真伪值（包括“有序对 ( x , y ) {displaystyle (x,y)} 是或非二元关系中的一元”此一问题）。若 X = Y {displaystyle X=Y} ，则称 R {displaystyle R} 为 X {displaystyle X} 上的关系。设 A {displaystyle A} 是一个集合，则设 X = { x 1 , x 2 , … , x n } {displaystyle X={x_{1},x_{2},ldots ,x_{n}}} 及 Y = { y 1 , y 2 , … , y m } {displaystyle Y={y_{1},y_{2},ldots ,y_{m}}} ， R {displaystyle R} 是 X {displaystyle X} Y {displaystyle Y} 上的关系，令则0,1矩阵称为 R {displaystyle R} 的关系矩阵，记作 M R {displaystyle M_{R}} 。设 A = { x 1 , x 2 , … , x n } {displaystyle A={x_{1},x_{2},ldots ,x_{n}}} ， R {displaystyle R} 是 A {displaystyle A} 上的关系，令图 G = ( V , E ) {displaystyle G=(V,E)} ，其中顶点集合 V = A {displaystyle V=A} ，边集合为 E {displaystyle E} ，且对于任意的 x i , x j ∈ V {displaystyle x_{i},x_{j}in V} ，满足 ( x i , x j ) ∈ E {displaystyle (x_{i},x_{j})in E} 当且仅当 ( x i , x j ) ∈ R {displaystyle (x_{i},x_{j})in R} 。则称图 G {displaystyle G} 是关系 R {displaystyle R} 的关系图，记作 G R {displaystyle G_{R}} 。关系的基本运算有以下几种：关系的性质主要有以下五种：设 R {displaystyle R} 为集合 A {displaystyle A} 上的关系，下面给出 R {displaystyle R} 的五种性质成立的充要条件：设 R {displaystyle R} 是非空集合 A {displaystyle A} 上的关系， R {displaystyle R} 的自反（对称或传递）闭包是 A {displaystyle A} 上的关系 R ′ {displaystyle R'} ，满足一般将 R {displaystyle R} 的自反闭包记作 r ( R ) {displaystyle r(R)} ，对称闭包记作 s ( R ) {displaystyle s(R)} ，传递闭包记作 t ( R ) {displaystyle t(R)} 。下列三个定理给出了构造闭包的方法：对于有限集合 A {displaystyle A} 上的关系 R {displaystyle R} ，存在一个正整数 r {displaystyle r} ，使得求传递闭包是图论中一个非常重要的问题，例如给定了一个城市的交通地图，可利用求传递闭包的方法获知任意两个地点之间是否有路相连通。可以直接利用关系矩阵相乘来求传递闭包，但那样做复杂度比较高；好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度；但最好的方法是利用基于动态规划的Floyd-Warshall算法来求传递闭包。