[ 이산 수학 ] 15. 관계(2)

 

Relations with Matrix

 

 

Matrix로 R을 나타내려면, Zero-one matrix로 한다.

해당 원소가 존재하면 1, 그렇지 않으면 0으로.

 

 

A = {1,2,3} and B = {1,2} 가 있고, R은 A → B이다. R = (a,b)형태이고 a ∈ A, b ∈ B이다.

R의 조건은 a>b이다. 그런 경우 R의 원소는  {(2,1), (3,1),(3,2)} 이다.

 

 

예제)

이거 보고 몇 번째 원소들이 있는지도 파악 가능해야함

 

 

 

---

종류별 R의 Matrix 모양

 

Reflexive : 그냥 대각선으로 1 쭈루루룩

---

 

Symmetric : (a,b)가 있으면 (b,a)도 있어야 함

                       반대로 (a,b)가 없으면 (b,a)도 없어야함 

 

위와 같은 형태

 

---

Antisymmetric : (a,a)빼고는 대칭인 거 있으면 안 됨

                            (a,b) (b,a) 대칭이면 안 됨, 둘 다 없거나 하나만 있거나 해야함

 

위와 같다.

 

예제)

 

대각선 , 대칭을 분석해본다.

 

답)

 

 

---

Digraphs for Relations

 

 

각 종류별로는?

 

 

Reflxivity : 자기 자신으로 화살표를 던져야 한다.

Symmetry : (X ,Y) 로 가는 edge가 있으면                                   → (Y, X)도 있어야 한다.

Antisymmetry : (X , Y) 로 가는 edge가 있는데 X=Y 가 아니면    → (Y, X) 는 있으면 안 된다.

Transitivity : (X,Y) 랑 (Y,Z)가 edge가 있으면                               → (X,Z)도 있어야 한다.

 

 예제1)

 

Reflxivity : X = a는 loop인데 나머지는 아님

Symmetry : (조건) → (충족해야하는 것) 이건데 애초에 조건이 false이므로 true

Antisymmetry  위와 같다 

Transitivity       위 같

 

 

 

 

 

---

 

Closures of R

 

 

Closure of R with respect to P

= 성질 P(ex. reflexive,symmetry 등등..) 을 지니고, R을 포함할 수 있는 가장 작은 집합 S

 

+ Antisymmetry 는 만들 수 없음. 원소를 더하는 건 가능한데, 빼는 건 안 되기 때문에 

 

1) P를 지니고 있어야 함

2) R도 데리고 있어야 함

3) P를 만족하기 위한 원소를 추가할 수 있음 (최소한으로 추가하셈)

 

 

 

S가 R보다 더 큰 집합이다.

 

 

 

 

 ex)

 

위 R은 A에 대해 reflexive하지 않다. 어떻게 reflexive하게 바꾸되, R을 포함한 가장 작은 집합을 만들 수 있을까?

 

(2,2) (3,3)을 더한다. R에 없긴한데 어차피 R을 포함하긴 하니까 ㄱㅊ

R을 포함하고 있는 새로운 S가 Reflxive 하니까 ㅇㅋ

 

 

추가 예제)

 

---

추가 예제)

 

Transitive closure는 P를 만족하기 위해 추가하면 할수록

추가해야하는 원소가 더 많아지기 때문에 복잡해진다. 

 

---

추가 예제)

 

 

 

PDF에 더 있으니 찾아보기

 

 

(출처)

한동대학교 최희열교수님 - 이산수학