이산수학 – Discrete Mathematics 그래프 이론

오일러 사이클과 해밀턴 사이클의 정의, 구하는 방법 동형 그래프의 정의와 구하는 방법 다익스트라 알고리즘과 와샬의 알고리즘 소개 – 6장. 그래프 이론 그래프의 정의와 용어 그래프의 표현 방법 오일러 사이클과 해밀턴 사이클의 정의, 구하는 방법 동형 그래프의 정의와 구하는 방법 다익스트라 알고리즘과 와샬의 알고리즘 나무의 정의와 성질 www.cspia.net DISCRETE MATHEMATICS

최단경로 가중그래프(weighted graph) 가중치(weight) – 간선 {i, j}에 값 w(i,j)가 부여되는 경우도 있으며 이 값을 {i, j}의 가중치라고 한다. 가중그래프(weighted graph) – 간선에 가중치가 부여된 그래프 그래프의 가중치 – 모든 간선의 가중치 합 경로의 길이(거리) – 경로의 가중치 최단경로(shortest path) – 두 정점 간의 경로의 길이가 최소인 경로 a b c d e f g h 1 2 4 3 6 5 가중치는 비용을 나타내기도 한다. 예를 들어 정점이 도시를, 간선이 건설할 도로를 나타낸다 면 도로의 건설 비용을 간선의 가중치에 나타내 기도 한다. www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 이 알고리즘은 연결된 가중그래프 G=(V, E)의 정점 a에서 다른 모든 정점까지의 최단경로의 길이를 구한다. 간선 {i, j}의 가중치는 w(i, j) > 0 이며 정점 a에서 x까지의 거리를 L(x)에 나타내기로 한다. 수행이 완료되면 L(h)는 a에서 h까지의 최단경로의 길이가 된다. { for(모든 정점 x) L(x)←∞; L(a)←0; T←V; While(T≠Ø) { L(v) 의 값이 최소인 정점 v∈T 를 선택; T←T-{v}; for(v 에 인접한 모든 정점 x∈T) L(x)←min{L(x), L(v)+w(v,x)}; } www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 [1] 시작 정점에서 가장 인접한 정점을 찾는다. 그 정점까지의 거리가 최단거리이다. 지금까 지 최단거리가 알려진 정점은 2개(자기자신과 지금 찾은 정점)가 된다. 최단거리가 알려 진 정점들의 집합을 S라 하자. [2] 집합 S에 포함되지 않은 정점들 중에서 시작 정점으로 부터 가장 가까운 정점을 찾는다. 이 새로운 정점은 집합 S에 바로 이웃한 정점들 중 하나일 것이다. 그 정점까지의 거리는 최단거리이며, 그 정점을 집합 S에 포함시킨다. [3] 새로운 정점이 없을 때까지, 즉 모든 정점이 집합 S에 포함될 때까지 [2]의 과정을 반복 한다. www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 알고리즘 수행 전 각 변수 값들의 초기화 b c d e f g h 1 2 4 3 6 5 알고리즘 수행 전 각 변수 값들의 초기화 - 각 정점까지의 거리(가중치)를 최대값으 로 지정 - 출발 정점(a)의 거리(가중치)를 0으로 지정 - 정점 Set을 검색된 Set와 검색되지 않은 Set으로 나누어 구분 정점 a에 인접한 정점 b, f에 대한 거리 검색 While loop L(b) = min{∞, 0+2} = 2 L(f) = min{∞, 0+1} = 1 a b c d e f g h 1 2 4 3 6 5 www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 정점 a의 인접정점까지의 거리가 구해졌으므로 b c d e f g h 1 2 4 3 6 5 정점 a의 인접정점까지의 거리가 구해졌으므로 검색된 정점 Set으로 이동, 검색되지 않은 정점 Set에서 제거 거리가 구해진 정점 Set중 정점b의 인접 정점에 대해 거리를 검색 b의 인접정점 중 c정점까지의 거리를 구함 L(c) = min{∞, L(b) + 2} = 4 b 2 c 2 4 2 4 1 2 3 a d e h 4 3 3 1 6 1 f 5 g www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 거리가 구해진 정점 Set중 정점b의 인접 정점에 대해 거리를 검색 c d e f g h 1 2 4 3 6 5 거리가 구해진 정점 Set중 정점b의 인접 정점에 대해 거리를 검색 b의 인접정점 중 d정점까지의 거리를 구함 b의 인접정점 중 e정점까지의 거리를 구함 L(d) = min{∞, L(b) + 2} = 4 L(e) = min{∞, L(b) + 4} = 6 거리가 구해진 정점 Set중 정점f의 인접 정점에 f의 인접정점 중 g정점까지의 거리를 구함 L(g) = min{∞, L(f) + 5} = 6 c, d, e, g 정점의 인접 정점에 대해 거리를 검색 a b c d e f g h 1 2 4 3 6 5 www.cspia.net DISCRETE MATHEMATICS

최단경로 다익스트라(Dijkstra)의 최단경로 알고리즘 거리가 구해진 정점 Set중 정점c의 인접 정점에 대해 거리를 검색 b c d e f g h 1 2 4 3 6 5 거리가 구해진 정점 Set중 정점c의 인접 정점에 대해 거리를 검색 c의 인접정점 중 e정점까지의 거리를 구함 c의 인접정점 중 h정점까지의 거리를 구함 L(e) = min{6, L(c) + 2} = 6 L(h) = min{∞, L(c) + 1} = 5 거리가 구해진 정점 Set중 정점g의 인접 정점에 g의 인접정점 중 e정점까지의 거리를 구함 g의 인접정점 중 h정점까지의 거리를 구함 L(e) = min{6, L(g) + 3} = 6 L(h) = min{5, L(g) + 6} = 5 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 방향그래프에서 두 정점쌍 간에 경로가 존재하는지를 알아내는 문제. 방향그래프 G=(V, E)에 대하여 E는 V에서의 관계인 것으로 간주할 수 있다. 이면 정 점 v1에서 v2로 길이가 1인 경로가 존재한다. 이를 확장하면 합성관계 는 길이가 2 인 경로가 존재하는 정점쌍이 된다. 을 로 정의하면 은 경로의 길이가 k인 정점쌍들의 집합이다. 따라서 두 정점쌍간에 경로가 존재하는지는 를 구하면 된다. www.cspia.net DISCRETE MATHEMATICS

경로의 존재 방향그래프에서 두 정점쌍 간에 경로가 존재하는지를 알아내는 문제. 위 식을 계산하려면 E의 모든 거듭제곱을 계산하여야 하는데 이렇게 되면 실용적이지 못하다. G에서 |V|=n이라면 n보다 큰 길이의 경로에는 같은 정점이 반복해서 나타나야 하며, 이는 방향그래프에 사이클이 존재함을 의미한다. 이러한 사이클들은 제거해도 경로의 존재에는 영 향을 주지않으며 사이클들을 제거하는 경우 모든 경로의 길이는 n이하이다. www.cspia.net DISCRETE MATHEMATICS

경로의 존재 방향그래프에서 두 정점쌍 간에 경로가 존재하는지를 알아내는 문제. E에 대한 인접행렬이 A이고 E*에 대한 인접행렬이 A*일 때 A*은 아래의 식으로 계산되며 이 를 G에 대한 도달행렬(reachability matrix)이라고 한다. 여기서 행렬 A에 대한 곱과 합은 각각 불 곱과 불 합 연산이다. www.cspia.net DISCRETE MATHEMATICS

경로의 존재 방향그래프에서 두 정점쌍 간에 경로가 존재하는지를 알아내는 문제. 예제 6.23 아래 방향그래프에 대하여 도달행렬을 구하라.  에서 까지가 해당 방향그래프와 함께 불 연산이 된 행렬을 그려보라. 5 1 2 3 4 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 방향그래프에서 두 정점쌍 간에 경로가 존재하는지를 알아내는 문제. – 와샬의 알고리즘 인 방향그래프에 대하여 관계 를 다음과 같이 정의한다. 에 대하여 일 필요충분조건은 이거나 을 중간 정점으로 하는 u에서 v로의 경로가 존재하는 것이다. 에 대하여 일 필요충분조건은 이거나 의 부분집합을 중간 정점으로 하는 u에서 v로의 경로가 존재하는 것이다. 즉, 는 의 부분집합을 중간정점으로 하여 경로가 존재하는 정점쌍들의 집합 이다. 따라서 의 순으로 계산하면 은 구하고자 하는 도달행렬이다. www.cspia.net DISCRETE MATHEMATICS

경로의 존재 W(k) 을 행렬로 나타내기로 하자. 와샬의 알고리즘 예제 6.24 그림 6-25의 그래프에 대하여 을 W(n)계산하라. W(k) 을 행렬로 나타내기로 하자. W(1) 에는 그림 6-25의 행렬 A에다가 정점 1을 거치는 정점 i에서 j로의 경로가 있으면 i행 j열이 1이 되도록 추가한다. 이 경우에는 그러한 경로가 존재하지 않으므로 W(1) = A이다. 5 1 2 3 4 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 와샬의 알고리즘 예제 6.24 W(2) 는 W(1) 에 {1, 2}의 부분집합을 중간 정점으로 하는 정점 i에서 j로의 경로가 있으면 i행 j열이 1이 되도록 추가하여 구한다. 그러한 것은 1 → 2 → 4 , 3 → 2 → 4 가 있으므로 1행 4열과 3행 4열에 1을 추가한다. 추가하면 다음과 같다. 1 2 3 4 5 1 0 1 0 1 1 2 0 0 0 1 0 W(2) = 3 0 1 0 1 0 4 0 0 1 0 0 5 0 0 0 1 0 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 와샬의 알고리즘 예제 6.24 W(3)을 구하기 위해 정점 1, 2, 3을 중간 정점으로 하는 경로를 구해 보면 1 → 2 → 4 , 3 → 2 → 4, 4 → 3 → 2, 4 → 3 → 2 → 4가 있으며 앞의 둘은 이미 반영이 된것이고 새로운 것은 끝의 둘이다. 따라서 W(3)는 다음과 같다. 1 2 3 4 5 1 0 1 0 1 1 2 0 0 0 1 0 W(3) = 3 0 1 0 1 0 4 0 1 1 1 0 5 0 0 0 1 0 www.cspia.net DISCRETE MATHEMATICS

경로의 존재 와샬의 알고리즘 예제 6.24 W(3)를 구할 때 정점 1, 2, 3을 중간 정점으로 하는 경로중에 새로 추가된 정점이 3이 반드시 중간 정점으로 포함된 경로만이 결과에 영향을 주었다. 따라서 W(4)를 구하기 위해서는 정점 4가 반드시 포함된 정점 1, 2, 3, 4를 중간 정점으로 하는 경로를 찾아내면 충분하다. 그러한 경로는 1 → 2 → 4 → 3, 1 → 2 → 4 → 3 → 2, 2 → 4 → 3, 2 → 4 → 3 → 2, 3 → 2 → 4 → 3, 5 → 4 → 3, 5 → 4 → 3 → 2이다. 이에 해당하는 원소를 1로 추가하면 W(4)는 다음과 같다. 1 2 3 4 5 1 0 1 1 1 1 2 0 1 1 1 0 W(4) = 3 0 1 1 1 0 4 0 1 1 1 0 5 0 1 1 1 0 끝으로 정점 5를 중간정점으로 하여 새로이 만들어지는 경로가 없다. 따라서 W(5) = W(4)이다. www.cspia.net DISCRETE MATHEMATICS

나무 나무 - 정렬, 탐색 문제, 식 계산 순서 표현 등 계층적 표현에서 응용됨 - 자유나무라고도 함 정의 6.4 사이클이 없는 단순연결그래프를 나무(tree)라고 한다. 정리 6.4 단순그래프 T = (V, E)에서 다음 문장들은 모두 동치(특징)이다. 단, n = |V|, e = |E|인 것으로 한다. T는 나무이다. T는 연결되어 있고 e = n - 1 이다. T에 있는 모든 두 정점 사이에는 꼭 하나의 경로만이 존재한다. T는 연결그래프이지만 T에 있는 임의의 간선을 제거하면 비연결 그래프로 된다. T에는 사이클이 없지만 임의의 간선을 추가하면 사이클이 만들어 진다. www.cspia.net DISCRETE MATHEMATICS

나무 예제 6.25 연결그래프 G에 정점은 5개, 간선은 6개가 존재한다. G를 나무로 바꾸려면 몇 개의 간선을 제거해야 하는가 ? 정리 6.4에 의하여 (1) 나무의 간선의 개수는 정점의 개수보다 하나 적다.(e = n - 1 ) (2) G에서 연결이 끊어지지 않도록 하는 간선 2개를 제거하면 된다.(사이클 중에 끊어도 연결이 끊어지지 않는 간선을 선택한다.) www.cspia.net DISCRETE MATHEMATICS

나무 자유나무(free tree), 뿌리나무(rooted tree), 기타 용어 뿌리나무란 나무의 정점 중의 하나가 뿌리(root)로 지정된 나무이다. 뿌리로 지정된 정점 r는 나무의 제일 위쪽에 오며 기타 다른 정점은 r의 밑에 위치한다. 어떤 나무(자유나무)라도 뿌리로 지정된 정점을 꼭대기에 올려놓고 다시 그리면 뿌리나무가 된다. 뿌리는 제일 위에, 나머지 정점들은 뿌리로부터 떨어진 정도에 따라 뿌리 아래쪽에 오 도록 하여 그린다. 뿌리나무에서 뿌리 r로부터 r밑에 있는 임의의 정점 u에 대하여 r로부터 u까지의 경로는 유일 하다. www.cspia.net DISCRETE MATHEMATICS

나무 e 예제 6.26 그림 6-23(a)의 나무에서 정점 d를 뿌리로 한 뿌리나무가 (b)이다. 정점 d에 바로 인접한 정점은 a, c, e, f이므로 이들을 d의 바로 밑에 그린다. 다음 b와 g는 d로부터 경로의 길이가 2이고 e의 인접 정점이므로 e의 밑에 둔다. 마지막으로 h는 d로부터 경로의 길이가 3이고 g에 인접해 있으므로 g의 아래에 두면 그림 6-32(b)가 완성된다. (a) (b) 그림 6-23 e www.cspia.net DISCRETE MATHEMATICS

나무 용어 자손(desendant) – 정점 u와의 경로가 있으면서 그 아래쪽에 있는 모든 정점은 u의 자손 자식(child) – u의 바로 아래에 있는 정점 v를 u의 자식, 이때 u는 v의 부모(parent)가 된다. 동기(sibling) – 부모가 같은 정점 조상(ancestor) – 정점 u에서 뿌리까지의 상향 경로에 존재하는 정점들을 u의 조상 부분나무(subtree) – u의 자손에 부수된 간선으로 이루어지는 부분그래프를 u가 뿌리인 부분나무 잎(leaf) – 자식이 없는 정점 내부정점 – 잎이 아닌 정점 깊이(depth) – 뿌리나무의 어떤 정점 u에 대하여 뿌리에서 u까지의 경로의 길이를 u의 수준 (level) 또는 깊이(depth)라고 한다. 높이(height) – 뿌리나무에서 가장 긴 경로의 길이를 그 뿌리나무의 수준 또는 높이(height) 뿌리나무에서는 정점의 차수가 자식의 개수로 정의된다. www.cspia.net DISCRETE MATHEMATICS

나무 예제 6.27 그림 6-23(b)에서 d의 자식은 a, c, f, e이고 a, c, f, e는 서로 동기이다. 정점 g의 부모는 e이고 g의 조상은 d와 e이다. e의 자손은 b, g, h이다. 그리고 e를 뿌리로 하는 부분나무는 정점 e, b, g, h로 이루어진다. a, c, f, b, h는 잎이다. h의 수준 또는 깊이는 3이고 이것이 가장 큰 잎의 정점이므로 이 뿌리나무의 높이 또는 수준은 3이다. 뿌리 d의 차수는 4이고 , 정점 e의 차수는 2, g의 차수는 1이다.. 모든 잎의 차수는 0이다. www.cspia.net DISCRETE MATHEMATICS

나무 기타 용어 순서나무(ordered tree) – 자식의 나열 순서 역시 중요한 뿌리나무, 순서나무에서는 동일한 값의 자식이라도 첫 번째 온 경우와 맨 끝에 온 경우와는 다르다. k진나무(k-ary tree) – 순서나무의 모든 정점의 차수가 최대 k일 때. 전k진나무(full k-ary tree) – 모든 내부정점의 차수가 k인 순서나무 이진나무 : 모든 정점의 최대 차수가 2인 나무 이진나무에서 각 내부정점은 왼쪽 자식과 오른쪽 자식을 가질 수 있다. 또한 어떤 정점의 왼쪽 자식을 뿌리로 하는 부분나무를 왼쪽 부분나무, 오른쪽 자 식을 뿌리로 하는 부분나무를 오른쪽 부분나무라고 한다. 균형적 나무 : 높이가 h인 k진나무에서 모든 잎의 깊이가 h이거나 h-1이면 그 나무는 균형적이라고 한다. www.cspia.net DISCRETE MATHEMATICS

나무 예제 6.28 다음 중 순서나무를 분류해보라 www.cspia.net DISCRETE MATHEMATICS

나무 전k진나무에 대한 내부정점과 잎과의 관계 정리 6.5 전k진나무의 정점의 개수가 n, 내부정점의 개수가 i, 잎의 개수가 l 이라고 하면 다음이 성립 한다. n=ki+1 l=n-I 예제 6.29 잎이 11개인 전3진나무의 내부정점의 개수는 ? 따라서 내부 정점은 5개이다. www.cspia.net DISCRETE MATHEMATICS