Relation

Generalized Unions and Intersections

 

union과 intersection은 commutative하고 associative하기 때문에, 임의대로 순서를 정하고 grouping해도 된다.

 

big U, big ∩ notations 

 

big U, big ∩ notation

Relation

 

A와 B의 관계는 AxB의 부분 집합으로 표현 가능하다.

 

Complementary Relations

: 전체 AxB 집합에서 R 집합의 원소를 제외한 집합을 의미한다.

 

Inverse Relation

: 원래의 relation의 순서를 반대로 한 relation

 

A 집합과 A 집합 그 자신과의 Relation을 구한 것을 a relation on the set A라고 한다.

Identity relation = {(a,a) | a ∈ A}

 

Properties of Relations

 

• reflexive if (𝑎,𝑎)∈𝑅𝑎(a,a)∈Ra for all 𝑎∈𝐴a∈A,
• irreflexive if (𝑎,𝑎)∉𝑅(a,a)∉R for all 𝑎∈𝐴a∈A,
• symmetric if (𝑎,𝑏)∈𝑅⇒(𝑏,𝑎)∈𝑅(a,b)∈R⇒(b,a)∈R for all 𝑎,𝑏∈𝐴a,b∈A,
• antisymmetric if [(𝑎,𝑏)∈𝑅∧(𝑏,𝑎)∈𝑅]⇒𝑎=𝑏[(a,b)∈R∧(b,a)∈R]⇒a=b for all 𝑎,𝑏∈𝐴a,b∈A,
• asymmetric 
• transitive if [(𝑎,𝑏)∈𝑅∧(𝑏,𝑐)∈𝑅]⇒(𝑎,𝑐)∈𝑅[(a,b)∈R∧(b,c)∈R]⇒(a,c)∈R for all 𝑎,𝑏,𝑐∈𝐴a,b,c∈A.

irreflexive != not reflexive

 

Composite Relation

 

합성함수와 비슷한 개념이다.

 

 

 합성함수와 마찬가지로 결합 법칙이 성립한다.

 

R^(n+m) = R^n ∘ R^m

(R^n)^m = R^(n*m)

 

R1 ∘ (R2 ∩ R3) ⊆ (R1 ∘ R2) ∩ (R1 ∘ R3)

R1 ∘ (R2 ∪ R3) = (R1 ∘ R2) ∪ (R1 ∘ R3)

 

Theorem 5

 

R is reflexive, iff IA ⊆ R

R is irreflexive, iff IA ∩ R = ∅

R is symmetric, iff R = R-1 ∩ R, R ⊆ R-1

R is asymmetric iff R ∩ R-1 = ∅

R is antisymmetric iff R ∩ R-1 ⊆ IA

R is transitive iff R∘R ⊆ R

 

Directed graph(digraph) : walk, path, cycle, loop, sling

 

a directed graph = G = <V, E>. where V is a set of vertices and E is a set of edges.

 

walk : a connected sequence of edges e1, e2, ..., en of G(or an alternating sequence of vertices and edges of G). 점들(vertices)을 따라 하나로 쭉 이어진 선들(edges)의 집합.

walk의 길이 : walk에 속한 edge들의 개수로 센다.

a trail : edge가 반복되지 않는 walk

a path : vertex가 반복되지 않는 trail

a closed walk, a circuit, a cycle : 시작과 끝 vertex가 같은 walk

loop : cycle의 길이가 1인 것

sling : cycle의 길이가 2인 것

 

graph로 나타내는 properties of relation

 

reflexive = 모든 vertex가 loop를 가지고 있을 때

irreflexive = 모든 vertex에 loop가 없을 때

symmetric = 서로 다른 두 vertex 사이에 길이 1짜리 walk가 있을 때, 그 둘 사이에 항상 sling이. 만들어질 때

asymmetic = 서로 다른 두 vertex 사이에 길이 1짜리 walk가 있을 때, 그 둘 사이에 항상 sling이 없고, loop도 없을 때

antisymmetric = 서로 다른 두 vertex 사이에 길이 1짜리 walk가 있을 때, 그 둘 사이에 sling이 없을 때

transitive = 서로 다른 두 vertex 사이에 길이 2짜리 walk가 있을 때 항상 그 둘 사이에 길이 1짜리 walk가 있어야 한다.

 

Closures of Relations

 

각각의 특성 X(reflexive, transitive....)에 대해 X closure of a relation R은 X라는 특징을 가진 R의 가장 작은 superset이다.

 

r(R) : the reflexive closure

s(R) : the symmetric closure

t(R) : the transitive closure

 

각각을 집합 연산으로 구해줄 수 있다.

 

Equivalence Relations & Equivalence Classes

 

Equivalence Relation : reflexive, symmetric, transitive

 

R on a set A가 Equivalence Relation일 때 집합 A a에 대한 equivalence class를 [a]R이라고 하며

 

[a]R = {b ∈ A | (a, b) ∈ R}

 

For every x ∈ A, x ∈ [x]R

if <x,y> ∈ R, then [x]R = [y]R

if <x,y> ∈ R, then [x]R ∩ [y]R = ∅