[이산수학] 추이폐포와 연결관계
■ 추이폐포(Transitive Closure) 집합 A에 대해, 관계 R를 포함하면서 추이관계를 갖는 관계 S 추이페포를 구하는 과정에서 새로운 순서쌍이 생기기 때문에 앞서 다룬 반사폐포나 대칭폐포를 구하는 것보다 복잡합니다. 예를 들어 집합 A = {1, 2, 4} 집합 A에 대한 관계 R = {(1,1),(1,4),(2,1),(4,2)} 위의 두 요건을 이용해 추이페포 S를 구해보겠습니다. (2,1)이 관계 R에 존재하고, (1, 4) 또한 존재합니다. 추이폐포가 되기 위해서는 (2,1)의 앞의 원소 2와 (1,4)의 뒤의 원소인 4으로 만들어진 순서쌍 (2, 4)이 추가되어야 합니다. 이제는 (2, 4)에 대해서도 추이폐포가 되도록 순서쌍을 추가해야 합니다. 즉 관계 R에 (2,4)도 있고, (4..
2020. 8. 21.
[이산수학]인접행렬, 인접리스트로 그래프 표현하기
그래프의 표현: 인접행렬, 인접리스트 ■ 인접행렬(Adjacency Matrix) 인접행렬은 그래프를 행렬 형태로 표현하는 방법입니다. 그래프를 구성하는 꼭짓점을 행렬의 각 원소로, 꼭짓점에 근접하는 변을 1 또는 0으로 표기하여 그래프로 표현합니다. 그래프 G = (V, E) 에서 |V| = n일 때, n × n 행렬로 나타내는 방법입니다. 그래서 그래프 G = (V, E) 에서 |V| = 3일 때, 그래프 G를 인접행렬로 표현하면 3 × 3 행렬이 됩니다. 그리고 꼭짓점에 근접하는 변이 두 꼭짓점 사이에 존재하면 행렬에 해당하는 원소의 값이 1, 꼭짓점 간에 변이 존재하지 않는다면 행렬에 해당하는 원소의 값이 0이 됩니다. 위 그래프를 인접행렬로 표현해보겠습니다. G = (V, E) V = {a, b..
2020. 8. 10.
[이산수학]그래프의 종류2(연결 그래프, 완전 그래프, 정규 그래프, 이분 그래프)
이산수학_그래프의 종류2(연결 그래프, 완전 그래프, 정규 그래프, 이분 그래프) 예제로 이해하기 ■ 연결 그래프(Connected Graph) 그래프 G = (V, E) 내에 있는 임의의 꼭짓점 u, v 간에 경로가 있는 그래프 예제 다음 중 연결 그래프인 것과 아닌 것을 구분하라. 풀이 더보기 예제풀이 (1) 그래프 안에 있는 모든 꼭지점 간에 경로가 존재한다. 예를 들어 e에서 d로 가는 경로는 e - b- c - a- f - b - d다. ∴ 연결그래프다. (2) 그래프의 꼭짓점들 중 a, b, c, d 와 e 혹은 f 간에는 경로가 존재하지 않는다 . ∴ 연결그래프가 아니다. ■ 완전 그래프(Complete Graph) 그래프 G = (V, E) 내에 있는 모든 꼭짓점 u, v 간에 변이 있는 ..
2020. 8. 9.
[이산수학]그래프의 종류1(부분 그래프, 부분신장 그래프, 동형 그래프, 평면 그래프)
■ 부분 그래프(Subgraph) 그래프 G = (V, E)가 있을 때, V' ⊆ V 이고 E' ⊆ E인 그래프 G' = (V', E') 어떤 그래프 G가 있을 때 그래프에 포함되는 일부 꼭짓점과 변으로만 그린 그래프를 부분 그래프라고 합니다. ■ 부분신장 그래프(Spanning Graph) 그래프 G = (V, E)가 있을 때, V' = V 이고 E' ⊆ E인 그래프 G' = (V', E') 부분 그래프 중에서 그래프 G의 꼭짓점을 모두 포함한 부분 그래프를 부분신장 그래프라고 합니다. 예를 들어 그래프 G가 다음과 같이 정의되고 있다고 하면, G = (V, E) V = {(A, B, C, D)} E = {(A, B), (A, D), (B, C), (C, D), (D, B)} G 그래프, G의 부분 그..
2020. 8. 9.
[이산수학]그래프 개념과 용어 정리(루프, 경로, 회로, 인접)/예제포함
그래프는 시작적 도구로써 복잡한 작업의 과정이나 구조를 표현하는 방법입니다. 현실 세계의 요소를 점의 집합과 그 점들 간의 선으로 표현합니다. 그래서 주요 도시를 연결하는 도로, 도시의 지하철 지도가 대표적인 예입니다. ■ 그래프(Graph) 그래프는 원소를 꼭짓점으로, 원소들 간의 관계를 변으로 표현합니다. 즉, 그래프는 꼭짓점과 변으로 구성되므로 꼭짓점의 집합과 변의 집합으로 표현할 수 있습니다. G - (V, E)는 "그래프 G는 꼭짓점 집합 V와 변의 집합 E로 구성된다"는 것을 의미합니다. ■ 인접(adjacent)과 근접(incident) 그래프 G = (V, E)에서 꼭짓점 u, v를 연결한 변 e가 있을 때 꼭짓점 u,v는 서로 인접하고, 변 e는 꼭짓점 u,v에 근접합니다. 그래프에서는 ..
2020. 8. 9.
[이산수학] 함수의 상, 정의역, 공변역, 치역
■ 상(Image), 정의역(Domain), 공변역(Codomain), 치역(Range) 집합 A에서 집합 B로 가는 함수 f: A → B에 대해, 집합 A의 원소 a에 대응하는 집합 B의 원소 b는 상(함숫값)라고 한다. 집합 A를 정의역라고 하며 dom(f)로 표기한다. 집합 B를 공변역라고 하며 codom(f)로 표기한다. 상(함숫값)의 집합을 치역라고 하며 ran(f)={f(a)|a ∈ A}로 표기한다. 예제 다음은 집합 A에서 집합 B로 가는 관계를 보이는 그림입니다. 함수인지 아닌지 판별하고 함수면 정의역, 공변역, 치역을 구하세요. 풀이 (1) 집합 A의 원소 중 c에 대응되는 상을 갖지 않습니다. ∴ 함수가 아니기 때문에 정의역, 공변역, 치역을 구할 수 없습니다. (2) 집합 A의 모든 ..
2020. 8. 6.
[이산수학]집합의 연산1 (합집합, 교집합, 차집합)_벤 다이어그램/예제
이산수학 합집합, 교집합, 차집합 벤 다이어그램/예제 ■ 합집합 집합 A, B가 있을 때, 집합 A와 B에 모두 속하거나 두 집합 중 합집합에 속하는 원소들로 구성되는 집합 A U B = {x|x∈A∨x∈B} ■ 교집합 집합 A, B가 있을 때, 집합 A와 B에 모두 속하는 원소로 구성되는 집합 A ∩ B = {x|x∈A∧x∈B} ■ 차집합 집합 A, B에 대하여 A에는 속하지만 B에는 속하지 않는 원소로 구성되는 집합 A - B = {x|x∈A∧x∈∉B} 예제 집합 A, B, C를 보고 다음을 구하여라 A = {a, b, c, d} B = {c, d, f. g, h} C = {f. h} (1) A U B (2) B ∩ C (3) B - A 풀이 더보기 예제풀이 (1) A U B = {a, b, c, d..
2020. 8. 2.
[이산수학]집합의 연산2 (대칭차집합, 여집합, 곱집합, 멱집합)_벤다이어그램, 예제
[이산수학]집합의 연산2 (대칭차집합, 여집합, 곱집합, 멱집합) ■ 대칭차집합 (Symmetric Difference): A ⊕ B 집합 A, B에 대하여 A - B에 속하거나 B - A에 속하는 원소로 구성되는 집합 A ⊕ B = {x|(x∈A∧x∉B)∨(x∉A∧x∈B)} = {x|(x∈A-B)∨(x∈B-A)} ■ 여집합 또는 보집합(Complement) 워드 ■ 곱집합(Cartesian Product): A X B 집합 A, B에 대하여 a ∈ A, b ∈ B일 때, 순서쌍 (a, b)의 집합 A × B = {(a, b)|a∈A ∧ b∈B} |A × B| 곱집합은 교환법칙이 성립하지 않습니다. 즉, A × B와 B × A의 결과는 서로 다릅니다. ■ 멱집합(Power Set): P(A) n개의 원소..
2020. 8. 2.
