관계

관계

• 집합에서의 원소들 간의 순서를 고려한 것
• 관계는 곱집합의 임의의 부분집합

한 집합에서의 관계
n개의 원소를 가진 집합 A에 대한 관계: A $\times$ A의 부분집합
A $\times$ A의 원소 개수: $n^2$
m개의 원소를 가진 집합의 부분집합 개수: 2^m
A $\times$ A의 부분집합의 개수: $2^{n^2}$

이항관계(binary relation)

• 두 집합 A,B에 대하여, A로부터 B로의 이항 관계 R은 두 집합의 곱집합 A*B의 원소인 순서쌍 (a,b)가 주어졌을 때 (a,b)∈R과 aRb는 동치이다.
• 이항을 생략하기도 한다.
• 두 개 이상인 원소에 대한 관계는 'n-ary'라고 한다.

정의역(domain)

• 관계R의 원소인 순서쌍에서 첫번째 원소의 집합, Dom(R)
• Dom(R)={a|(a,b)∈R}⊆A

치역(range)

• 관계R의 원소인 순서쌍에서 두번째 원소의 집합, Ran(R)
• Ran(R)={b|(a,b)∈R}⊆A

카티시안 곱(cartesian product)
A와 B가 집합일 때, 순서쌍의 첫 번째 요소는 집합 A의 원소이고 두 번째 요소는 B의 원소로 구성된 모든 순서쌍의 집합을 A와 B의 카티시안 곱 또는 곱집합이라고 하며 A×B로 나타낸다

A×B={(x,y)|x∈A, y∈B}

두 개 이상의 집합에 대해서도 확장할 수 있다.
$A_1×A_2×...×A_n=\{x_1,x_2,...,x_n |모든i, 1≤i≤n에 대해 x_i∈ A_i\}$

역관계(inverse relations)
집합 A에서 집합 B로의 관계 R에 대한 역관계 $R^{-1}$는 집합 B에서 집합A로의 관계를 나타내며, 순서쌍 내의 순서를 다시 바꾸면 그 순서쌍은 관계 R에 속하게 된다.

$R^{-1}=\{(b,a)|(a,b)∈R\}$, aRb의 관계가 있어야만 b$R^{-1}$a가 존재하게 된다.

표현 방법

• 화살표 도표(arrow diagram): a가 A의 원소이고 b가 B의 원소라면 (a,b)∈R일 경우 집합 A에 있는 원소 a에서 집합 B에 있는 원소 b로 화살표를 그려 관계를 표현한다.

• 좌표 도표(coordinate diagram): 집합 A의 원소를 x축 위의 점으로 표시하고 집합 B의 원소를 Y축 위의 점으로 생각하여, a∈A, b∈B 관계가 있으면 a를 가리키는 x좌표 축과 b를 가리키는 y좌표축이 만나는 곳에 점으로 표시한다.

• 방향 그래프(directed graph): 관계 R이 두 집합 사이가 아닌 하나의 집합 A에 대한 관계일 때, 집합 A의 각 원소를 그래프의 정점을 표시하고 관계가 있으면 화살표가 있는 연결선으로 표현한다.

• 관계 행렬(relation matrix): 행렬을 이용. 부울 행렬은 행렬 안에 있는 모든 원소들이 0 또는 1로 표시되는 행렬을 의미한다. 즉, 관계 행렬의 행에는 집합 A의 원소, 열에는 B의 원소를 표시한다.
  관계가 있으면 1 아니면 0 으로 표현

---

여러 관계

합성 관계(composite relation)
세 집합 A,B,C 에서 $R_1$을 A에서 B로의 관계, $R_2$를 B에서 C로의 관계라 하면, A에서 C로의 합성관계 $R_1*R_2$는 다음과 같이 정의 된다.
$R_1*R_2={(a,c)|a∈A, c∈C, (a,b)∈R_1, (b,c)∈R_2}$

행렬에서는 $R_1$의 a행의 각 원소를 $R_2$의 각 행 마다 순서대로 하나씩 논리 곱을 한 것(행의 1번째 원소는 1행, 2번째 원소는 2행...)을 행단위로 논리합 한다. 해당 값은 합성 관계의 한 행

항등 관계(identity relation)

• $I_A$={(a,a)|a∈A}
• (a,b)∈$I_A$ 이면 a=b
  $I_AR=RI_B=R$

---

반사 관계(reflexive relation)
집합 A에 있는 임의의 원소x에 대하여 xRx이면 즉 (x,x)∈R 일 때 관계 R을 반사 관계라고 한다.

비반사 관계(irreflexive relation): A의 모든 원소가 반사 관계가 없는 관계(하나라도 있으면 안 된다.)

대칭 관계(symmetric relations): A에 있는 원소 x,y에 대해 (x,y)∈R 일 때 (y,x)∈R 인 관계, R의 원소 중 (a,b)가 존재하면 (b,a)가 반드시 존재해야 한다.

반대칭 관계(anti-symmetric relations): A에 있는 모든 원소 x,y에 대해 (x,y)∈R 이고 (y,x)∈R 일 때 y=x인 관계
대칭 관계와 반대칭 관계가 같이 존재할 수도 있다. R={(1,1),(2,2),(3,3)}

추이 관계(transitive relation): A에 있는 원소 x, y, z에 대해 관계 R이 (x,y)∈R이고 (y,z)∈R 이면 (x,z)∈R 인 관계

---

추이 클로우저(transitive closure)

$R^+$ = $\cup^∞_{n=1}R^n=R^1 \cup R^2 \cup ... \cup R^n$
1. 만약 (a,b)∈R이면 (a,b)∈$R^+$
2. (a,b)∈$R^+$이고 (b,c)∈R이면 (a,c)∈$R^+$ 이다.
3. 앞의 1,2의 경우를 제외하고 어느 것도 $R^+$에 속하지 않는다.

집합의 관계에 추이 관계를 찾아 더해 추이 관계가 더 이상 추가 되지 않게 한다.(이 상태가 closure, 폐포라고도 함)

반사 및 추이 클로우저(reflexive and transitive closure)
$R^*$ 추이클로우저에 반사관계를 더한 것

clouser(폐포, 폐쇄, 클로우저)
관계 R이 어떤 성질을 만족하지 않을 때, 그 성질을 만족하도록 R을 최소한 확장해서 얻은 것
$R⊆ R^+⊆ R^*$

---

동치 관계(equivalence relation)

• 관계 R에서 반사 관계, 대칭 관계, 추이 관계 성립하는 것
• 동치 관계 R의 중요한 성질로는 R이 서로 공통 부분이 없으면서 공집합이 아닌 클래스들로 S를 분할한다는 점이다.

동치류, 동치 클래스(equivalence classes)

• 집합 A에 대한 동치 관계를 R이라고 할 때, A의 각 원소 x에 대하여 [x]를 R에 대한 x의 동치 클래스라 하고 [x]={y|(x,y)∈R}
• 같은 원소 끼리 그룹
• 하나의 원소를 대표원소라고 한다.[a]
  • a를 동치 클래스의 대표 멤버라고 한다.

목집합, 상집합(quotient set)
집합 A의 동치류 모임을 A의 목집합이라 한다.

• $A \over R$={[x]|x∈A}
• $A\over R$={[a], [b], [c]}

분할(partitions)
공집합이 아닌 집합 A의 분할은 다음 조건을 만족시키는 A의 부분 집합 모임
{$A_1,A_2,...,A_n$}을 말한다.
1. $A_i≠∮$, 1≤i≤n
2. $A=U^n_{i=1}A_i$
3. $A_i \cap A_j=∮$, i≠j

x≡y(mod n): mod 합동, x와 y를 n으로 각각 나눴을 때 나머지가 같은 경우
위 개념들의 좋은 예

---

부분 순서 관계(partially odered relation)

집합 A에 대한 관계 R이 반사, 반대칭, 추이 관계인 관계

부분 순서 집합(partially order set,(poset))

• R이 A에 대한 부분 순서 관계일 때 순서쌍 (A,R),(A,≼) 기호를 사용해 나타낸다.
• 집합 내의 원소를 부분적으로 정렬할 수 있다.

Greatest(최대 원소): 집합 A의 모든 원소 x에 대해 x≤M을 만족시키는 집합 A의 원소 M
Least(최소 원소): 집합 A의 모든 원소 x에 대해 m≤x을 만족시키는 집합 A의 원소 m

최대원소와 최소원소는 집합내의 모든 원소와 비교가 가능해야한다.

Maximal(극대 원소): 부분 순서 집합에서 그와 비교 가능한 원소들 가운데 가장 큰 원소.
모든 ${\displaystyle x\in P}에 대하여, {\displaystyle M\leq x}라면 {\displaystyle M=x}$이다.
Minimal(극소 원소): 부분 순서 집합에서 그와 비교 가능한 원소들 가운데 가장 작은 원소
모든 ${\displaystyle x\in P}$에 대하여, ${\displaystyle m\geq x}$라면 ${\displaystyle m=x}$이다.

upper bound: 부분 순서 집합(A,≤)와 집합 A의 부분 집합 E가 주어졌을 때 집합 E의 모든 원소 x에 대하여 x≤M을 만족 시키는 집합 A의 원소 M, E의 상계

lower bound: 부분 순서 집합(A,≤)와 집합 A의 부분 집합 E가 주어졌을 때 집합 E의 모든 원소 x에 대하여 m≤x을 만족 시키는 집합 A의 원소 m, E의 하계

GLB(greatest lower bound): 집합 E의 하계 집합의 최대 원소, 하한

LUB(least upper bound,supremum): 집합 E의 상계 집합의 최소 원소, E의 최소 상계

lattice: 모든 원소 쌍이 (같은?)LUB, GLB를 갖는 부분 순서 관계

하세 도표(hasse diagram):부분 순서 집합(A,≼)을 그림으로 나타낼 때 이용
방향 그래프의 일종으로 화살표는 표시하지 않고 모든 연결선을 트리와 같이 모두 아래 방향을 하도록 그린다. 모든 순환은 표시하지 않고 집합 A의 원소 x,y,z에서 x≼y 이고 y≼z를 만족하는 y가 존재하지 않을 경우만 x에서 z로의 연결선을 그린다.
반사관계를 없애고 전이관계를 없애면 된다.
(x,y)∈R iff xㄷy(ㄷ: 모든 x가 y에 포함된다.)

부분이라는 용어를 쓰는 이유는 집합 A의 원의 모든 쌍이 관계를 갖는 것은 아니기 때문이다. A에 대한 R이 부분 순서 관계면, A의 두 원소 x,y에 대하여 (x,y)∈R을 x≼y로 표기하고' x가 y를 선행한다.(x precedes y)'라 읽는다.
부분 순서 집합(A,≼)에서 A의 두 원소 x,y가 x≼y 또는 y≼x 이면 x와 y를 비교 가능 하다고 하고, A의 모든 두 원소가 비교 가능하면 A를 선형 순서 집합(linearly odered set)이라고 하며, 이 경우 관계≼를 선형 순서 관계(linearly odered relation), 선형 순서(linear order)라 한다.
linearly odered, linear order, total order relation

선형 순서(linear order) 집합 A상에서의 관계 R이 다음 조건을 만족하는 관계
1. R이 부분 순서를 만족한다.
2. a∈A, b∈A 라면 aRb, bRa, 또는 a=b 중 하나가 성립한다.
LUB와 GLB 모두 존재한다.

위상 정렬 알고리즘

부분 순서 관계를 입력 받아서전체 순서 관계로 변환한다. DAG에서만 수행 가능하다.

k=1
while S !=∮
$a_k$: $a_k$=S의 최소 //진입 차수가 0인 것
S-{$a_k$}:S=S-{$a_k$} // a_k 와 연결된 간선 제거
k=k+1
return $a_1, a_2, ... , a_n$