이 영역을 누르면 첫 페이지로 이동
컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

페이지 맨 위로 올라가기

컴퓨터와 수학, 몽상 조금

컴퓨터공학, 딥러닝, 수학 등을 다룹니다.

14. 관계와 부분 순서 (Relations and Partial Orders)

  • 2020.12.06 17:24
  • 학부 수업/이산수학
반응형

관계 $R$은 집합 $A$와 집합 $B$의 곱집합의 부분집합이다.

$$R\subseteq A\times B$$

곱집합은 집합 $A$와 $B$의 조합으로 다음과 같이 정의된다.

$$ \{a, b\}\times \{c, d\} = \{(a, c), (a, d), (b, c), (b, d) \}$$

관계는 이 곱집합의 부분집합인데, 예를들어 집합 $A$가 학생의 집합이고, $B$가 수강 과목의 집합일 때, 백지오가 이산수학을 수강하는 관계를 다음과 같이 나타낼 수 있다.

$$ (\text{백지오}, \text{Discrete Math}) \in R,_\text{(백지오)}R_\text{(Discrete Math)} $$

관계  $R$이 정의하는 것은 상황에 따라 달라지는데, 수학적 표기법으로 다음과 같이 나타낼 수 있다.

$$ A = \mathbb{Z}: xRy \iff x \equiv y \mod(5)$$

이때, $\iff$ 뒤에 있는 것이 관계 $R$의 정의가 된다. 예를들어, 위 $R$은 $(6, 1)$에 대해 성립하고, $(4, 5)$에 대해서는 성립하지 않는다.

관계의 그래프 표현

집합 $A$에 대한 관계 $R$은 유향 그래프 $G=(V, E)$로 표현될 수 있다. $V=A, E=R$을 나타낸다.
어렵게 생각할 것 없는게, 우리가 드라마 등에서 쉽게 접하는 관계도도 이 일종이다.

출처: TVN

여러가지 관계들

  • 모든 $x\in A$에 대하여, $xRx$가 성립할 경우 반사Reflexive라고 한다.
  • 모든 $x, y \in A$에 대하여, $xRy \rightarrow yRx$일 경우 대칭Symmetric이라고 한다.
  • 모든 $x, y \in A$에 대하여, $xRy \wedge yRx \rightarrow x=y$일 경우 비대칭Anti-Symmetric이라고 한다.
  • 모든 $x, y, z \in A$에 대하여, $xRy \wedge yRz \rightarrow xRz$일 경우, 추이Transitive라고 한다.
  반사 대칭 비대칭 추이 특이사항
$x\equiv y \mod(5)$ Y Y N Y 동치 관계
$x | y$ Y N Y Y  
$x\leq y$ Y N Y Y 부분 순서 관계

동치Equivalence 관계

동치 관계에서는 반사, 대칭, 추이가 성립된다. 동치 클래스는 $[x]$와 같이 표현되며, $xRy$가 성립되는 모든 y를 의미한다.

예를들어, $R$이 $x\equiv y \mod (5)$일 때 $[7]$은 아래와 같다.

$$[7] = \{\cdots , -3, 2, 7, 12, \cdots \}\\
[7] = [-3] = [2] $$

부분 순서Partial Order 관계

집합 $A$의 분할partition $\{A_1, A_2, \cdots, A_n\}$은 $A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A$이며, 다른 집합과 원소가 중복되지 않고, 공집합이 아닌 집합들을 말한다.

어떤 관계가 반사, 비대칭, 추이를 만족할 경우 약한 부분 순서weak partial order 관계이고, 비반사, 비대칭, 추이를 만족할 경우 강한 부분 순서strong partial order 관계이다.

비반사란, $x$가 $x$와의 관계를 갖는 것을 불허하는 조건이다.

부분 순서 관계는 $\preccurlyeq$ 기호로 나타내고, $(A, \preccurlyeq)$ 집합은 부분 순서 집합poset이라고 한다.
부분 순서 집합 $(A, \preccurlyeq)$는 노드 집합 $A$와 간선 집합 $\preccurlyeq$를 갖는 유향 그래프이다.

하세 도형Hasse Diagram

부분 순서 집합 $(A, \preccurlyeq)$의 하세 도형은 self-loop와 추이 연결 간선을 제외하고 노드 $A$와 간선 집합을 이용해 그린 도형이다.

부분 순서 집합에는 셀프 루프는 있으나, 이외에 방향 사이클은 존재하지 않는다. 이러한 부분 순서 집합에서 셀프 루프를 제외하면 방향 비순환 그래프 DAG가 된다.

$a\preccurlyeq b$ 혹은 $b\preccurlyeq a$인 경우, $a, b$가 비교 가능comparable하다고 한다. 반대 경우에는 비교 불가incomparable하다고 한다.

전순서Total Order 관계

모든 원소 쌍이 비교 가능한 부분 순서 관계를 전순서 관계라고 한다.
부분 순서를 전순서로 변환하는 것을 위상 정렬Topological Sort이라고 한다.

부분 순서 집합 $(A, \preccurlyeq)$를 위상 정렬한 결과는 전순서 집합 $(A, \preccurlyeq_T)$이다. $(\preccurlyeq \subseteq \preccurlyeq_T)$

모든 유한 부분 순서 집합은 위상 정렬이 가능하다.

$x\in A$에 대해, $y\preccurlyeq x$이고 $x$와 다른 $y$가 존재하면 minimal이라 하고, $x\preccurlyeq y$이면 maximal이라 한다.

증명: 모든 유한 부분 순서 집합은 위상 순서를 갖는다.

보조 증명: 모든 유한 부분 순서 집합은 Minimal 원소를 갖는다.

체인이 각기 다른 원소 $a_1 \preccurlyeq a_2 \preccurlyeq \cdots \preccurlyeq a_t$들의 시퀀스이고, $t$가 체인의 길이라 하자.

$a_1 \preccurlyeq \cdots \preccurlyeq a_n$이 최대 길이의 체인이라 할 때,

$\exists a \not \in \{a_1, \cdots, a_n\} \text{ and } a\preccurlyeq a_1$ 라면,

$a\preccurlyeq a_1 \preccurlyeq \cdots \preccurlyeq a_n$이 존재할 수 없으므로, (최대 길이보다 긴 체인이므로) 성립하지 않는다.

$\exists a \in \{a_1, \cdots, a_n\} \text{ and } a\preccurlyeq a_1$이면,

$a\preccurlyeq a_1 \preccurlyeq \cdots \preccurlyeq a \preccurlyeq, \preccurlyeq a_n$으로 사이클이 존재하므로, 성립하지 않는다.

보조 증명에 의해, $a_1$은 항상 minimal 원소가 된다.

이제 어떤 부분 순서 집합 $p$에서 minimal 원소를 $a_1$을 제거해도 $p$는 여전히 부분 순서 집합이므로, 부분 순서 집합 전체에 위상 순서가 존재함이 귀납적으로 증명된다.

반응형

'학부 수업 > 이산수학' 카테고리의 다른 글

16. 점근법 표현들 (Asymptotic Notations)  (0) 2020.12.06
15. 적분의 상한과 하한(Lower/Upper Bound of Integration)  (0) 2020.12.06
13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)  (0) 2020.12.06
12. 통신 네트워크 (Communication Networks)  (0) 2020.12.06
11. 그래프 이론과 신장 트리 (Spanning Tree)  (1) 2020.12.05

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 16. 점근법 표현들 (Asymptotic Notations)

    16. 점근법 표현들 (Asymptotic Notations)

    2020.12.06
  • 15. 적분의 상한과 하한(Lower/Upper Bound of Integration)

    15. 적분의 상한과 하한(Lower/Upper Bound of Integration)

    2020.12.06
  • 13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)

    13. 그래프 이론과 오일러 순회, 해밀턴 경로 (Euler Tour, Hamiltonian Path)

    2020.12.06
  • 12. 통신 네트워크 (Communication Networks)

    12. 통신 네트워크 (Communication Networks)

    2020.12.06
다른 글 더 둘러보기

정보

컴퓨터와 수학, 몽상 조금 블로그의 첫 페이지로 이동

컴퓨터와 수학, 몽상 조금

  • 컴퓨터와 수학, 몽상 조금의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • 분류 전체보기 (276)
    • Tech Trend (3)
    • Deep Learning (77)
      • 공부 노트 (21)
      • 논문 리뷰 (44)
      • 논문 스키밍 (1)
      • 영상처리 (11)
    • Engineering (3)
      • Tips (2)
      • Experiences (1)
    • Blog (42)
      • 회고 & 계획 (16)
      • 내 이야기 (8)
      • 리뷰 (3)
      • 군대에 간 공돌이 (9)
      • ML엔지니어 취업 도전기 (1)
      • 여행 (4)
    • 학부 수업 (141)
      • 머신러닝 (16)
      • C프로그래밍 (8)
      • 자료구조 (11)
      • 알고리즘 (17)
      • 디지털시스템 (25)
      • 컴퓨터구조 (11)
      • 확률과 통계 (21)
      • 선형대수학 (14)
      • 이산수학 (18)
      • 데이터시각화 (0)
    • 강의 (9)
      • 딥러닝 기초 (7)
      • Python (2)

공지사항

인기 글

정보

백지오의 컴퓨터와 수학, 몽상 조금

컴퓨터와 수학, 몽상 조금

백지오

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
반응형

나의 외부 링크

  • profile
  • github
  • linkedin

방문자

  • 전체 방문자
  • 오늘
  • 어제
Powered by Tistory / Kakao. © 백지오. Designed by Fraccino.

티스토리툴바