B. Sets, Etc.

집합 등에 대해 알아보자.

B.1. Sets

집합멤버원소의 구별 가능한 모임이다. 두 집합의 원소들이 같다면 그 집합은 같다고 한다. \emptyset공집합, \mathbb{Z}정수 집합, \mathbb{R}실수 집합, \mathbb{N}자연수 집합이다. A의 원소가 B의 원소이면 A는 B의 부분집합, A가 B의 부분집합이면서 A와 B가 같지 않으면 A를 B의 진부분집합이라 한다. 집합 연산에 대해서는 합집합, 교집합, 차집합 등이 있다. 집합 연산에 대한 여러 법칙이 있으며 이는 벤 다이어그램으로 쉽게 시각화 가능하다. 교집합이 없으면 서로소라 한다. 집합들의 집합이 쌍별 서로소면서 그 합집합이 S면 이를 S의 분할이라 한다. 집합의 원소 수를 기수라 한다. 기수가 유한이면 유한집합, 무한이면 무한집합이다. 집합의 기수가 \mathbf{N}과 일대일대응이 되면 가산무한, 아니면서 무한이면 불가산이라 한다. 원소가 n개인 유한집합을 n-집합이라 한다. 1-집합은 싱글톤이다. 원소가 k개인 부분집합을 k-부분집합이라 한다. 부분집합들의 집합을 멱집합이라 한다. 두 원소의 순서가 주어진 집합을 순서쌍이라 한다. 두 집합의 카티션 곱은 두 집합에서 원소를 하나씩 취한 순서쌍의 집합이다. 집합 n개의 카티션 곱은 n-튜플이다.

B.2. Relations

두 집합의 이진 관계는 카티션 곱의 부분집합이다. R ⊆ A × A가 모든 a ∈ A에 대해 a R a이면 반사적, a, b ∈ A에 대해 a R b가 b R a를 함의하면 대칭적, a, b, c ∈ A에 대해 a R b, b R c가 a R c를 함의하면 추이적이라 한다. 반사적, 대칭적, 추이적인 관계는 동치 관계이다. 집합 A에 대해 R이 동치 관계이면 A를 R의 동치류라 한다.

Theorem. (An equivalence relation is the same as a partition) 집합 A에 대해 동치 관계 R에 대한 동치류들은 A의 분할을 정의한다. A의 분할은 A에 대해 동치류가 되는 동치 관계를 유도한다.

a R b, b R a면 a = b면 반대칭이라 한다. 반사적, 반대칭적, 추이적인 관계를 부분a R b, b R a면 a = b면 반대칭이라 한다. 반사적, 반대칭적, 추이적인 관계를 반순서라 한다. 집합에 반순서가 존재하면 반순서 집합이다. 반순서 관계 R에 대해 a R b인 b ∈ A가 없으면 a를 A의 극대원소라 한다. 모든 a, b ∈ A에 대해 a R b거나 b R a라면 R을 완전관계라 한다. 완전관계인 반순서를 완전순서 또는 선형순서라 한다. 추이적인 완전 관계가 반대칭적이거나 반사적이지 않다면 완전선순서라 한다.

B.3. Functions

집합 A, B에 대해 함수 f는 a ∈ A에 대해 오직 하나의 b ∈ B가 존재해 f(a) = b가 되는 이진 관계이다. A를 f의 정의역, B를 공역이라 한다. a는 함수의 인자, b는 이라 한다. 함수값이 전부 같고 정의역과 공역이 같은 함수를 같다고 한다. 유한수열은 정의역이 {1, …, n}인 함수이다. 무한수열은 정의역이 \mathbb{N}인 함수이다. 정의역이 집합 n개의 카티션 곱일 경우 (a_{1}, \cdots, a_{n})a_{i} 각각을 f의 인자라 한다. f(a) = b면 b가 f에 대한 a의 이라 하며 f(A)를 f의 치역이라 한다. 치역이 공역과 같으면 전사함수라 한다. B로의 함수라고도 한다. 서로 다른 인자가 서로 다른 상을 갖는 함수를 단사함수라 한다. 일대일함수라고도 한다. 전사함수이면서 단사함수면 전단사함수라 한다. 일대일대응이라고도 한다. A에서 A로의 일대일대응은 순열이라고도 한다. 전단사함수에 대해 역함수를 정의할 수 있다.

B.4. Graphs

방향그래프(다이그래프) G는 정점들로 이뤄진 정점 집합 V와 정점들의 이진 관계인 간선들로 간선 집합 E의 쌍이다. 자가순환도 가능하다. 비방향그래프는 간선이 비순서쌍인 경우이다. 방향그래프에서 간선이 (u, v)면 이는 u로부터 연관하고 u를 떠나며 v로 연관하고 v로 진입한다고 한다. 비방향그래프에서는 간선 (u, v)는 u, v에 연관한다고 한다. v는 u에, u는 v에 인접한다고 한다. 비방향그래프에서 정점의 차수는 그에 연관된 간선의 수이다. 차수가 0인 정점은 고립이다. 방향그래프에서는 내차수는 그로 진입하는 간선의 수, 외차수는 그를 떠나는 간선의 수, 차수는 내차수와 외차수의 합이다. 길이 k의 경로는 연속된 간선 k개의 집합이다. 이는 정점 v_{0}, \cdots, v_{k}포함한다고 한다. u에서 v로의 경로가 존재하면 도달 가능하다고 한다. 경로 내 모든 정점이 다르면 단순 경로라 한다. 경로의 부분집합인 경로는 부분경로이다. 방향그래프에서 단순경로의 시작점과 끝점이 같으면 순환이다. 순환에서 모든 정점이 다르면 단순 순환이다. 자가 순환이 없는 방향그래프는 단순이다. 비방향그래프에서도도 경로의 시작점과 끝점이 같으면 순환이다. 순환에서 모든 정점이 다르면 단순 순환이다. 순환이 없는 그래프는 비순환이다. 비방향그래프는 모든 정점이 서로간 도달가능하면 연결이라 한다. 그래프 내 연결부분은 서로간 도달가능성의 동치관계를 이루는 정점 집합이다. 방향그래프는 모든 정점이 서로간 도달가능하면 강연결이라 한다. 그래프 내 강연결부분은 서로간 도달가능성의 동치관계를 이루는 정점 집합이다. 그래프간 정점/간선간 전단사함수가 존재하면 동형이라 한다. 그래프의 부분집합인 그래프를 부분그래프라 한다. 정점들의 부분집합으로부터 부분그래프는 유도될 수 있다. 비방향그래프에 대해 방향 버전을 생각할 수 있고, 방향그래프에 대해 비방향 버전을 생각할 수 있다. 방향그래프에서 u의 근방은 (u, v)나 (v, u)가 간선으로 존재하는 정점들이다. 완전그래프는 모든 정점이 인접한 비방향그래프이다. 이분그래프는 정점들이 두 집합으로 분할되어 간선들이 두 집합간에만 존재하는 비방향그래프이다. 비순환 비방향그래프는이고 연결 비순환 비방향그래프는 나무라 한다. 방향비순환그래프는 DAG라 한다. 정점간 간선이 복수 존재할 수 있다면 중복그래프라 한다. 초그래프는 간선이 두 정점이 아니라 정점의 집합들을 연결하는 초간선이 주어진 그래프이다. 비방향그래프의 간선 (u, v)에 대한 수축은 간선의 두 정점 u, v를 새 정점 x로 수축시킨 그래프이다.

B.5. Trees

트리를 알아보자.

B.5.1. Free trees

자유 나무는 연결비순환비방향그래프이다. 연결성이 없으면 이다.

Theorem. (Properties of free trees) 비방향그래프에서 다음은 동치이다.

  • G는 자유 나무이다.
  • G 내의 임의의 정점 쌍간에는 유일한 단순 경로가 존재한다.
  • G는 연결이나, 간선을 하나 제거하면 비연결이 된다.
  • G는 연결이고, E = V – 1이다.
  • G는 비순환이고, E = V – 1이다.
  • G는 비순환이나, 간선을 하나 추가하면 순환이 된다.

B.5.2. Rooted and ordered trees

뿌리 나무는 한 정점이 뿌리로 구분지어지는 나무이다. 이 경우 정점을 노드라고도 한다. 뿌리에서 노드로의 경로 내 임의의 노드는 그 노드의 선조이며 y가 x의 선조면 x는 y의 후손이다. 이 때 y ≠ x면 y는 x의 진선조, x는 y의 진후손이다. 나무에서 x를 뿌리로 하는 부분나무를 생각할 수 있다. 뿌리에서 x로의 경로의 마지막 간선이 (y, x)면 y를 x의 부모, x를 y의 자식이라 한다. 두 노드가 부모를 공유하면 형제이다. 자식이 없는 노드는 또는 외부 노드이다. 잎이 아니면 내부 노드이다. 노드의 자식의 수는 차수와 같다. 뿌리에서 x로의 경로의 길이는 x의 깊이이다. 나무의 은 깊이가 같은 노드들이다. 노드의 높이는 그 노드에서 잎으로의 가장 긴 경로의 길이이다. 순서 나무는 노드의 각 자식에 순서가 부여된 트리이다.

B.5.3. Binary and positional trees

이진 나무는 노드가 유한 개인 나무로 노드가 없는 빈 나무이거나, 뿌리 노드왼쪽 자식을 뿌리로 하는 왼쪽 이진 부분나무, 오른쪽 자식을 뿌리로 하는 오른쪽 이진 부분나무로 구성되는 나무이다. 부분나무가 없으면 그 자식은 부재/분실이라 한다. 왼쪽 자식오른쪽 자식 은 구분된다. 부재한 자식이 없는 이진 나무를 꽉 찬 이진 나무라 한다. 노드의 자식이 서로 다른 정수로 구별되는 것을 위치 나무라 한다. i번째 자식이 없으면 부재라 한다. k진 나무는 위치 나무 중 모든 노드의 차수가 최대 k인 것이다. 완전 k진 나무는 모든 내부 노드의 차수가 k이고 모든 잎의 깊이가 같은 나무이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중