CHAPTER 6 그래프

6. 그래프(Graph) 그래프의 개요 Koenigsberg(퀘닉스버그) 다리 문제를 해결하기 위해 Euler(오일러)가 처음 사용-7개의 다리를 한번씩만 지나서 원래 위치로 되돌아오는 방법 최단거리, 연구계획 분석, 전기회로 분석 등 Kneiphof A B C D c e g f a b d c d a b f g e A B C D

6.1 그래프의 정의 그래프 G는 공집합이 아닌 정점(Vertex)들의 유한집합과 공집합도 허용되는 간선(Edge)들의 유한집합으로 구성 G = ( V, E ) V(G) : 공집합이 아닌 정점(vertex)들의 유한집합 E(G) : 간선(edge)들의 집합 1) 방향그래프(digraph, directed graph) 각 간선은 방향성을 가진 정점들의 쌍으로 표현 간선의 표기 <v1, v2> v1 : tail, v2 : head 2) 무방향그래프 정점의 쌍에 순서는 의미가 없다. (undirected graph)에서의 간선의 표기 (v1, v2)

6.1 그래프의 정의(계속) V(G1) = { 1, 2, 3, 4} E(G1) = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)} V(G2) = { 1, 2, 3, 4, 5, 6, 7} E(G2) = {(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)} V(G3) = {1, 2, 3} E(G3) = {<1,2>, <2,1>, <2,3>} 1 2 3 G3 1 2 3 4 5 6 7 G2 2 3 4 G1 1

그래프의 용어 인접(adjacent) 부속,교차(incident) 경로(path) 단순 경로(simple path) 간선(v1, v2)가 E(G)에 있는 간선이면, v1과 v2는 인접한 것이다. 부속,교차(incident) v1과 v2가 인접하였을때 간선 (v1, v2)는 정점 v1과 v2에 부속된 것이다. 경로(path) 임의 정점에서 다른 정점에 이르는 길 단순 경로(simple path) 한 경로상에 있는 모든 정점들이 서로 다른 경로 사이클(cycle) 처음과 마지막 정점이 같은 단순경로 (A→B→C→A) 연결(connected) 무방향그래프 G에서 정점 v1에서 부터 v2에 이르는 경로가 존재하면 v1과 v2는 연결되었다.

그래프의 용어(계속) 연결그래프(connected graph) 단절그래프(disconnected graph) 임의의 vi, vj 에 대해 경로가 있음 단절그래프(disconnected graph) 연결요소(connected component) 최대 연결 서브그래프(Maximal Connected Subgraph) 트리(tree) : 사이클이 없는 연결 그래프 강력연결 그래프(strongly connected graph) 방향그래프 G에서 V(G)에 속한 상이한 두 정점 vi, vj 의 모든 쌍에 대하여 vi에서 vj로, 또한 vj에서 vi로 방향 경로가 존재하는 그래프 2 3 4 1 6 7 8 5 1 2 3

그래프의 용어(계속) 차수 진입차수(in-degree) 진출차수(out-degree) 다중그래프(multi-graph) 정점에 부속된 간선들의 수 진입차수(in-degree) 방향그래프 G에서 임의 정점 v가 머리(head)가 되는 간선들의 수 진출차수(out-degree) 방향그래프 G에서 임의 정점 v가 꼬리(tail)가 되는 간선들의 수 다중그래프(multi-graph) 두 정점 사이에 두개 이상의 간선이 존재하는 그래프 완전그래프(complete graph) n개의 정점으로 구성된 무방향 그래프에서 간선 수가 최대인 그래프 최대 간선수 : n(n - 1)/2 1 2 3 4 1 2 3 4

그래프의 용어(계속) 부그래프(subgraph) 방향 비사이클 그래프(DAG : directed acyclic graph) V(G’) V(G)이고, E(G’) E(G)인 그래프 G’를 그래프 G의 부그래프 방향 비사이클 그래프(DAG : directed acyclic graph) 사이클이 없는 방향 그래프 1 2 3 4

6.2 그래프 표현법 인접행렬 2차원 배열을 만들어서 간선이 존재하는 부분을 '1'로 저장하여 그래프를 표현하는 방법 정점 수만큼의 행과 열로 구성된 정방 행렬 무방향그래프에서 정점 i의 차수는 그 행의 합이다. 방향그래프에서 정점 i의 진출차수는 그 열의 합 집입차수는 그 행의 합 A B C A B C D A B C A B C D

6.2 그래프의 표현 인접리스트 그래프의 각 정점에 대해 한 개의 연결 리스트가 존재. 정점이 n개이고 간선이 e개이면, n개의 'head node'와 (2 * e)개의 리스트 노드가 필요. 진출차수(out-degree) : 인접리스트의 노드의 수 진입차수(in-degree) : 역인접리스트의 노드의 수

6.2 그래프의 표현 역인접리스트 : 방향그래프에서 각 정점에 대해 그 정점으로 들어오는 연결선과 인접한 정점들로 구성된 리스트 리스트 노드구조로 변환

6.2 그래프의 표현 인접 다중리스트 여러 리스트들이 노드 공유 무방향 인접리스트 표현에서 간선(vi, vj)는 2개의 항으로 표현 vi와 vj에 대한 리스트 M : 간선 조사 여부에 대한 마크 필드

6.3 그래프 연산 (1) 그래프 탐색/순회 ① 깊이 우선 탐색 ( Depth First Search ) 알고리즘

6.3 그래프 연산 DFS 인접리스트에서의 DFS => V0, V1, V3, V7, V4, V5, V2, V6, 깊이 우선 탐색의 실행결과 깊이 우선 스패닝 트리(Spanning Tree)가 만들어진다.

6.3 그래프 연산 DFS

6.3 그래프 연산 (1) 그래프 탐색/순회 ② 너비우선 탐색 ( Breadth First Search ) 알고리즘

6.3 그래프 연산 BFS 인접리스트에서의 BFS => V0, V1, V2, V3, V4, V5, V6, V7 너비 우선 탐색의 실행결과 너비 우선 스패닝 트리(Spanning Tree)가 만들어진다.

6.3 그래프 연산 BFS

그래프 용어 스패닝 트리(Spanning Tree) : 그래프 G의 간선들로만 구성되고 G의 모든 정점들을 포함한 트리 Articulation Point : 그래프 G의 정점들 중에서 그 정점을 부속된 간선들과 같이 삭제하면 최소한 두 개의 연결 컴포넌트를 갖는 그래프 G'를 생성하는 정점 v 다음 그래프에서 1과 3이 articulation point 이다 Articulation point를 갖지 않는 연결 그래프를 biconnected graph라고 한다.

6.4 최소 스패닝 트리(Minimum Spanning Tree) 모든 정점들을 사이클없이 최소한의 연결선으로 구성된 그래프 T에 있는 간선들과 G의 모든 정점들로 구성된 트리 T : 탐색중에 순회된 간선들의 집합 B : 나머지 간선들의 집합 T에 있는 간선들은 G의 모든 정점을 포함하는 트리를 형성 Spanning tree

6.4 최소 스패닝 트리(Minimum Spanning Tree) Minimum Cost Spanning Tree 가중치가 부여된 그래프에서 최소비용(혹은 최대이익)을 나타낼 수 있도록 구성된 신장트리 Kruskal 알고리즘 E = edge집합 MST = {    } while( ((n-1)개 edge가 포함) && (Edge집합 != NULL) ) ⅰ) 최저비용 edge (u, v) 선택, Edge집합에서 (u, v)제거 ⅱ) if( (u, v)가 기존 MST에 cycle을 형성하지 않음 )       then (u, v)을 MST에 추가       then (u, v)을 버림 if(MST가 (n-1)개 edge를 포함하지 않음)   then "No Spanning Tree"

6.4 최소 스패닝 트리(Minimum Spanning Tree) Kruskal 알고리즘으로 최소 스패닝 트리를 구현

6.4 최소 스패닝 트리(Minimum Spanning Tree) 2) Prim 알고리즘 G=(V, E) A : set of chosen edges S : subset of nodes which are in the connected component 알고리즘 1. (u, v) : shortest edge    A={(u, v)}    S={u, v} 2. while |S|<|V| do    1) (x, y) 선택      ⅰ) x∈S      ⅱ) y∈V-S      ⅲ) shortest edge && (ⅰ), (ⅱ)만족    2) A=A∪{(x, y)}      S=S∪{y}

6.4 최소 스패닝 트리(Minimum Spanning Tree) Prim알고리즘으로 최소 스패닝 트리를 구현

6.5 최단경로(Shortest Path) (1) 하나의 출발점으로부터의 최단 경로 정점 v0 에서 정점 v1 에 도달하는 가장 짧은 경로는? (v0 v2 v3 v1)=45 인접행렬

6.5 최단경로(Shortest Path) 최단 경로 알고리즘 G=(V, E) C(Vi , Vj ) : edge cost from Vi to Vj d(Vi ) : the cost of the shortest path from V0 to Vi S={V0 }  /* 최단 경로에 포함된 vertex */ d(V0 ) = 0 for[each v ∈ v - {V0 }] do d(v)=c(V0, v ) while S≠V do   choose a vertex w∈V-S ∃ d(w) is a minimum;   S=S∪{w}   for each v∈V-S do d(v)=min{d(v), d(w)+c(w, v)}

6.5 최단경로(Shortest Path) (2) 모든 쌍의 최단 경로 정점 i에서 정점 j로의 최단 경로를 구하는 알고리즘 Find the shortest path from node i to node j Give G=(V, E) : a graph that has no cycle with negative edge cost (G may have a cycle with positive edge cost) Cij : the edge cost from node i to node j Aij : the path cost from node i to node j Aij k : the cost of a shortest path from to           where the path only uses {1, 2, …, k} as intermediate nodes  Aij k = Cij Aij k = min{Aij k-1 , Aik k-1 + Akj k-1 }, for k=1, 2, …, n

6.5 최단경로(Shortest Path) (2) 모든 쌍의 최단 경로 정점 i에서 정점 j로 가는 최단 경로를 구하는 과정

6.6 작업 네트워트(Activity Network) AOV(Activity On Vertex) 네트워크 정점이 작업을 나타내고 간선이 작업사이의 선행관계를 나타내는 방향그래프

6.6 작업 네트워트(Activity Network) AOE(Activity On Edge) 네트워크 간선은 수행되어야 할 작업과 시간을 나타내고, 정점은 작업의 완료를 알리는 사건을 나타내고, 각 사건은 그에게 들어오는 모든 작업이 완료될때 일어난다. 임계경로(Critical Path) : AOE 네트워크로부터 프로젝트를 완료하는데 걸리는 시간, 즉 시작에서 종료까지의 최장거리

6.6 작업 네트워트(Activity Network) 임계경로(Critical path) 작업 공정 그래프의 경우 한 작업의 공정이 다른 작업에 직접적인 영향을 주게 될 때, 주로 작업에 직접적으로 영향을 주는 경로 작업을 완료하는 최소시간인 가장 긴 경로 v5까지 임계경로 : v1 v2 v5 v8까지 임계경로 : v1 v2 v5 v8 v9까지 임계경로 : v1 v2 v5 v7 v9 혹은 v1 v2 v5 v8 v9 v1 v2 v4 v3 v6 v8 v9 v7 v5 a1=6 a4=1 a7=9 a10=2 a2=4 a5=1 a3=5 a6=2 a9=4 a11=4 a8=7 <작업공정에 대한 AOE network 에 대한 임계경로>

임계작업(critical path) 구하는 방법 Earlist time : 사건 vi 가 일어날 가장 이른 시간 v0 에서 vi 까지 최장 거리 모든 ai 에 대하여 earlist time 구함 latest time: 작업 a 에 대하여 프로젝트의 완료를 지연시키지 않고 가장 늦게 작업을 시작할 수 있는 시간 earlist time = latest time 이면 임계작업