이산구조기초-관계4

동치관계와 부분순서관계

동치관계(Equicalence Relation)

• 동치는 '같다'라는 의미
• 동치관계라는 것은 집합의 원소들이 '같다'는 것을 의미
  

동치류(Equivalence Class: [a])

동치류의 분할

부분순서관계(Partial Order Relation)

집합 A에 대한 관계 R이 반사관계, 반대칭관계, 추이관계가 성립하는 관계

• 순서관계를 갖기 위해서는 어떤 관계 R에서 a≠b 일때
  (a,b)가 존재하면 (b,a) 가 존재할 수 없음
• 그러므로 관계 R에 반대칭관계가 성립할 때 그 관계 R은 순서관계를 가짐

비교가능(Comparable), 비교불가능(Noncomparable)

• 비교가능 기호(≼)나 비교불가능 기호(⋠)는 값의 크기를 비교하는 연산자가 아닌 우선순위를 비교하는 연산자

완전순서(Total Order)

하세도표

• 방향그래프와 부분순서관계의 성질을 이용하여 표기하는 방식

하세도표 그리는 규칙

• 부분순서관계는 반사관계가 성립하기 때문에 루프가 생략 가능함
• 규칙(2)는 부분순서관계는 반대칭관계가 성립하기 때문
• 규칙(3)의 경우는 부분순서관계는 추이관계가 성립하기 때문

극대원소(Maximal Element)

극대원소는 집합 A에 대한 부분순서관계 R을 하세도표로 표현했을 때 가장 상위에 위치하는 하나이상의 원소들로, 부분순서집합 A에 포함되는 원소들 중 가장 우선순위가 높은 원소들을 의미, 하지만 이 극대원소들 간의 우선순위는 같음

극소원소(Minimal Element)

극소원소는 집합 A에 대한 부분순서관계 R을 하세도표로 표현했을 때 가장 하위에 위치하는 하나이상의 원소들로, 부분순서집합 A에 포함되는 원소들 중 가장 우선순위가 낮은 원소들을 의미

최대원소(Greatest Element)

• 최대원소는 집합 A에 대한 부분순서관계 R을 하세도표로 표현했을 때 가장 상위에 위치하는 단 하나의 원소
• 부분순서집합 A에 포함되는 원소들 중 가장 우선순위가 높은 원소를 의미

최소원소(Least Element)

• 최소원소는 집합 A에 대한 부분순서관계 R을 하세도표로 표현했을 때 가장 하위에 위치하는 단 하나의 원소
• 부분순서집합 A에 포함되는 원소들 중 가장 우선순위가 낮은 원소를 의미