이산수학 - 그래프, 트레일, 경로, 이분 그래프, 완전 이분 그래프, 정규 그래프, 오일러 투어, 해밀턴 경로
1. 기본사항 다음 그림처럼 점과 두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라 한다. 2. 주요 용어 그래프 \( G \)는 꼭지점(vertex)들과 변(edge)들로 구성된다. 이를 수식으로 나타내면 \( G = (V, E) \)이다. 여기서 \( V = \{ v | v \text{는 꼭지점} \} \)이고, \( E = \{ e | e \text{는 변} \} \)이다.변은 두 꼭지점을 연결한다. 즉, 변에 의해 발생(incident)된다고 한다.연결된 두 꼭지점은 서로 인접(adjacent)한다고 한다.병렬 변(parallel edge)은 두 꼭지점을 연결하는 변이 복수개 있을 때를 의미한다.루프(loop)는 동일한 꼭지점을 연결하는 변을 뜻한다.고립된 꼭지점(isolated ..
2024. 5. 15.
이산수학 - 함수, 함수의 상등, 전사함수, 단사함수, 합성함수, 계승함수, 바닥함수, 천장함수, 나머지 함수
1. 기본사항 집합 \(X\)와 \(Y\)가 주어졌을 때, \(X\)에서 \(Y\)로의 함수 \(f\)는 다음 조건을 만족하는 관계이다.모든 \(x \in X\)에 대해, 오직 하나의 \(y \in Y\)가 존재하여 \((x, y) \in f\)를 만족한다. 이를 수식으로 표현하면 다음과 같다.\[ \forall x \in X, \exists ! y \in Y \quad \text{such that} \quad (x, y) \in f \]즉, \(X\)의 임의의 원소 \(x\)에 대해, \((x, y) \in f\)를 만족하는 \(y\)가 \(Y\)에 오직 하나만 존재한다.이를 함수 \(f\)로 표현하면 다음과 같이 쓸 수 있다.\[ f : X \to Y \]그리고, \(f(x) = y\)라는 관계를 만..
2024. 5. 15.
이산수학 - 관계, 관계의 표현, 관계의 성질, 관계의 종류, 반사적, 대칭적, 추이적, 동치관계
1. 기본사항관계란 객체들 간의 연관성을 포현하는 구조이다. 이산수학에서 관계는 주로 두 집합에 속하는 서로 다른 두 원소 사이의 연관성을 표현하는 데 사용된다. 두 집합 X와 Y에 대하여 곱집합 X x Y의 부분집합 R을 X에서 Y로의 관계라고 말한다. 집합 \(A\)와 \(B\)의 곱집합(Cartesian Product) \(A \times B\)는 \(A\)의 원소와 \(B\)의 원소의 모든 순서쌍(ordered pair)들의 집합을 의미합니다. 즉,\[ A \times B = \{ (a, b) \mid a \in A, b \in B \} \] 집합 \( X \)에서 집합 \( Y \)로의 (이항)관계 \( R \)은 \( X \times Y \)의 부분집합이다.- 이항관계 \( R \)에 대..
2024. 5. 15.
이산수학 - 행렬: 행렬의 연산, 종류, 정방행렬, 단위행렬, 역대칭행렬, 삼각행렬, 역행렬, 부울행렬
1. 기본 사항 행렬은 행과 열로 구성되는 사각형 형태로 수를 배열한 것 \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8 \\9 & 0 & 2 & 5 \\\end{bmatrix} - 컴퓨터 분야의 활용프로그래밍 언어 자료구조 컴퓨터 그래픽스패턴인식 로봇동작 인공지능행렬 m과 n이 양의 정수일 때, m개의 행과 n개의 열로 구성된 직사각형의 수 배열 A를 \( m \times n \) 행렬이라 한다.행렬 \( A \)에서 i번째 행의 j번째 열의 수를 행렬 \( A \)의 \((i,j)\) 원소라 하며, \( a_{ij} \)로 표시한다. 행렬 \( A \)를 간단히 \( A = [a_{ij}] \)로 표기하기도 한다.- 행 벡터(row vector): \( 1 \ti..
2024. 5. 15.
이산수학 - 집합, 집합 연산, 합집합, 교집합, 차집합, 대칭차집합, 대수 법칙
1. 기본사항 집합론에서 집합과 원소는 무정의용어이다. 무정의용어란 정의 없이 사용하는 용어를 가리키며, 직관적으로 이해할 수 있고 지금까지 알려진 다른 용어로 정의하기 힘든 대상을 표현하기 위해 사용된다. S가 집합이라고 할 때, a를 S의 원소이고, b가 S의 원소가 아니라면 다음과 같이 표기한다. a ∈ S, b ∉ S 다음의 항목들이 집합인지 아닌지 판별해보자. 1) { a, b, c} 2) a 3) {{a}, b} 4) { a, b, a, c} 2)는 집합 표시가 없으므로 집합이 아니다. 4는 원소 a가 중복되므로 집합이 아니다. 집합을 서술하기 위해서는 원소나열법과 조건제시법을 사용한다. 1) 원소나열법: S = {1, 2, 3}2) 조건나열법: S = {x | 0 ≤ x 집합의..
2024. 5. 13.
