[이산수학] 그래프의 종류와 오일러/해밀턴 경로
1. 그래프소개 2. 부분그래프 3. 연결그래프 4. 이동경로 5. 최단경로찾기 --------------------------------------------------------------------------------- ① 그래프 모델링 : 주어진 문제를 그래프로 표현하여 해결 (정점과 정점을 잇는 간선으로 표현) 주요 구성 요소 - 정점(꼭짓점) - 간선(모서리) G = (V,E) V = {1,2,3,4,5,6} E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} // 집합으로 나타내면 '연결'이 되어 있음. // 순서쌍으로 연결되어 있으면 '방향' 그래프로 표현 가능 다중 간선 : 두 정점을 연결하는 간선의 수가 두 개 이상인 경우 (루프 : 자기에..
2020. 5. 6.
[이산수학] 관계의 정의와 성질
다른 집합과의 관계 1. 이항 관계 : A에서 B로의 이항관계 R ⊆ AxB R = {(a,b) | a∈A, b∈B} (a,b) ∈ R iff aRb - A와 B 순서에 주의 - 순서쌍 집합, 그림, 테이블 등으로 표현 ★★함수와 관계의 차이점★★ // 하지만 국가와 도시 간의 "수도"에서는 관계보다 함수가 더 적절하게 쓰인다. 국가-수도 관계는 하나씩 매핑되기 때문에 함수로 매핑하자. // 대학의 사립, 국립 유형에서도 1대1로 매핑되기 때문에 함수로 표현하는 게 더 적절하다. 2. 삼항 관계 : A, B, C로의 관계 R ⊆ AxBxC R = {(a,b,c) | a∈A, b∈B, c∈C} 3. 다항 관계 : A1, ... , An로의 관계 "n-tuple"이라고 부름. RDB(Relational Da..
2020. 5. 6.
