关系图

數學上，**二元關係**（英語：Binary relation，或簡稱**關係**）用於討論兩種物件的連繫。諸如算術中的「大於」及「等於」、幾何學中的「相似」或集合論中的「為…… 之元素」、「為…… 之子集」。

## 定義

實際上是以列舉二元有序對的方式去定義二元關係 $R$ ，也就是一個集合滿足

* 對所有的 $r\in R$ 存在 $x$ 且存在 $y$ 使 $r=(x,\,y)$

或是以正式的邏輯符號表述為

　
: $(\forall r\in R)(\exists x)(\exists y)[\,r=(x,\,y)\,]$

例一：有四件物件 {_球_，_糖_，_車_，_槍_} 及四個人 {_甲_，_乙_，_丙，丁_} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有車，則「擁有」的二元關係可以寫為

　
: $R$ = {(_球_，_甲_), (_糖_，_乙_), (_車_，_丁_)}

其中二元有序對的第一項是被擁有的物件，第二項是擁有者。

例二：實數系 $\mathbb {R} $ 上的「大於關係」可定義為

　
: $>\,:=\{\,(a,\,b)\in {\mathbb {R} }^{2}\,|\,(\exists r\in \mathbb {R} )[\,(a=b+r)\wedge (r\neq 0)\,]\}$

由於習慣上 $(a,\,b)\in \,>$ 通常都是寫為 $a>b$ ，更一般來說，不引起混淆的話會把 $(x,\,y)\in R$ 簡寫成 $xRy$ 。

## 集合的關係

集合 $X$ 與集合 $Y$ 上的二元關係則定義為 $R=(X,Y,G(R))$ ，當中 $G(R)\subseteq X\times Y$ (請參見笛卡兒積) ，稱為 $R$ 的**圖**。若 $(x,y)\in G(R)$ 則稱 $x$ 與 $y$ 有關係 $R$ ，並記作 $xRy$ 或 $R(x,y)$ 。

但經常地我們把關係與其圖等價起來，即若 $R\subseteq X\times Y$ 則 $R$ 是一個關係。

話雖如此，我們很多時候索性把集合間的關係 $R$ 定義為 $G(R)$ 而 「有序對 $(x,y)\in G(R)$ 」 即是 「 $(x,y)\in R$ 」。

## 特殊的二元關係

設 $A$ 是一個集合，則

1. 空集 $\varnothing $ 稱作 $A$ 上的**空關係**
2. $E_{A}=A\times A$ 稱作 $A$ 上的**全域關係**（**完全關係**）
3. $I_{A}=\{(x,x)|x\in A\}$ 稱作 $A$ 上的**恆等關係**

## 關係矩陣

設 $X=\{x_{1},x_{2},\ldots ,x_{n}\}$ 及 $Y=\{y_{1},y_{2},\ldots ,y_{m}\}$ ， $R$ 是 $X$ 和 $Y$ 上的關係，令

　
: $r_{ij}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\notin R\end{cases}}$

則 0,1 矩陣

　
: $(r_{ij})={\begin{bmatrix}r_{11}&r_{12}&\cdots &r_{1m}\\r_{21}&r_{22}&\cdots &r_{2m}\\\vdots &\vdots &\vdots &\vdots \\r_{n1}&r_{n2}&\cdots &r_{nm}\end{bmatrix}}$

稱為 $R$ 的**關係矩陣**，記作 $M_{R}$ 。

## 關係圖

設 $A=\{x_{1},x_{2},\ldots ,x_{n}\}$ ， $R$ 是 $A$ 上的關係，令圖 $G=(V,E)$ ，其中頂點集合 $V=A$ ，邊集合為 $E$ ，且對於任意的 $x_{i},x_{j}\in V$ ，滿足 $(x_{i},x_{j})\in E$ 若且唯若 $(x_{i},x_{j})\in R$ 。則稱圖 $G$ 是關係 $R$ 的**關係圖**，記作 $G_{R}$ 。

## 運算

關係的基本運算有以下幾種：

* 設 $R$ 為二元關係， $R$ 中所有有序對的第一元素構成的集合稱為 $R$ 的**定義域**，記作 ${\mbox{dom}}(R)$ 。形式化表示為

　
: ${\mbox{dom}}(R)=\{\,x\,|\,(\exists y)[\,(x,y)\in R\,]\,\}$

* 設 $R$ 為二元關係， $R$ 中所有有序對的第二元素構成的集合稱為 $R$ 的**值域**，記作 ${\mbox{ran}}(R)$ 。形式化表示為

　
: ${\mbox{ran}}(R)=\{\,y\,|\,(\exists x)[\,(x,y)\in R\,]\,\}$

* 設 $R$ 為二元關係， $R$ 的定義域和值域的併集稱作 $R$ 的**域**，記作 ${\mbox{fld}}(R)$ ，形式化表示為

　
: ${\mbox{fld}}(R)={\mbox{dom}}(R)\cup {\mbox{ran}}(R)$

* 設 $R$ 為二元關係， $R$ 的**逆關係**，簡稱 $R$ 的**逆**，記作 $R^{-1}$ ，其中

　
: $R^{-1}=\{\,p\,|\,(\exists x)(\exists y)[\,(x,y)\in R\wedge p=(y,x)\,]\,\}$

* 設 $F,G$ 為二元關係， $G$ 與 $F$ 的**合成關係**記作 $F\circ G$ ，其中

　
: $F\circ G=\{(x,y)|\exists t,~(x,t)\in F\wedge (t,y)\in G\}$

* 設 $R$ 為二元關係， $A$ 是一個集合。 $R$ 在 $A$ 上的**限制**記作 $R\upharpoonright A$ ，其中

　
: $R\upharpoonright A=\{(x,y)|(x,y)\in R\wedge x\in A\}$

* 設 $R$ 為二元關係， $A$ 是一個集合。 $A$ 在 $R$ 下的**像**記作 $R[A]$ ，其中

　
: $R[A]={\mbox{ran}}(R\upharpoonright A)$

* 設 $R$ 為 $A$ 上的二元關係，在右複合的基礎上可以定義關係的**冪運算**：

　
: $R^{0}=I_{A}\ $ 
 $R^{n+1}=R^{n}\circ R\ $

## 性質

關係的性質主要有以下五種：

* 自反性： $\forall x\in A,~(x,x)\in R$

　
: 在集合 X 上的關係 R，如對任意 $x\in X$ ，有 $(x,x)\in R$ ，則稱 R 是自反的。

* 非自反性（自反性的否定的強型式）： $\forall x\in A,~~(x,x)\notin R$

　
: 在集合 X 上的關係 R，如對任意 $x\in X$ ，有 $(x,x)\notin R$ ，則稱 R 是非自反的。

* 對稱性： $\forall x,y\in A,~(x,y)\in R\implies (y,x)\in R$

　
: 在集合 X 上的關係 R，如果有 $(x,y)\in R$ 且 $x\neq y$ 必有 $(y,x)\in R$ ，則稱 R 是對稱的。

* 反對稱性（不是對稱性的否定）： $\forall x,y\in A,~((x,y)\in R\wedge (y,x)\in R)\implies x=y$
* 非對稱性（對稱性的否定的強型式）： $\forall x,y\in A,~(x,y)\in R\implies (y,x)\notin R$

　
: 非對稱性是 滿足非自反性的反對稱性。

* 傳遞性： $\forall x,y,z\in A,~((x,y)\in R\wedge (y,z)\in R)\implies (x,z)\in R$

設 $R$ 為集合 $A$ 上的關係，下面給出 $R$ 的五種性質成立的充要條件：

 1. $R$ 在 $A$ 上自反，若且唯若 $I_{A}\subseteq R$
2. $R$ 在 $A$ 上非自反，若且唯若 $R\cap I_{A}=\emptyset $
3. $R$ 在 $A$ 上對稱，若且唯若 $R=R^{-1}\ $
4. $R$ 在 $A$ 上反對稱，若且唯若 $R\cap R^{-1}\subseteq I_{A}$
5. $R$ 在 $A$ 上非對稱，若且唯若 $R\cap R^{-1}=\emptyset $
6. $R$ 在 $A$ 上傳遞，若且唯若 $R\circ R\subseteq R$

## 閉包

設 $R$ 是非空集合 $A$ 上的關係， $R$ 的自反（對稱或傳遞）**閉包**是 $A$ 上的關係 $R'$ ，滿足

 1. $R'$ 是自反的（對稱的或傳遞的）
2. $R\subseteq R'$
3. 對 $A$ 上任何包含 $R$ 的自反（對稱或傳遞）關係 $R''$ 有 $R'\subseteq R''$

一般將 $R$ 的自反閉包記作 $r(R)$ ，對稱閉包記作 $s(R)$ ，傳遞閉包記作 $t(R)$ 。

下列三個定理給出了構造閉包的方法：

 1. $r(R)=R\cup R^{0}$
2. $s(R)=R\cup R^{-1}$
3. $t(R)=R\cup R^{2}\cup R^{3}\cup \cdots $

對於有限集合 $A$ 上的關係 $R$ ，存在一個正整數 $r$ ，使得

　
: $t(R)=R\cup R^{2}\cup \cdots \cup R^{r}$

求傳遞閉包是圖論中一個非常重要的問題，例如給定了一個城市的交通地圖，可利用求傳遞閉包的方法獲知任意兩個地點之間是否有路相連通。可以直接利用關係矩陣相乘來求傳遞閉包，但那樣做複雜度比較高；好一點的辦法是在計算矩陣相乘的時候用分治法降低時間複雜度；但最好的方法是利用基於動態規劃的 Floyd-Warshall 算法來求傳遞閉包。

## 參見

* 有序對
* 二元集合
* 笛卡兒積
* 偏序關係
* 等價關係
* 相容關係