[이산수학]인접행렬, 인접리스트로 그래프 표현하기
그래프의 표현: 인접행렬, 인접리스트 ■ 인접행렬(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.
[이산수학]관계의 정의역, 공번역, 치역이란? 구하는 법은?
관계와 관련된 집합들의 명칭은 위치나 의미에 따라 달리 표현합니다. ■ 정의역(Domain) 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 첫 번째 원소가 포함되어 있는 집함, 즉 집합 A dom(R)={a|a∈A} ■ 공번역(Codomain) 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 두 번째 원소가 포함되어 있는 집합, 즉 집합 B codom(R)={b|b∈B} ■ 치역(Range) 집합 A에서 집합 B로 가는 관계 R에 속한 순서쌍의 두 번째 원소들을 모아놓은 집합, 공번역의 부분집합 ran(R)={b|(a,b)∈R}⊆B 예제 집합 A = {(x|1≤x≤5, x는 정수}이고, A에서 A로 가는 관계 R은 다음과 같을 때, 관계 R의 정의역, 공변역, 치역을 구하세요. R =..
2020. 8. 2.
[이산수학]동치관계와 동치류란?_예제포함
이산수학 동치관계, 동치류 예제로 이해하기 ■ 동치관계 관계에서 동치관계라는 것은 집합의 원소들이 '같다'라는 것을 의미합니다. 즉 어떤 관계가 동치관계라고 하면, 그 관계에 포함된 순서쌍 원소 (a, b)에서 a와 b가 '같다'고 할 수 있습니다. 10진수의 7과 2인수 111이 같은 수임을 의미하는 것과 같습니다. 동치관계가 성립되려면 반사관계, 대칭관계, 추이관계가 모두 성립해야 합니다. 예제 정수 집합 Z에 대한 관계 R = {(a,b) ∈ Z × Z|a=b} 일 때, 관계 R이 동치관계인지 판별하라. 풀이 더보기 예제풀이 - (a,b) ∈ R일 때, a = b이다. ∴관계 R은 반사관계다. - (a,b) ∈ R일 때, a = b므로 b = a도 성립하여 (b, a) ∈ R이다. ∴관계 R은 대칭..
2020. 7. 30.
