8. Relations

8.1. Relations and Their Properties

Set $A,B$에 대해 Binary relation from $A$ to $B$는 $A\times B$의 Subset이다.

Binary relation from $A$ to $B$의 첫 번재 Element가 $A$에서 오고 두 번재 Element가 $B$에서 온 각 Ordered pair의 Set $R$이라고 할 때 $(a, b)\in R$을 나타내기 위해 $a\ R\ b$라는 Notation을 사용하고 $(a,b)\notin R$을 Notation으로 $a \not R\ b$로 나타낸다.
$(a,b)$가 $R$에 속할 때 $a$는 related to $b$ by $R$($a$는 $R$에 의해 $b$와 관계)라고 한다.

팁

Example

$A=\{0,1,2\}, B=\{a,b\}$라고 할 때 relation from $A$ to $B$

• Solution
  $\{(0,a),(0,b),(1,a),(1,b),(2,a),(2,b)\}$

Functions as Relations

Functrion $f$가 Set $A$에서 $B$로 정의된 경우 $f$는 $A$의 각 Element에 대해 $B$에 정확히 하나의 Element를 할당한다.
$f$의 Graph는 $A\times B$의 Subset이므로 $A$에서 $B$로의 Relation이다.
Function의 Graph는 $A$의 모든 Element가 Graph의 정확히 하나의 Ordered pair의 첫 Element라는 특성을 가지고 있다.

$R$이 $A$에서 $B$로의 관계이고 $A$의 모든 Element가 $R$의 정확히 하나의 Ordered pair의 첫 Element라면 $R$을 Graph로 하는 Function이 정의될 수 있다.
$A$의 Element $a$에 대해 $(a,b)\in R$인 유일한 Element $b\in B$를 할당함으로 가능해진다.

Relation은 Set $A,B$의 Element 간 One-to-many relationship을 표현하는 데 사용될 수 있다.
이 경우 $A$의 Element는 $B$의 여러 Element와 Relation이 있을 수 있다.
Funtion의 경우 $A$의 각 Element와 관련된 $B$의 정확히 하나의 Element를 나타내는 Relation이다.

Relations on a Set

Set $A$에서 $A$로의 Relation은 Relation on the set $A$라고 하며 $A\times A$의 Subset이다.

팁

Example

Set $A=\{1,2,3,4\}$라고 할 때 Relation $R=\{(a,b)\mid a\ divides\ b\}$의 Ordered pair

• Solution
  $R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}$

팁

Example

$n$개의 Element를 가진 Set에서 Relation 개수

• Solution
  Set $A$에서의 Relation은 $A\times A$의 Subset이다.
  $A\times A$는 $n^2$개의 Element를 가지기에 $2^{n^2}$만큼의 Relation이 존재한다.

Properties of Relations

Set $A$에서의 Relation $R$은 모든 Element $a\in A$에 대해 $(a,a)\in R$일 경우 Reflexive(반사적)이라고 한다.

경고

Remark

Quantifier를 사용할 경우 Relation $R$이 Set $A$에서 Reflexive하다는 것은 $\forall a\in A, (a,a)\in R$을 의미한다.

Set $A$에 대한 Relation $R$은 $A$의 모든 $a, b$에 대해 $(a,b)\in R$일 때 $(b,a)\in R$이면 Symmetric(대칭적)이라 하고 $a,b \in A$에 대해 $(a, b)\in R, (b,a)\in R$을 만족하는 Condition이 $a=b$일 경우 Antisymmetric(비대칭적)이라고 한다.

경고

Remark

Quantifier를 사용할 경우 Set $A$의 Relation $R$은 $\forall a\forall b((a,b)\in R\to (b,a)\in R)$인 경우 Symmetric, $\forall a \forall b(((a,b)\in R\land(b,a)\in R)\to (a=b))$인 경우 Antisymmetric이라 한다.

Set $A$의 Transitive(전이) relation은 Relation $R$의 모든 $a, b,c \in A$에 대해 $(a,b)\in R$이고 $(b,c)\in R$이면 $(a, c)\in R$이 성립함을 의미한다.

경고

Remark

Quantifier를 사용하여 Set $A$의 Relation $R$이 Transitive인 경우를 $\forall a\forall b\forall c((a,b)\in R\land (b,c)\in R)\to(a,c)\in R$로 표현 가능하다.

팁

Example

모든 $a$가 Positive integer set $A$에 속할 때 $(a,a)$는 Positive integer의 Divide relation에서 Reflexive인 지, Symmetric인 지, Transitive인 지

• Solution
  Reflexive: $a$가 Positive integer일 때 항상 $a$는 $a$를 나누므로 Divide relation은 Reflexive하다.
  만약 Set을 Nonnegative integer set으로 바꿀 경우 0은 0을 나눌 수 없으므로 Divide relation이 Reflexive하지 못한다.
  Symmetric: Symmetirc이지 않다.
  이유로는 $1|2$이나 $2\not |1$이기 때문이다.
  추가적으로 이 Relation은 Antisymmetric인 이유로는 $a, b$가 Positive integer일 때 $a|b$이고 $b|a$이면 $a=b$이기 때문이다.
  Transitive: Positive integer $a,b,c$에 대해 $a|b \land b|c \to a|c$이기에 이 Relation은 Transitive이다.

Combining Relation

Set $A, B$에 대한 Relation은 $A\times B$의 Subset이다.

$R$을 Set $A$에서 $B$로의 Relation, $S$를 Set $B$에서 $C$로의 Relation이라고 할 때 $R, S$의 Composite는 $a\in A, c\in C$를 만족하는 Ordered pair $(a,c)$로 이루어진 Releation이며 $(a,b)\in R \land (b, c)\in S$이다.
Notation으로 $S\circ R$로 표현한다.

Set $A$의 Relation $R$의 Power $R^n, n=1,2,\dots$를 $R^1=R, R^{n+1}=R^n\circ R$로 Recursive하게 정의된다.

팁

Example

Relation $R$을 모든 사람에 대한 Set의 Relation이라고 할 때 $(a, b)\in R$은 $a$가 $b$의 부모일 때 성립할 때 $(a,c)\in R\circ R$

• Solution
  Relation $R$이 부모 Relation을 나타내기에 $R\circ R$은 부모의 부모, 즉 조부모 Relation을 나타낸다.

팁

Example

Relation $R=\{(1,1),(2,1),(3,2),(4,3)\}$이라고 할 때 $R^n$

• Solution
  $R^2=\{(1,1),(2,1),(3,1),(4,2)\}$이고 $R^3=\{(1,1),(2,1),(3,1),(4,1)\}$을 알 수 있다.
  이후 몇 번을 거듭제곱하여도 모든 Ordered pair의 뒤 Element가 1이 되는 것을 알 수 있으므로 $n\geq 3\to R^n=R^3$가 참임을 알 수 있다.

정보

Theorem

Set $A$의 Relation $R$은 $n=1,2,\dots$일 때 $R^n\subseteq R$일 경우 Transitive이다.

8.2. n-ary Relations and Their Application

n-ary Relations

Set $A_1, A_2,\cdots,A_n$에 대한 $n$-ary Relation은 $A_1\times A_2\times \cdots \times A_n$의 Subset이다.
Set $A_1, A_2,\cdots,A_n$을 Domain, $n$을 Relation의 Degree라고 한다.

팁

Example

$R$을 Airplane flight를 나타내는 5-Tuple($A,N,S,D,T$)라고 할 때 이 Relation의 예시로 (항공사, 비행기 번호, 출발지, 도착지, 출발 시간)의 꼴로 (Nadir, 963, Mewark, Bangor, 15:00)로 나타낼 수 있다.
이 Relation의 Degree는 5이며 Relation의 Domain은 모든 항공사 Set, 비행기 Set, 출발 도시 Set, 도착 도시 Set, 시간 Set이 된다.

Databases and Relations

DB는 Field로 구성된 $n$-tuple인 Record로 이루어져 있다(Field = 각 Tuple의 Item).
DB의 Relation을 Table이라고 부른다(표현이 Table로 되기 때문).
$n$-tuple의 Relation의 Domain은 $n$-tuple의 Value가 이 Domain에서 $n$-tuple을 결정할 때 Primary key라고 한다.
Primary key는 Unique, Not null이다.

Relation에서 현재 $n$-tuple의 Set을 Relation의 Extension이라고 한다.
DB의 Name, Attribute들을 포함하는 Permanent part를 Intension이라고 한다.

Domain의 Combination은 $n$-ary Relation에서 $n$-tuple을 Uniquyely Identifiy 가능하다.
특정 Domain set의 Value가 Relation 내의 $n$-tuple을 결정할 때 Domain의 Cartesian product를 Composite key라고 한다.

Operations on n-ary Relations

$n$-ary relation $R$의 Element가 만족할 수 있는 Condition을 $C$라 할 때 Selection operator $s_C$은 $n$-ary relation $R$을 Condition $C$를 만족하는 $R$의 모든 $n$-tuple의 $n$-ary relation을 Mapping한다.

Projection(투영 연산) $i_1<i_2<\cdots<i_m$을 만족하는 $P_{{i_1}{i_2}\dots{i_m}}$은 $m\leq n$일 때, $n$-tuple($a_1, a_2,\dots,a_n$)을 $m$-tuple($a_{i_1},a_{i_2},\dots,a_{i_m}$)로 Mapping한다.

$R$이 Degree $m$인 Relation이고 $S$가 Degree $n$인 Relation일 때 $p\leq m, p\leq n$인 Join $J_p(R,S)$는 Degree가 $m+n-p$인 Relation이며 $(m+n-p)$-tuple($a_1,a_2,\dots,a_{m-p},c_1,c_2,\dots,c_p,b_1,b_2,\dots,b_{n-p}$)로 구성되며 $a_1,\dots,a_{m-p},c_1,\dots,b_{n-p}$는 $m$-tuple이며 $R$에 속하고 $c_1,\dots,c_p,b_1,\dots,b_{n-p}$은 $n$-tuple이며 $S$에 속한다.

SQL

SQL(Structured Query Language)는 DB의 Queryu language이다.

Airline	Flight_number	Gate	Destination	Departure_time
Nadir	122	34	Detroit	08:10
Acme	221	22	Denver	08:17
Acme	122	33	Anchorage	08:22
Acme	323	34	Honolulu	08:30
Nadir	199	13	Detroit	08:47
Acme	222	22	Denver	09:10
Nadir	322	34	Detroit	09:44

팁

Example

SELECT Departure_time FROM Flights WHERE Destination='Detroit';

• Solution
  위 Table Flights DB에서 Condition Destination='Detroit'를 만족하는 5-tuple의 Selection으로부터 Departure_time Attribute의 Projection $P_5$를 찾는 데 사용된다.

8.3. Representing Relations

Representing Relations Using Matrices

Finite set 간의 Relation은 Zero-one Matrix를 사용하여 표현 가능하다.
$R$이 Set $A=\{a_1,a_2,\dots,a_m\}$에서 $B=\{b_1,b_2,\dots,b_n\}$으로의 Relation이라 가정할 때 $A=B$와 같을 때 Relation $R$은 $M_R=[m_{ij}]$($m_{ij}=1\ if(a_i,b_j)\in R, m_{ij}=0\ if(a_i,b_j)\notin R$)로 나타낼 수 있다.

팁

Example

Set $A=\{1,2,3\}, B=\{1,2\}$의 $A$에서 $B$로의 Relation $R$에 대해 $a\in A, b \in B, a>b$일 때 Ordered pair $(a,b)$일 때 Matrix

• Solution
  $R=\{(2,1),(3,1),(3,2)\}$이기에 $R$에 해당하는 Matrix는
  $M_R=\begin{bmatrix}0 & 0 \\ 1 & 0 \\ 1 & 1 \end{bmatrix}$가 된다.

$R$이 Set $A$에서 $B$로의 Relation이고 $S$가 Set $B$에서 $C$로의 Relation일 때 Set $A,B,C$는 각각 $m,n,p$개의 Element를 가진다고 할 때 $S \circ R, R, S$에 대한 Zero-one matrix는 각각 $M_{S\circ R}=[t_{ij}], M_R=[r_{ij}], M_S=[s_{ij}]$로 표기할 때 Matrix의 크기는 각각 $m\times p, m\times n, n\times p$이다.
Ordered pair $(a_i,c_j)$는 $S\circ R$에 속하기 위해 어떤 Element $b_k$가 존재해야 하며 $(a_i,b_k)$는 $R$에, $(b_k, c_j)$는 $S$에 속해야 한다.
싸라서 $t_{ij}=1\ if\ and\ only\ if\ r_{ik}=s_{kj}=1$을 만족하는 $k$에 대해 성립할 경우에만 성립한다.
즉 $M_{S\circ R}=M_R\odot M_S$이다.

팁

Example

$M_R=\begin{bmatrix} 1&0&1\\1&1&0\\0&0&0\end{bmatrix}$이고 $M_S=\begin{bmatrix}0&1&0\\0&0&1\\1&0&1\end{bmatrix}$일 때 $S\circ R$의 Matrix

• Solution
  $M_{S\circ R}=M_R\odot M_S=\begin{bmatrix}1&1&1\\0&1&1\\0&0&0\end{bmatrix}$이다.

팁

Example

$M_R=\begin{bmatrix}0&1&0\\0&1&1\\1&0&0\end{bmatrix}$일 때 $R^2$의 Matrix

• Solution
  $M_{R^2}=M_R^{[2]}=\begin{bmatrix}0&1&1\\1&1&1\\0&1&0\end{bmatrix}$이다.

Representing Relations Using Digraphs

Directed graph(=Digraph)는 Vertex(Node)들로 이루어진 Set $V$와 $V$의 Element pair로 구성된 Set $E$로 이루어져 있으며 이를 Edge(Arc)라고 부른다.
형태가 $(a,a)$인 Edge는 다시 자기 자신으로 향하는 Arc로 표현되며 Loop라고도 한다.

팁

Example

Vertex $a,b,c,d$가 존재하고 Edge $(a,b), (a,d),(b,b),(b,d),(c,a),(c,b),(d,b)$가 존재하는 Digraph는 위 Example's Directed graph 1과 같이 존재한다.

팁

Example

주어진 Example's Directed graph 2의 Relation이 Reflexive, Symmetric, Antisymmetric, Transitive인 지

• Solution
  Reflexive: $R$은 매 Vertex에 Loop edge가 존재하여 Reflexive하나 $S$는 그렇지 못하다.
  Symmetric / Antisymmetric: 양 방향을 잇는 Edge가 둘 다 존재하지 않으므로 $R, S$는 Symmetric하지도 Antisymmetric하지도 않다.
  Transitive: $(a,c)$가 존재하지 않아 $R$은 Transitive하지 않고 $(c,b)$가 속하지 않아 $S$ 역시 Transitive하지 않다.

8.4. Closures of Relations

Set $A=\{1,2,3\}$의 Relation $R=\{(1,1),(1,2),(2,1),(3,2)\}$는 Not reflexive이다.
$R$을 포함하며 최소한의 Reflexive relation을 생성하기 위해 $R$에 $(2,2),(3,3)$을 추가해야 한다.
앞 $R$을 포함하며 Reflexive이며 $R$을 포함하는 모든 Reflexive relation 내에 위치하는 것을 Reflexive closure of $R$($R$의 반사적 닫힘)이라 한다.
즉 $\Delta=\{(a,a)\mid a\in A\}$를 만족할 때 $R\cup \Delta$이며 이 Relation은 Diagonal relation이다.

Set $A=\{1,2,3\}$의 Relation $R=\{(1,1),(1,2),(2,2),(2,3),(3,1),(3,2)\}$는 Not Symmetric이다.
$R$을 포함하며 최소한의 Symmetric relation을 생성하기 위해 $R$에 $(2,1),(1,3)$을 추가해야 한다.
앞 $R$을 포함하며 Symmetric이며 $R$을 포함하는 모든 Symmetric relation은 새로 생성된 Relation을 포함해야 한다(모든 Symmetric Relation은 $(2,1),(1,3)$을 포함해야 한다.).
이 새로운 Relation을 Symmetric closure of $R$($R$의 대칭적 닫힘)이라고 한다.

팁

Example

$a,b$가 Positive Integer일 때 Relation $R=\{(a,b)\mid a<b\}$의 Reflexive closure

• Solution
  $R$의 Reflexive closure는 $R\cup \Delta=\{(a,b)\mid a<b\}\cap\{(a,a)\mid a\in Z\}=\{(a,b)\mid a\leq b\}$이다.

팁

Example

$a,b$가 Positive integer일 때 Relation $R=\{(a,b)\mid a>b\}$의 Symmetric closure

• Solution
  R의 Symmetric closure는$R\cap R^{-1}=\{(a,b)\mid a>b\}\cap \{(b,a)\mid a>b\}=\{(a,b)\mid a\not =b\}$이다.

Paths in Directed Graphs

Directed graph $G$에서 $a$에서 $b$로 가는 Path는 $G$에서 Edge의 Sequence $(x_0,x_1),(x_1,x_2),(x_2,x_3),\dots,(x_{n-1},x_n)$이다($x_0=a,x_n=b,n\geq 0$).
Path 중 Edge의 끝 Vertex가 다음 Edge의 시작 Vertex와 같으며 길이가 0인 경우 Empty set이며, 길이가 $n$인 경우 $n-1$ 길이의 Circuite나 Cycle이라고 부른다.

정보

Theorem

Set $A$ 위 Relation $R$에 대해 $n$이 Positive integer일 경우 $a$에서 $b$로 가는 길이 $n$인 Path가 존재하는 것은 $(a,b)\in R^n$과 필요 충분 조건이다.

• Proof
  Mathematical induction을 사용하여 $a$에서 $b$로의 Path는 $(a,b)\in R$과 필요 충분 조건이다.
  $a$에서 $b$로 가는 길이가 $n+1$인 Path가 존재하는 것은 $a$에서 $c$로 가는 $1$이 길이인 Path가 존재하고 $c$에서 $b$로의 가는 길이가 $n$인 Path가 존재할 때 필요 충분 조건이다.
  이로써 증명할 수 있다.

Transitive Closures

Set $A$에 대한 Relation $R$에 대해 $R^\star$이 $a$에서 $b$로 가는 길이가 1 이상인 Path가 존재하는 Pair $(a,b)$로 구성되는 Connectivity relation이라고 할 때 $R^\star=\sum_{n=1}^\infin R^n$이다.

정보

Theorem

Relation $R$의 Transitive closure는 Connectivity Relation $R^\star$

• Proof
  $R^\star$이 Transitive인 지 qhdlrl dnlgo $(a,b)\in R^\star, (b,c)\in R^\star$라면 $R^\star$에서 $a$에서 $b,\ b$에서 $c$로 가는 Path가 존재한다.
  즉 $(a,c)\in R^\star$이다.
  $S$가 $R$을 포함하는 Transitive relation이라고 할 때 $S^n$ 역시 Transitive이며 $S^n\subseteq S$이다($\because S^\star =\sum_{k=1}^\infin S^k$).
  $S^k\subseteq S$이기에 $S^\star \subseteq S$이며 $R\subseteq S$이기에 $R^\star \subseteq S^\star$이다.
  요약하여 $R^\star \subseteq S^\star \subseteq S$가 되므로 $R$을 포함하는 모든 Transitive closure는 $R^\star$를 포함하여야 하며 $R$의 Transitive closure이다.

정보

Theorem

$R$에 대한 Zero-one matrix $M_R$일 때 Transitive closure $R^\star$의 Zero-one matrix는 $M_{R^\star}=M_R \lor M_R^{[2]}\lor M_R^{[3]}\lor \cdots \lor M_R^{[n]}$

팁

Example

Relation $R$의 Zero-one matrix가 $M_R=\begin{bmatrix}1&0&1\\0&1&0\\1&1&0\end{bmatrix}$일 때 Transitive closure의 Zero-one matrix

• Solution
  $R^\star$의 Zero-one matrix는 $M_{R^\star}=M_R \lor M_R^{[2]}\lor M_R^{[3]}$이기에 $M_R^{[2]}=\begin{bmatrix}1&1&1\\0&1&0\\1&1&1\end{bmatrix}, M_R^{[3]}=\begin{bmatrix}1&1&1\\0&1&0\\1&1&1\end{bmatrix}$임을 이용하여
  $M_{R^\star}=\begin{bmatrix}1&0&1\\0&1&0\\1&1&0\end{bmatrix}\lor \begin{bmatrix}1&1&1\\0&1&0\\1&1&1\end{bmatrix}\lor \begin{bmatrix}1&1&1\\0&1&0\\1&1&1\end{bmatrix}=\begin{bmatrix}1&1&1\\0&1&0\\1&1&1\end{bmatrix}$이다.

정보

Pseudocode

Algorithm : A Procedure for Computing the Transitive Closure

procedure transitive closure($M_R$: zero-one $n\times n$ matrix)
$A$ := $M_R$
$B$ := $A$
for $i$ := 2 to $n$
begin
$A$ := $A\odot M_R$
$B$ := $B\lor A$
end {$B$ is the zero-one matrix for $R^\star$}

현재 위 Algorithm의 각 거듭제곱을 계산하기 위해 $n-1$의 $n\times n$의 Zero-one matrix의 Boolean product를 찾아야하기에 총 $n^2(2^n-1)(n-1)+n^2(n-1)$만큼의 Bit operator를 사용하여야 하며 Big-O notation으로 $O(n^4)$가 된다.

Warshall's Algorithm

1960년에 Stephen Warshall에 의해 설명된 Warshall's algorithm은 Relation의 Transitive closure를 계산하는 효율적인 Algorithm이다.

$R$을 $n$개의 Element를 가진 Set의 Relation으로 가정할 때 $v_1, v_2, \dots, v_n$이 $n$개의 Element의 임의의 나열일 때 Path의 Interior vertex의 Concept를 사용하여 $a, x_1, x_2, \dots, x_{m-1}, b$가 Path일 때 Interior vertex는 $x_1,\dots,x_{m-1}$로 Path에서 첫 번째와 마지막 Vertex를 제외한 모든 Vertex들이다.
Zero-one matrix의 Sequence를 구성하는 데 기반을 두며 $W_0, W_1,\dots, W_n$들이 이 Matrix라고 할 때 $W_0=M_R$이고 $W_k=[w_{ij}^{(k)}]$($w_{ij}^{(k)}=1$ if $v_i$에서 $v_j$로 가는 Path가 존재하며 모든 Interior vertex들이 $\{v_1,\cdots,c_k\}$안에 존재할 때, 그렇지 않다면 $w_{ij}^{(k)}=0$)이다.
$W_n=M_{R^\star}$임을 유의하여 $M_{R^\star}$의 $(i,j)$번째 Element는 $v_i$에서 $v_j$로 가는 Path가 존재하고 모든 Interior vertex들이 $\{v_1,\dots,v_n\}$ Set 내에 있을 때 1, 그렇지 않다면 0이다.

팁

Example

Relation $R$을 $(a,d),(b,a),(b,c),(c,a),(c,d),(d,c)$라고 할 때 Matrix $W_0,W_1,W_2,W_3,W_4$

• Solution
  $v_1=a, v_2=b, v_3=c, v_4=d$라고 할 때 $W_0=\begin{bmatrix}0&0&0&1\\1&0&1&0\\1&0&0&1\\0&0&1&0\end{bmatrix}$이다.
  $W_1$의 $(i,j)$번째 Element는 $v_i$에서 $v_j$까지의 Path가 $v_1=a$를 가질 때에만 Interior vertex이며 즉 1이다.
  모든 길이가 1인 Path는 Interior vertex가 없으므로 여전히 사용 가능하다.
  $b$에서 $d$의 Path인 $b, a, d$가 존재하므로 $W_1=\begin{bmatrix}0&0&0&1\\1&0&1&1\\1&0&0&1\\0&0&1&0\end{bmatrix}$이며 $b$가 단말 Vertex인 Edge가 존재하지 않기에 $b$를 Interior vertex로 허용할 때 새로운 Path가 생기지 않으므로 $W_1=W_2$이다.
  $W_3$의 $(i,j)$번째 Element는 $v_i$에서 $v_j$까지의 Path가 $v_1=a, v_2=b, v_3=c$를 Interior vertex로 가질 경우 1이므로 $W_3=\begin{bmatrix}0&0&0&1\\1&0&1&1\\1&0&0&1\\1&0&1&1\end{bmatrix}$이며 $W_4$의 경우 $v_i$에서 $v_j$까지의 Path가 $v_1=a,v_2=b,v_3=c,v_4=d$를 Interior vertex로 가질 경우 1이므로 $W_4=\begin{bmatrix}1&0&1&1\\1&0&1&1\\1&0&1&1\\1&0&1&1\end{bmatrix}$이다.

정보

Lemma

$W_k=[w_{ij}^{[k]}]$를 Zero-one matrix라고 할 때 $(i,j)$위치에 1이 들어가 있는 경우가 $\{v_1,\dots,v_k\}$ Set의 Interior vertex를 가진 $v_i$에서 $v_j$로 가는 Path가 존재할 때일 때 $w_{ij}^{[k]}=w_{ij}^{k-1}\lor (w_{ik}^{[k-1]}\land w_{kj}^{[k-1]})(단,\ i,j,k\leq n)$

정보

Pseudocode

Algorithm : Warshall Algorithm

procedure Warshall($M_R$: $n\times n$ zero-one matrix)
$W$ := $M_R$
for $k$ := 1 to $n$
begin
for $i$ := 1 to $n$
begin
for $j$ := 1 to $n$
$w_{ij}$ := $w_{ij}\lor (w_{ik}\land w_{kj})$
end
end {$W$ = $[w_{ij}]$ is $M_{R^\star}$}

8.5. Equivalence Relations

Equivalence Relations

Set $A$에서 Relation을 Equivalence relation(동치 관계)라고 하기 위해 Reflexive, Symmetric, Transitive해야 한다.
두 Element $a, b$가 Equivalence relation라고 할 때 equivalent(동치)라고 하며 Notation으로 $a \sim b$로 표현한다.

팁

Example

Positive integer $n$과 Character string $S$에 대해 $R_n$이 $S$의 Relation이며 $s R_n t$는 $s=t$이거나 $s$와 $t$가 모두 $n$자 이상이며 $s, t$의 첫 $n$자가 같을 때 성립
즉 $n$자 미만의 String은 자기 자신과만 Relation이 있으며 $n$자 이상의 경우 처음 $n$자가 동일할 때만 Relation 존재
$n=3$이라고 할 때 $S$가 모든 Bit string의 Set일 때 $sR_3t$는 $s=t$거나 3 이상인 Bit string이 동일한 3 Bit로 시작할 때 성립
이때 모든 $S$와 모든 $n$에 대해 $R_n$이 $S$의 Equivalence relation임을 증명

• Solution
  $R_n$은 Reflexive하다($s=s$).
  만약 $sR_nt$라면 $s=t$이거나 $s, t$는 $n$자 이상이며 같은 String으로 시작한다.
  따라서 $sR_nt$가 성립할 때 $tR_ns$ 역시 성립하며 $R_n$이 Symmetric하다.
  $sR_nt, tR_nu$라고 가정할 경우 $sR_nu$가 성립하므로 Transitive하므로 $R_n$은 $S$의Equivalence relation이다.

팁

Example

Positive integer set에서 "Divide" Relation이 Equivalence relation이 아님을 증명

• Solution
  이전 Example에서 "Divide" Relation은 Reflexive, Transitive이나 Symmetric하지 않으므로($2|4,4\not |2$) Equivalence relation이 아니다.

Equivalence Classes

Set $A$에 정의된 Equivalence relation $R$이 있을 때 $A$의 Element $a$와 관련된 모든 Element의 Set을 Equivalence class라고 한다.
$R$에 대한 $a$의 Equivalence class를 Notation으로 $[a]_R$로 표기하며 하나의 Relation만 고려할 경우 $[a]$로 표기 가능하다.
즉, $[a]_r=\{s\mid (a,s)\in R\}$이며 $b\in[a]_R$일 경우 $b$는 Equivalence class의 Representative라고 하며 어떤 Equivalence class의 Element는 Representative로 사용할 수 있으며 특별한 의미가 없다.

팁

Example

0, 1의 Equivalence class는 4로 나눈 나머지에 대해 어떻게 정의되는지

• Solution
  0의 Equivalence class는 $a\equiv 0(\mod 4)$인 모든 Integer들은 4로 나누어 떨어지는 모든 Integer $a$를 포함한다.
  따라서 이 Relation에 대한 0의 Equivalence class는 $[0]=\{\dots,-8,-4,0,4,8,\dots\}$이다.
  1의 Equivalence class는 $[1]=\{\dots, -7, -3, 1, 5, 9,\dots\}$이다.

팁

Example

Bit string set의

$R_3$ Relation에 따라 String 0111의 Equivalence class
($sR_3t$는 $s,t$가 Bit string이며 $s=t$이거나 $s, t$의 앞 3 Bit가 동일한 3Bit 이상 String)

• Solution
  $[0111]_{R_3}=[011]_{R_3}=\{011, 0110,0111,01100,01101,01110,01111,\dots\}$

Equivalence Classes and Partitions

정보

Theorem

Set $A$에 대한 Equivalence relation $R$에 대해 $A$의 Element $a,b$에 대해 다음의 Statement들은 Equivalent이다.

$(i)\ aRb$, $(ii)\ [a]=[b]$, $(iii)\ [a]\cap [b]\not= \empty$

• Proof
  (i) & (ii) $aRb$일 때 $[a]=[b]$임을 보이기 위해 $[a]\subseteq [b]$, $[b]\subseteq [a]$를 증명한다.
  $c$가 $[a]$에 속한다면 $aRc$가 성립하며 $aRb$이고 $R$이 Symmetric이므로 $bRa$가 성립함을 알 수 있다.
  $R$이 Transitive이고 $R$이 Transitive이기에 $bRa$와 $aRc$가 주어질 경우 $bRc$가 성립하므로 $[a]\subseteq [b]$이다.
  같은 방법으로 $[b]\subseteq [a]$도 증명 가능하다.
  (ii) & (iii)를 의미하기 위해 $[a]=[b]$일 때 $[a]\cap [b]\not = \empty$가 성립한다.
  $[a]\not= \empty$이며 $a$가 $[a]$에 속하기에 $R$은 Reflexive이다.
  (iii) & (i)를 위해 $[a]\cap [b]\not= \empty$라고 가정할 때 Element $c$는 $[a],[b]$에 모두 속한다.
  즉 $aRc, bRc$가 성립하고 Symmetric에 의해 $cRb$가 성립하고 Transitivity에 의해 $aRc, cRb$로 인해 $aRb$가 성립한다.

$R$이 Set $A$에 대한 Equivalence relation이라고 할 때 $R$의 Equivalence class의 Union은 $A$ 전체와 동일하다.
$\sum_{a\in A}[a]_R=A$
위 Theorem에 의해 Equivalence class는 서로 같거나 Disjoint일 때 $[a]_R \cap [b]_R=\empty$d lek.
두사실로 Equivalence class가 $A$를 분리한 Subset으로 나누기에 $A$의 Partition을 형성함을 확인할 수 있다.
즉 Subset $A_i$는 $S$의 Partition을 형성하기 위한 Condition은 $A_i\not =\ for\ i\in I, A_i\cap A_j=\empty\ when\ i\not=j$가 필요충분 조건이다.

정보

Theorem

$R$을 Set $S$의 Equivalence relation이라고 할 때 $R$의 Equivalence class들은 $S$의 Partition을 형성하고, Set $S$의 Partition $\{A_i \mid i\in I\}$가 주어지면 $A_i$를 Equivalence class로 가지는 Equivalence relation $R$이 존

정보

Example

Congruence modulo 4의 Set의 Partition

• Solution
  총 4개의 Congruence class들이 존재하며 $[0]_4, [1]_4,[2]_4,[3]_4$이다.
  $[0]_4=\{\dots,-8,-4,0,4,8,\dots\},$
  $[1]_4=\{\dots,-7,-3,1,5,9,\dots \},$
  $[2]_4=\{\dots,-6,-2,2,6,10,\dots \},$
  $[3]_4=\{\dots,-5,-1,3,7,11,\dots \}$이다.

8.6. Partial Orderings

Set $S$에 대한 Relation $R$은 Reflexive, Antisymmetric, Transitive일 때 Partial order라고 한다.
Partial order $R$과 함께하는 Set $S$를 Partially ordered set(Poset)이라고 하며 Notation으로 $(S, R)$로 표기하며 $S$의 Element는 Poset의 Element라고 불린다.

팁

Example

Integer set에서 $\geq$ Relation이 Partial order임을 증명

• Solution
  모든 Integer $a$에 대해 $a\geq a$이므로 Reflexive이며 $a\geq b \land b\geq a$일 때는 $a=b$일 때 뿐이므로 Antisymmetric이다.
  $a\geq b \land b\geq c$일 때 $a\geq c$이므로 Transitive이다.
  그러므로 $\geq$는 Integer set에대한 Partial order이다.

Poset($S, \preccurlyeq$)의 Element $a, b$는 $a\leq b$나 $b\leq a$인 경우 Comparable(비교 가능)하다고 하고, $S$의 Element $a, b$가 $a\leq b$나 $b\leq a$가 아닌 경우 Incomparable(비교 불가능)하다고 한다.

팁

Example

Poset($\mathbf{Z^+}, |$)에서 Integer 3, 9 / 5, 7이 Comparable인 지 여부

• Solution
  $3 | 9$이므로 Comparable, $5\not | 7, 7\not | 5$이므로 Incomparable이다.

Poset($S,\preccurlyeq$)이 모든 $S$의 Element가 Comparable이면 $S$는 Totally ordered(Linearly ordered) set이라고 하며 $\preccurlyeq$는 Total order(linear order)라고 하며 Totally ordered set을 Chain이라고도 한다.

팁

Example

Poset ($\mathbf{Z},\leq$)은 Totally ordered이다.
Integer $a,b$가 $a\leq b \lor b\leq a$이기 때문이다.

Poset($S,\preccurlyeq$)가 Well-ordered set이면서 $\preccurlyeq$가 $S$의 Non empty subset이 최소 Element를 가지는 경우 Total ordering이다.

팁

Example

Positive integer의 Ordered pair set $\mathbf{Z^+} \times \mathbf{Z^+}$에서 $(a_1,a_2) \preccurlyeq (b_1,b_2)$($a_1<b_1 \lor (a_1 =b_1 \land a_2\leq b_2)$)(=Lexicographic ordering)으로 Well-ordered set이다.

정보

Theorem

The principle of well-ordered induction

$S$가 Well-ordered set일 때 모든 $x\in S$에서 $P(x)=True$일 때
Inductive step: For every $y\in S$, if $P(x)$ is true for all $x\in S$ with $x\prec y$ then $P(y)$ is true

• Proof
  $P(x)$가 모든 $x\in S$에 대해 True가 아니라고 가정할 때 $P(y)$가 False인 어떤 $y\in S$가 존재하므로 $A=\{x\in S\mid P(x)\ is\ false\}$가 Nonempty set이 된다.
  $S$가 Well-ordered이기에 최소 Element $a$를 가진다.
  $a$가 $A$의 최소 Element로 선택됨에 따라 $x\leq a$인 모든 $x\in S$에 대해 $P(x)$가 True임을 알 수 있다.
  Inductive step에서 $P(a)$가 True임을 의미하며 이 Contradiction은 $P(x)$가 모든 $x\in S$에 대해 True여야 함을 보여준다.

Lexicographic Order

두 개의 Poset($(A_1,\preccurlyeq_1),(A_2,\preccurlyeq_2)$)의 Cartesian product에서 Partial ordering을 구성하기 위해 $A_1\times A_2$에서의 Lexicographic ordering은 $(a_1,a_2)\prec (b_1,b_2)$로 표현할 수 있다.
$A_1\times A_2$에 Equality를 추가하여 $\preccurlyeq$로 나타낼 수 있다.

팁

Example

Poset ($\mathbf{Z}\times\mathbf{Z},\preccurlyeq$)에서 $(3,5)\prec (4,8), (3,8)\prec(4,5), (4,9)\prec (4,11)$ 여부

• Solution
  3<4이므로 $(3,5)\prec(4,8),(3,8)\prec(4,5)$ 성립하며, 9<11이므로 $(4,9)\prec(4,11)$성립한다.

Hasse Diagrams

Finite poset에 대한 Directed graph에서 많은 Edge들은 반드시 표시할 필요가 없다.

팁

Example

Set $\{1, 2,3,4\}$에 대한 Partial ordering $\{(a,b)\mid a\leq b\}$의 Directed graph

• Solution
  이 Relation은 Partial ordering이므로 Reflexive하고 모든 Vertex에 Loop가 존재한다.
  Partial ordering은 Transitivity하기에 반드시 존재하는 Edge를 나타낼 필요가 없고 방향을 위쪽으로 향한다고 가정하면 Edge의 방향까지 표시할 필요가 없어진다.\

Maximal and Minimal Elements

Poset($S,\leq$)에 대해 $a$가 Maximal element라면 $a\leq b$인 $b\in S$가 존재하지 않고, Poset($S,\geq$)에 대해 $a$가 Minimal element라면 $b\leq a$인 $b\in S$가 존재하지 않는다.
Hasse diagram에서 가장 위의 Element가 Maximal, 가장아래의 Element가 Minimal이 된다.

팁

Example

Poset($\{2,4,5,10,12,20,25\},|$)에서 Maximal과 Minimal element

• Solution
  Poset의 Hasse Diagram은 아래와 같다.
  
  Minimal은 2, 5이고 Maximal은 12, 20, 25이다.

Poset에서 모든 다른 Element보다 큰 Element가 존재할 수 있는데 이를 Greatest element라고 하고 모든 다른 Element보다 작은 Element는 Least element라고 한다.

Poset $A$의 모든 Element보다 크거나 같은 Element를 찾을 때 $S$의 Element $u$가 $A$의 모든 Element $a$에 대해 $a\leq u$라면 $u$는 $a$의 Upper bound, $u\leq a$라면 Under bound라 한다.

Element $x$가 $A$의 Upper bound 중 가장 작은 Upper bound 일 때 $x$는 $A$의 Least upper bound라고하고, $A$의 Lower bound 중 가장 큰 Lower bound 일 때 $x$는 $A$의 Greatest lower bound라 한다.
Notation으로 각각 $glb(A), lub(A)$로 표기한다.

팁

Example

Poset($\mathbf{Z^+},|$)의 Set$\{3,9,12\}$와 $\{1,2,4,5,10\}$의 $glb, lub$

• Solution
  3,9,12로 나누어 떨어지는 수 중 가장 작은 수 $= lcm(3,9,12) = lub(\{3,9,12\})=36$
  3,9,12를나누어 떨어트리는 수 중 가장 큰 수 $=gcd(3,9,12)=glb(\{3,9,12\})=3$
  1,2,4,5,10의 최대공약수와 최소 공배수 $lcm(1,2,4,5,10)=20, gcd(1,2,4,5,10)=1$로 구할 수 있다.

Lattices

Lattice(격자)는 $lub, glb$를 가지는 Partial ordering을 의미한다.

팁

Example

Poset($\mathbf{Z^+},|$)가 Lattice인 지

• Solution
  Positive integer $a, b$에 대해 $lub, glb$, 즉 $lcm, gcd$가 존재하므로 Lattice라고 한다.

Topological Sorting

Topological sorting(위상 정렬)은 Partial ordering을 Compatible(호환)되게 하여 Total ordering으로 만드는 과정을 의미한다.

정보

Lemma

모든 Finite nonempty poset($S, \preccurlyeq$)는 적어도 하나의 Minimal element를 가진다.

• Proof
  임의의 Element $a_0$가 Minimal element가 아닐 때 더 작은 Element를 찾는다.
  이를 반복할 경우 Finite set이기에 Minimal element가 존재할 수 밖에 없다.

정보

Psudocode

Algorithm : Topological Sorting

procedure topological sort($(S,\preccurlyeq)$ : finite poset)
$k$ := 1
while $S\not=\empty$
begin
$a_k$ := a minimal element of $S$ {such an element exists by Lemma}
$S$ := $S-\{a_k\}$
$k$ := $k+1$

end {$a_1,a_2,\dots,a_n$ is compatible total ordering of $S$}

팁

Example

Poset($\{1,2,4,5,12,20\},|$)의 Compatible total ordering(Topological sorting)

• Solution
  매 Step마다 Minimal elemnt를 고르고 제외한 후 반복한다.
  즉 1 | 2, 5 | 4 | 12, 20에서 |에서의 순서만 지킨 결과값이 나온다.
  
  위 이미지와 같이 Topological sorting을 한다면 $1\prec 5\prec 2\prec 4\prec 20\prec 12$가 된다.