그래프의 용어 알고리즘 수업자료 2001242021 김정현.

Presentation on theme: "그래프의 용어 알고리즘 수업자료 2001242021 김정현."— Presentation transcript:

1 그래프의 용어 알고리즘 수업자료 김정현

2 개요 그래프의 정의 그래프의 용어 그래프의 종류 그래프의 표현방법

3 그래프의 정의 각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조 Tree는 사이클이 없는 Graph이다
그래프에서 노드는 "vertex", 링크는 "edge"라 한다. 하나의 그래프는 다음과 같이 vertex와 edge의 집합으로 정의할 수 있다. => G = (V,E) (V는 vertex집합 , E는 edge집합) 유한개의 정점과 유한개의 간선 집합(간선은 공집합이 가능)

4 그래프의 용어(1) 인접(Adjacent) 교차(Incident) 경로(Path) 경로 길이(Path Length)
단순 경로(Simple Path) 기본 경로(Basic Path) 인접 정점의 순서쌍(V1, V2)가 E(G)에 있는 연결선이면, 정점 V1과 V2는 인접되어 있다고 하며 그림의 G1에서 정점 B에 인접한 정점들은 A, C, D이다. G3에서 B는 C로 인접하지만 C는 B로 인접하지 않다. 교차 정점의 순서쌍(V1, V2)가 E(G)에 있는 연결선이면, 연결선 (V1, V2)는 정점 V1과 V2에 교차되었다고 한다. 그림의 G1에서 연결선(A, B), (A, C), (A, D)는 정점 A에 교차되어있는 연결선이다. 경로(Path) 임의의 정점에서 다른 정점에 이르는 길 경로 길이(Path Length) 경로상에 있는 간선들의 수 단순경로(Simple Path) 경로상에 있는 정점들 중에서 첫 번째와 마지막 정점을 제외하고 모든 정점들이 서 로  다를 때를 말한다. 그림의 G2에서 정점 A에서 E로의 경로 ABE는 단순 경로이 지만, ABEBE는 단순 경로가 아니다. 기본 경로(Basic Path) 한 경로상에 있는 모든 정점이 유일할 때의 경로, 즉 같은 정점을 두 번 이상 지나지 않는 경로

5 그래프의 용어(2) 연결(Connected) 연결요소(Connected Component) 사이클(Cycle) Loop
차수(Degree) 진입차수(Indegree) 진출차수(Outdegree) 연결(Connected) 무방향 그래프에서 임의의 두 정점  Vi와  Vj사이에 경로가 존재하면 Vi와  Vj는 연결되었다고 하며, 그림의 G1에서 정점 A와 D는 연결되어 있다라고 할 수 있다 연결요소(Connected Component) 그래프 G에서 최대 연결 부프로그램을 연결 요소라고 한다. 사이클(Cycle) 처음 정점과 마지막 정점이 같은 단순 경로를 말한다. 그림의 G1에서 경로((AB), (BD), (DC))를 (ABDC) 또는 ABDC와 같이 표현하며, 이 경로를 단순 경로라고 한다. ABCDA는 단순 경로로써 사이클이다. Loop 한 정점에서 그 자신에 이어지는 간선 차수 그래프 G(V,E)에서 한 정점에 교차된 연결선들의 수를 말한다. 그림의 G1에서 정점 B에 교차된 연결선의 수는 3이므로 정점 B의 차수는 3이다. 진입차수 방향성 그래프에서 한 정점에서 들어오는 연결선의 수, 즉 한 정점을 머리(head)로 하는 연결선의 수를 정점 V의 진입 차수라고 하며, 그림의 G3에서 정점 B의 진입차수는 1이다. 진출차수 방향성 그래프에서 한 정점에서 나가는 연결선의 수, 즉 한 정점을 꼬리(tail)로 하는 연결선의 수를 정점 V의 진출 차수라고 하며, 그림의 G3에서 정점 B의 진출차수는 2이다. 차수(Degree) 무방향 그래프 : 한 정점에 연결된 간 선의 수 방향 그래프 진입 차수(Indegree) : 한 정점에 도착하 는 방향 간선의 수 진출 차수(Outdegree) : 한 정점에서 출 발하는 방향 간선의 수 차수(Degree) = 진입 차수 + 진출 차수

6 그래프의 종류(1) 무향그래프 E={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)} 유향그래프 E={<A,B>, <B,D>, <D,C>,<C,A>} 무향 그래프(undirected graph) edge에 방향성이 없어서 연결된 vertex들의 순서가 정해지지 않은 그래프를 말한다. 무향 그래프의 edge는 vertex쌍을 괄호로 묶어 표현한다. (예) E={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)} 무향 그래프는 실선으로 edge를 표현한다. 유향 그래프(directed graph) edge에 방향성이 있어서 연결된 vertex들의 순서가 정해진 그래프를 말한다. 유향 그래프의 edge는 vertex쌍을 각괄호로 묶어 표현한다. 유향 그래프는 화살표로 edge의 방향을 표시한다.

7 그래프의 종류(2) 연결그래프(Connected Graph) G1과 G2 개별은 연결그래프
다중그래프(Multi Graph, Multiple Graph) 두 정점사이에 간선이 2개이상인 경우 연결그래프(Connected Graph) 그래프 G에 속하는 모든 정점들이 연결되어 있어서 임의의 두 정점 Vi와  Vj에 대하여 경로가 존재하는 그래프를 말한다. 그림의 그래프들은 연결 그래프이며, 바로 밑 그림에서 G1부분 정점과 G2부분의 정점들이 연결되어 있지 않기 때문에 연결 그래프가  아닌 단절 그래프(disconnected graph)이다. 다중그래프(Multi Graph, Multiple Graph) 그래프 G의 임의의 두 정점 사이에 두 개 이상의 연결선이 존재하는 그래프를 말한다. 밑 그림의 정점 C와 D사이에 3개의 연결선이 존재하므로 그래프 G는 다중 그래프이다

8 그래프의 종류(3) 완전 그래프의 edge수 =n(n-1) /2 n은 vertex수
강력연결그래프(Strongly Connected Graph) 유방향그래프에서 모든 Edge연결 완전그래프(complete Graph) 무방향그래프에서 모든 Edge연결 완전 그래프의 edge수 =n(n-1) /2 n은 vertex수 강력연결그래프(Strongly Connected Graph) 방향 그래프 G에서 V(G)에 속한 상이한 두 정점 Vi,  Vj의 모든 쌍에 대해  Vi →  Vj  또는 Vj→Vi로 경로가 존재하는 그래프를 말한다. 강력 연결 요소(Strongly Connected Component) 방향 그래프에서 두 정점 사이의 간선이 양방향으로 서로 강력하게 연결되어 있는 요소, 즉 두 정점 사이에 방향 사이클이 이루어지는 요소 완전 그래프(complete Graph) 모든 vertex쌍을 연결하는 edge가 존재하는 그래프를 말한다. 완전 그래프는 같은 수의 vertex를 가지는 그래프들 중에서 가장 많은 edge를 가진다. 꼭짓점 차수의 특성 어떤 그래프에 있는 모든 꼭짓점 차수의 합은 이 그래프가 가진 변의 수의 두 배가 된다. 따라서, 꼭짓점 차수의 합은 짝수가 되면, 차수가 홀수인 꼭짓점의 수도 짝수가 된다는 성질을 가진다 정점이 n개일 때 정점 2개의 조합 nC2 = = n! / 2! * (n - 2)! = n * (n - 1) / 2 완전 그래프의 edge수 = n(n-1) /2 , n = vertex수

9 그래프의 종류(4) 모든 정점의 차수가 같은 그래프를 말한다. 아래 그림에서 A와 B에서 모든 정점의 차수가 2로서 동일하다.
정규 그래프 (Regular Graph) 모든 정점의 차수가 같은 그래프 부분그래프(Sub Graph) 어떤 그래프의 부분집합이 되는 그래프 정규 그래프 (Regular Graph) 모든 정점의 차수가 같은 그래프를 말한다. 아래 그림에서 A와 B에서 모든 정점의 차수가 2로서 동일하다. 부분그래프(SubGraph) G(V,E)에서 V의 부분 집합을 V', E의 부분 집합을 E라고 할 때, G'(V',E')를 G(V,E)의 부분 그래프라고 한다. 동형 그래프(Isomorphic Graph) 두 개의 그래프 간 정점, 차수, 간선의 수가 동일한 그래프이다. (그림 A와 B) 동형 그래프(Isomorphic Graph) 두개의 그래프 간 정점,차수, 간선의 수가 동일한 그래프

10 그래프의 표현방법(1) 인접행렬(Adjacency Matrix) 인접 리스트(Adjacency List)
역인접 리스트(Inverse Adjacency List) 인접 다중 리스트(Adjacency Muti-List)

11 그래프의 표현방법(2) 인접행렬(Adjacency Matrix) 인접행렬의 문제점 기억공간의 낭비
정점 집합 V(G)={ V1, V2…  Vn}인 그래프 G=(V(G),E(G))의 인접 행렬(adjacency matrix)은 그래프를 구성하는 각 정점들 간의 인접 여부를 n×n의 2차원 배열로 표현한 것이다. 2차원 배열 A(i, j)에서 연결선 (Vi,  Vj)가 E(G)에 속하면 A(i, j)=1이 되고, E(G)에 속하지 않으면 A(i, j)=0 이 된다. 인접행렬의 문제점 인접 행렬로는 n(n-1)개의 edge를 표현할 수 있다. 그러나 실제로 그래프내의 edge수는 이보다 훨씬 적기 때문에 대부분의 행렬원소는 0의 값을 가진다. 따라서 완전 그래프처럼 edge가 많은 경우를 제외하고는 상당량의 기억장소가 낭비되는 문제가 있다. 이러한 문제를 해결하기 위해 인접 리스트를 사용한다 인접행렬의 문제점 기억공간의 낭비

12 그래프의 표현방법(3) 인접 리스트(Adjacency List) 인접 리스트(Adjacency List)
인접 리스트는 연결 리스트(linked list)를 사용하여 그래프의 구조를 표현하는 방법으로 그래프의 각 정점에 인접한 정점들을 각각 한 노드에 보관하여 한 개의 연결 리스트를 구성하여 각 리스트에 대한 포인터를 1차원 배열로 저장한 구조이다. 이와 같은 인접 리스트는 밑의 그림에서 보여 주는 것과 같이 순차적인 표현이나 연결 리스트 표현으로 나타낼 수 있다. 여기에서 순차적으로 표현된 각 인접 리스트의 길이는 degree 열에 주어져 있고, 인접 리스트 표(adjacency list table)에 있는 degree 열은 그림에서 각 정점의 진출 차수가  된다. 장점 인접 리스트는 연결된 vertex들만 리스트로 관리하기 때문에 인접 행렬을 사용하는 경우처럼 비연결 vertex를 표현하기 위해 기억장소를 낭비하지 않는다. 단점 인접 리스트는 하나의 연결을 표시하기 위해 vertex 정보뿐 아니라 링크 정보까지 사용되므로 edge의 수가 상대적으로 많은 경우 인접행렬을 사용할 때보다 기억장소 낭비가 심해질 수있다.