이산수학

[Discrete Mathematics] 결정 트리(decision tree) 및 최소 시간
·
Mathematics/Discrete Mathematics
결정 트리 어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다. 5개의 동전 문제 5개의 동전 중 하나의 동전만 무게가 다르다면 어떤 동전이 무게가 다르고, 다른 동전보다 무거운지 가벼운지를 알 수 있는 결정 트리이다.최악의 경우 시간을 최악의 경우에 필요한 무게 비교의 수로 정의한다면 최악의 경우 시간은 결정 트리의 높이인 33이다. 만약 최악의 경우에도 22 이하의..
[Discrete Mathematics] 이진 트리(binary tree) 및 트리의 운행(traversal)
·
Mathematics/Discrete Mathematics
이진 트리 이진 트리는 각 정점의 자식의 수가 최대 2개인 트리이다. 이때 자식은 왼쪽 자식 혹은 오른쪽 자식으로 지정된다. 트리 운행 트리의 각 정점을 정확히 한 번씩 방분하는 체계적 방법으로 트리를 운행한다. 순회라고도 한다.이진 트리에서 운행은 전위 운행법(preorder traversal), 중위 운행법(inorder traversal), 후위 운행법(postorder traversal)이 존재한다. 전위, 중위, 후위에서 전, 중, 후는 운행 중 루트의 위치를 말한다. 전위는 루트를 먼저 처리하고, 중위는 중간에, 후위는 마지막에 처리한다. 전위 운행법입력: TT (이진 트리의 루트 혹은 트리가 비어있음을 나타내는 NULL)출력: processprocess 에 따라 종속적preord..
[Discrete Mathematics] 신장 트리(spanning tree) 및 최소 신장 트리(minimal spanning tree)
·
Mathematics/Discrete Mathematics
신장 트리 TT 가 그래프 GG 의 모든 정점을 포함하는 부분 그래프이면서 트리라면 TTGG 의 신장 트리라 한다.일반적으로 그래프는 여러 개의 신장 트리를 가진다.예를 들어 위와 같은 그래프에는 아래와 같은 신장 트리가 있을 수 있다. 주황색 선으로 표시된 것이 신장 트리이다.그래프 GG 가 신장 트리 TT 를 가지고 있다는 것과 GG 가 연결되어 있다는 것은 동치이다. 증명은 다음과 같다.그래프 GG 가 신장 트리 TT 를 가진다 가정하고, a,bVGa,bVG 를 가정하자. 그렇다면 a,bVTa,bVT 이다. TT 가 트리이므로 aa 에서 bb 로의 경로 PP 가 존재하며 따라서 연결되어 있다.반대로 $ G..
[Discrete Mathematics] 트리(tree)와 허프만 코드(Huffman codes)
·
Mathematics/Discrete Mathematics
트리 트리는 v,wVv,wV 에 대해 vv 에서 ww 로의 유일한 단순 경로가 존재하는 그래프를 말한다. 루트 트리(rooted tree)는 특별한 정점이 루트(뿌리)로 지정된 트리이다. 근 트리라고도 한다.어떤 정점 vv 의 레벨(level)은 루트에서 vv 로의 단순 경로의 길이가 되고, 루트 트리의 높이(height)는 최대 레벨 값이 된다.TT 가 루트 v0v0 를 가진 루트 트리이고, x,y,zVx,y,zV 이며 (v0,v1,,vn)(v0,v1,,vn)TT 에서의 단순 경로라 하면 기본적인 용어들은 다음과 같다.부모 (parent): vn1vn1vnvn 의 부모조상 (ancestor): $ ..
[Discrete Mathematics] 그래프 동형사상(isomorphism of graph) 및 위상동형(homeomorphic)
·
Mathematics/Discrete Mathematics
그래프 동형사상 어떤 두 그래프가 겉보기에는 완전히 다른 그래프처럼 보이지만, 구조만 때어놓고 본다면 같은 구조를 가진 그래프일 수 있다. 아래 그래프를 보면 정점과 간선의 이름, 생김새가 다르게 보인다.그러나 재배열 한다면 비슷한 그래프처럼 보인다.이처럼 구조가 같은 그래프를 동형이라 한다. 좀더 명확하게는 다음과 같이 정의힌다.그래프 G1=(V1,E1)G1=(V1,E1) 과 그래프 G2=(V2,E2)G2=(V2,E2) 가 동형(isomorphic)이라 할 때 다음 조건을 만족하는 함수 쌍 ffgg 가 존재하고, 이를 동형사상(혹은 동형함수)이라 한다.f:V1V2f:V1V2g:E1E2g:E1E2 는 전단사 함수이다. 즉 ffV1V1 의 모든 정..
[DIscrete Mathematics] 다익스트라 알고리즘(Dijkstra algorithm)
·
Mathematics/Discrete Mathematics
최단 경로 문제 (Shortest Path Problem) 가중치 그래프는 간선에 값을 부여한 그래프이다. 이때 경로의 길이는 경로 안의 간선의 가중치 합으로 정의하고, 간선 (i,j)(i,j) 의 가중치를 w(i,j)w(i,j) 라 표기한다.가중치 그래프가 있을 때 2개의 정점 간 가장 길이가 짧은 경로를 찾는 최단 경로 문제는 내비게이션, 통신망 등 여러 분야에서 활용된다. 다익스트라 알고리즘 다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 최단 경로를 구하는 알고리즘이다. nn 개의 정점으로 구성되고, 단순하며, 연결된 가중치 그래프에 대하여 최악의 경우 Θ(n2)Θ(n2) 의 시간복잡도를 가진다.이 알고리즘은 가중치 그래프의 어느 한 정점에서 다른 정점으로의 최..
[Discrete Mathematics] 오일러 사이클(Euler cycle) 및 해밀턴 사이클(Hamiltonian cycle)
·
Mathematics/Discrete Mathematics
오일러 사이클 그래프 안의 모든 정점과 모든 간선을 포함하는 사이클을 오일러 사이클이라 한다. 쾨니히스베르크 다리 문제가 대표적인 오일러 사이클을 확인하는 문제이다.어떤 그래프 GG 가 오일러 사이클을 가진다면, GG 는 연결 그래프이고, 각 정점의 차수는 짝수여야 한다. 이를 증명하기 위해 GG 가 오일러 사이클을 가진다 가정하자. vvwwGG 의 정점이면 vv 에서 ww 까지 취한 오일러 사이클의 일부는 vv 에서 ww 까지의 경로이고, 따라서 GG 는 연결 그래프이다. 어떤 간선으로 vv 에 도착하면 다른 간선을 따라 반드시 떠나야 하기 때문에, 또한 vv 에 연결된 모든 간선이 반드시 사용되어야 하기 때문에 vv..
[Discrete Mathematics] 그래프(graph)의 기본 개념과 그래프 구분
·
Mathematics/Discrete Mathematics
그래프 그래프는 정점(vertex)과 간선(edge)로 이루어져 있는데, 각 정점들을 연결하는 것이 간선이다. 특정 정점에서 다른 정점으로 이동하는것을 경로(path)라 한다.그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 나눌 수 있는데, 무방향 그래프는 정점의 집합 VV 와 간선의 집합 EE 로 구성되어 있고, 각 간선 eEeE 는 순서가 없는 정점의 쌍으로 나타낸다. 일반적으로 그냥 그래프라 말하면 무방향 그래프를 말한다. 방향 그래프 역시 정점의 집합 VV 와 간선의 집합 EE 로 구성되어 있는데, 각 간선 eEeE 는 순서가 있는 정점의 쌍으로 나타낸다. 통합적으로 그래프 GG 는 $ G = ..
[Discrete Mathematics] 점화 관계(recurrence relation)와 알고리즘 분석에 대한 응용
·
Mathematics/Discrete Mathematics
점화 관계 점화 관계는 수열을 선행 항으로 표현한다. 점화식이라고도 한다.수열 a0,a1,a0,a1, 에 대한 점화 관계는 anan 과 그 앞의 항들인 특정 a0,a1,,an1a0,a1,,an1 과의 관계를 나타내는 식이다. 이 수열 a0,a1,a0,a1, 에 대한 초기 조건은 명시적으로 유한 개의 수열 항에 주어진 값들이다.예를 들어 피보나치 수열을 점화 관계로 나타낸다면, fn=fn1+fn2fn=fn1+fn2 (n3)(n3) 이고, 초기 조건은 f1=1,f2=1f1=1,f2=1 이다.이러한 점화 관계는 재귀적 알고리즘 및 수학적 귀납법과 관련되어 있다.예를 들어 피보나치 수열의 재귀적 알고리즘을 구현한다면 다음과 같고, 이를 수학..
[Discrete Mathematics] 비둘기집 원리(pigeonhole principle)
·
Mathematics/Discrete Mathematics
비둘기집 원리 kk 개의 비둘기집에 nn 마리의 비둘기가 들어갈 때 kk n +1 ,, n ,.,. n n ,.,. f X Y , | X | > | Y | , x_1,..
애스터로이드