[이산수학] 관계

기본사항

• 곱집합 : 집합 A와 B의 곱집합 A x B는 A원소와 B원소의 모든 순서쌍들의 집합
  
• 관계 : 집합 X에서 집합 Y로의 이항관계 R은 X x Y의 부분집합
  
  • (x,y) ∈ R → x와 y는 R의 관계가 있다 → xRy로 표기
    
  • X = Y면 R을 X에서의 관계
    
    

관계의 표현

1. 화살표 도표
   
2. 방향 그래프
   
   • 그래프 : 점과 선으로 이루어진 도형
     
   • 방향그래프 : G = (V, E)에서 변이 방향을 가지면 방향그래프 (방향을 가지지 않으면 무향그래프)
     
3. 부울행렬
   
   • (a₁, b₂) ∈ R 이면 M₁₂ = 1, 아니면 0
     
     

   • 관계의 성질

     • 성질의 종류
       1. 반사적 성질 : ∀a∈A, (a, a)∈R
       2. 대칭적 성질 : ∀a,b∈A, (a, b)∈R ⇒ (b,a)∈R
       3. 추이적 성질 : ∀a,b,c∈A, ((a,b)∈R ∧ (b,c)∈R) ⇒ (a,c)∈R
       4. 관계의 성질과 부울행렬
       
     • 반사적 성질에 해당하는 행렬은 대각원소가 모두 1
       
     • 대칭적 성질에 해당하는 행렬은 대칭행렬
       
     • 추이적 성질 : 행렬의 부울곱을 실행해 1로 나오는 값이 1이어야 함
       
       

관계의 종류

• 역관계
  

  • R-¹ = { (y, x)

    (x, y) ∈ R} ⊂ Y x X

  • 각 원소의 (x, y)를 (y,x)로 바꿔줌
    
• 합성관계
  
  • R : A에서 B로의 관계, S:B에서 C로의 관계라고 가정할때. R과 S의 합성관계
    

  • S∘R = {(a, c) ∈ A×C

    a ∈ A, b ∈ B, c ∈ C, (a, b) ∈ R, (b, c) ∈ S}

  • 합성관계의 부울행렬 표현
    
• 동치관계
  
  • R이 집합 A에서 관계. R이 반사적, 대칭적, 추이적이면 R을 동치관계라고 부름
    
• 동치류
  

  • R이 집합 A에서의 동치 관계일때, A의 임의원소 a에 대해서 [a] = {x∈A

    (a,x) ∈ R}를 a의 동치류라고 부름