Mathematics/Discrete Mathematics

결정 트리 어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다. 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..

트리 트리는 $ \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 $ 의 모든 정..

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

오일러 사이클 그래프 안의 모든 정점과 모든 간선을 포함하는 사이클을 오일러 사이클이라 한다. 쾨니히스베르크 다리 문제가 대표적인 오일러 사이클을 확인하는 문제이다.어떤 그래프 $ G $ 가 오일러 사이클을 가진다면, $ G $ 는 연결 그래프이고, 각 정점의 차수는 짝수여야 한다. 이를 증명하기 위해 $ G $ 가 오일러 사이클을 가진다 가정하자. $ v $ 와 $ w $ 가 $ G $ 의 정점이면 $ v $ 에서 $ w $ 까지 취한 오일러 사이클의 일부는 $ v $ 에서 $ w $ 까지의 경로이고, 따라서 $ G $ 는 연결 그래프이다. 어떤 간선으로 $ v $ 에 도착하면 다른 간선을 따라 반드시 떠나야 하기 때문에, 또한 $ v $ 에 연결된 모든 간선이 반드시 사용되어야 하기 때문에 $ v $..

그래프 그래프는 정점(vertex)과 간선(edge)로 이루어져 있는데, 각 정점들을 연결하는 것이 간선이다. 특정 정점에서 다른 정점으로 이동하는것을 경로(path)라 한다.그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 나눌 수 있는데, 무방향 그래프는 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있고, 각 간선 $ e \in E $ 는 순서가 없는 정점의 쌍으로 나타낸다. 일반적으로 그냥 그래프라 말하면 무방향 그래프를 말한다. 방향 그래프 역시 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있는데, 각 간선 $ e \in E $ 는 순서가 있는 정점의 쌍으로 나타낸다. 통합적으로 그래프 $ G $ 는 $ G = ..

점화 관계 점화 관계는 수열을 선행 항으로 표현한다. 점화식이라고도 한다.수열 $ a_0, a_1, \dots $ 에 대한 점화 관계는 $ a_n $ 과 그 앞의 항들인 특정 $ a_0, a_1, \dots, a_{n-1} $ 과의 관계를 나타내는 식이다. 이 수열 $ a_0, a_1, \dots $ 에 대한 초기 조건은 명시적으로 유한 개의 수열 항에 주어진 값들이다.예를 들어 피보나치 수열을 점화 관계로 나타낸다면, $ f_n = f_{n-1} + f_{n-2} $ $ (n \geq 3) $ 이고, 초기 조건은 $ f_1 = 1, f_2 = 1 $ 이다.이러한 점화 관계는 재귀적 알고리즘 및 수학적 귀납법과 관련되어 있다.예를 들어 피보나치 수열의 재귀적 알고리즘을 구현한다면 다음과 같고, 이를 수학..

비둘기집 원리 $ k $ 개의 비둘기집에 $ n $ 마리의 비둘기가 들어갈 때 $ k 비둘기가 $ n +1 $ 마리, 비둘기 집이 $ n $ 개라 할 때 한 집당 한 마리의 비둘기가 들어가 있다고 가정하면, 이미 모든 집에는 비둘기가 들어가 있는데 한 마리의 비둘기는 들어가지 못했기 때문에 이 비둘기 한 마리를 어느 집에 할당해도 특정 비둘기 집은 두 마리의 비둘기가 들어가게 된다. 즉 $ n $ 개의 비둘기 집이 존재할 때 비둘기가 $ n $ 마리를 초과한다면, 그리고 모든 비둘기가 비둘기 집에 들어간다면 반드시 두 마리 이상이 들어가 있는 비둘기 집이 존재한다. 확장 $ f $ 가 유한 집합 $ X $ 에서 유한 집합 $ Y $ 로의 함수이고, $ | X | > | Y | $ 라 할 때, $ x_1,..