Mathematics

직교행렬 $ n $ 차 정사각행렬 $ A $ 에 대하여 $ A^T A = I_n $ 이면 $ A $ 를 직교행렬이라 한다. 또한 이는 $ A^T = A^{-1} $ 이면 $ A $ 는 직교행렬이다와 동치이고, $ A $ 의 열(행)벡터들은 정규직교집합이다와 동치이다.$ A $ 의 열(행)벡터들이 정규직교집합인 이유는 $ A^T A = I = A A^T $ 이기 때문이다.$ A $ 가 직교행렬이면 $ A^T A = I $ 이고, $ | A | = | A^T | $ 이므로 $ 1 = | I | = | A^T A | = | A^T | | A | = | A | ^2 $ 이므로 $ | A | = \pm 1 $ 이다. 즉 $ A $ 가 직교행렬이면 $ | A | = 1 $ 또는 $ -1 $ 이다. 직교 대각화 정사..

행렬 대각화 정사각행렬 $ A $ 와 어떤 가역행렬 $ P $ 에 대하여 $ P^{-1}AP $ 가 대각행렬이 된다면 $ A $ 를 대각화 가능한 행렬(diagonalizalble matrix)이라 하고, $ P $ 는 $ A $ 를 대각화하는 행렬이라 한다.만약 $ A $ 가 대각행렬이라면 $ P $ 를  $ I $ 로 둠으로써 대각화 가능하다.이러한 대각화가 가능할 필요충분조건은 $ n $ 차 정사각행렬 $ A $ 가 $ n $ 개의 일차독립인 고유벡터를 갖는 것이다. 이때 $ A $ 는 고윳값 $ \lambda_1, \lambda_2, \cdots, \lambda_n $ 을 주대각성분으로 갖는 대각행렬 $ D $ 와 닮은 행렬이다.더보기$ A $ 개 대각화 가능한 $ n $ 차 정사각행렬이라할 때 ..

결정 트리 어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다. 5개의 동전 문제 5개의 동전 중 하나의 동전만 무게가 다르다면 어떤 동전이 무게가 다르고, 다른 동전보다 무거운지 가벼운지를 알 수 있는 결정 트리이다.최악의 경우 시간을 최악의 경우에 필요한 무게 비교의 수로 정의한다면 최악의 경우 시간은 결정 트리의 높이인 $ 3 $이다. 만약 최악의 경우에도 $ 2 $ 이하의..

이진 트리 이진 트리는 각 정점의 자식의 수가 최대 2개인 트리이다. 이때 자식은 왼쪽 자식 혹은 오른쪽 자식으로 지정된다. 트리 운행 트리의 각 정점을 정확히 한 번씩 방분하는 체계적 방법으로 트리를 운행한다. 순회라고도 한다.이진 트리에서 운행은 전위 운행법(preorder traversal), 중위 운행법(inorder traversal), 후위 운행법(postorder traversal)이 존재한다. 전위, 중위, 후위에서 전, 중, 후는 운행 중 루트의 위치를 말한다. 전위는 루트를 먼저 처리하고, 중위는 중간에, 후위는 마지막에 처리한다. 전위 운행법입력: $ T $ (이진 트리의 루트 혹은 트리가 비어있음을 나타내는 NULL)출력: $ \text{process} $ 에 따라 종속적preord..

신장 트리 $ T $ 가 그래프 $ G $ 의 모든 정점을 포함하는 부분 그래프이면서 트리라면 $ T $ 를 $ G $ 의 신장 트리라 한다.일반적으로 그래프는 여러 개의 신장 트리를 가진다.예를 들어 위와 같은 그래프에는 아래와 같은 신장 트리가 있을 수 있다. 주황색 선으로 표시된 것이 신장 트리이다.그래프 $ G$ 가 신장 트리 $ T $ 를 가지고 있다는 것과 $ G $ 가 연결되어 있다는 것은 동치이다. 증명은 다음과 같다.그래프 $ G $ 가 신장 트리 $ T $ 를 가진다 가정하고, $ a, b \in V_G $ 를 가정하자. 그렇다면 $ a, b \in V_T $ 이다. $ T $ 가 트리이므로 $ a $ 에서 $ b $ 로의 경로 $ P $ 가 존재하며 따라서 연결되어 있다.반대로 $ G..

고윳값과 고유벡터 $ n $ 차 정사각행렬 $ A $ 와 $ \mathbf{x} \in \mathbb{R}^n $ 및 $ \lambda \in \mathbb{R} $ 에 대해 다음이 성립하면 $ \lambda $ 를 $ A $ 의 고윳값이라 하고, $ \mathbf{x} $ 를 $ \lambda $ 에 대응하는 고유벡터라 한다.$$ A \mathbf{x} = \lambda \mathbf{x} $$즉 행렬과의 곱이 실수와의 곱과 동일할 때 고윳값과 고유벡터를 말할 수 있다.$ \mathbf{x} \in \mathbb{R}^n $ 에 대하여 $ I_n \mathbf{x} = 1 \times \mathbf{x} $ 이므로 단위행렬 $ I_n $ 의 고윳값은 $ \lambda = 1$ 뿐이고, 영벡터가 아닌 $..

트리 트리는 $ \forall v, w \in V $ 에 대해 $ v $ 에서 $ w $ 로의 유일한 단순 경로가 존재하는 그래프를 말한다. 루트 트리(rooted tree)는 특별한 정점이 루트(뿌리)로 지정된 트리이다. 근 트리라고도 한다.어떤 정점 $ v $ 의 레벨(level)은 루트에서 $ v $ 로의 단순 경로의 길이가 되고, 루트 트리의 높이(height)는 최대 레벨 값이 된다.$ T $ 가 루트 $ v_0 $ 를 가진 루트 트리이고, $ x, y, z \in V $ 이며 $ (v_0, v_1, \dots, v_n ) $ 을 $ T $ 에서의 단순 경로라 하면 기본적인 용어들은 다음과 같다.부모 (parent): $ v_{n-1} $ 은 $ v_n $ 의 부모조상 (ancestor): $ ..

그래프 동형사상 어떤 두 그래프가 겉보기에는 완전히 다른 그래프처럼 보이지만, 구조만 때어놓고 본다면 같은 구조를 가진 그래프일 수 있다. 아래 그래프를 보면 정점과 간선의 이름, 생김새가 다르게 보인다.그러나 재배열 한다면 비슷한 그래프처럼 보인다.이처럼 구조가 같은 그래프를 동형이라 한다. 좀더 명확하게는 다음과 같이 정의힌다.그래프 $ G_1 = (V_1, E_1) $ 과 그래프 $ G_2 = (V_2, E_2) $ 가 동형(isomorphic)이라 할 때 다음 조건을 만족하는 함수 쌍 $ f $ 와 $ g $ 가 존재하고, 이를 동형사상(혹은 동형함수)이라 한다.$ f: V_1 \to V_2 $ 와 $ g: E_1 \to E_2 $ 는 전단사 함수이다. 즉 $ f $ 는 $ V_1 $ 의 모든 정..

행렬표현 일반적으로 $ n $ 차원 벡터공간 $ V $ 에서 $ m $ 차원 벡터공간 $ W $ 의 선형변환을 행렬변환으로 나타낼 수 있고, 이는 좌표벡터를 통해 확인해볼 수 있다.$ n $ 차원 벡터공간 $ V $ 의 순서 기저를 $ S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \} $ 이라 하고, $ m $ 차원 벡터공간 $ W $ 의 순서 기저를 $ R = \{ \mathbf{y_1}, \mathbf{y_2}, \cdots, \mathbf{y_m} \} $ 이라 하며, $ T: V \to W $ 를 선형변환이라 하자. $ \mathbf{x_i} \in S $ $(i = 1, 2, \cdots, n) $ 에 대하여 $ T(\mathbf{x_i})..

최단 경로 문제 (Shortest Path Problem) 가중치 그래프는 간선에 값을 부여한 그래프이다. 이때 경로의 길이는 경로 안의 간선의 가중치 합으로 정의하고, 간선 $ (i, j) $ 의 가중치를 $ w (i, j) $ 라 표기한다.가중치 그래프가 있을 때 2개의 정점 간 가장 길이가 짧은 경로를 찾는 최단 경로 문제는 내비게이션, 통신망 등 여러 분야에서 활용된다. 다익스트라 알고리즘 다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 최단 경로를 구하는 알고리즘이다. $ n $ 개의 정점으로 구성되고, 단순하며, 연결된 가중치 그래프에 대하여 최악의 경우 $ \mathcal{\Theta} (n^2) $ 의 시간복잡도를 가진다.이 알고리즘은 가중치 그래프의 어느 한 정점에서 다른 정점으로의 최..