[이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등)_예제포함
[이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등) ■ 트리(Tree) - 트리 T는 비순환, 연결 그래프 - 루트(Root)라고 불리는 노드가 반드시 하나 있어야 함 - 트리 T를 구성하는 꼭짓점 v, w 간에, v에서 w로 가는 단순 경로가 있음 ▶ 선형과 비선형, 순환과 비순환의 뜻은? ■ 서브 트리(Sub Tree) - T를 구성하는 꼭짓점 v를 루트로 하는 트리 예제 다음 중 트리인 것은? 풀이 더보기 예제풀이 (1) A가 루트며 그래프를 구성하는 꼭짓점 A부터 G 사이에는 단순 경로만 존재하므로 트리다. (2) A-B-D 간에 순환 경로가 존재하고, A-B-D와 C-E가 연결되지 있지 않으므로 비연결 그래프다. 그러므로 트리가 아니다. 아래 트리(Tree)로 관련..
2020. 8. 24.
[이산수학] 추이폐포와 연결관계
■ 추이폐포(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.
