이산수학 6. 그래프 - swkim0128/PARA GitHub Wiki
그래프는 정점(Vertex)의 집합과 선(Edge)들의 집합으로 구성되며 G = {V, E}로 표시한다
임의의 연결선 e=(u,v)에 대해서 정점(Vertex) u와 v는 서로 인접(adjacent) 했다고 하며, e는 정점 u와 정점 v에 **접합(incident)**했다고 말한다
연결선의 두 끝점이 같은 정점(Vertex)이면 이 연결선(Edge)을 **루프(loop)**라고 한다
두 정점의 연결선(Edge)이 두개 이상일때 다중 연결선이라고 한다
-
단순 그래프(simple graph)
루프나 다중 연결선이 없는 그래프
-
차수(degree)
정점u에 접합된 연결선(Edge)의 수
- eg(u)와 같이 표기하기도 한다
자기 자신을 연결하는 연결선(loop)의 경우 차수를 2로 본다
그래프에서 모든 정점의 차수의 합은 모든 연결선 수의 2배이다
두 정점 u와 v사이에 연결선이 존재하면 두 정점은 **연결(connected)**되었다고 한다
-
길이(length): 두 정점의 경로를 구성하는 연결선의 수
-
거리(distance): 두 정점 간의 최단 경로의 길이
-
닫힌 경로(closed path)
시작점과 끝점이 같은 경로
시작점에서 끝점으로 향할시 다시 시작점으로 돌아오는 경로
-
순환(사이클 cycle)
3개 이상의 연결선을 갖는 경로에서 어떤 연결선도 중복되지 않는 닫힌 경로
-
부분 그래프(subgraph)
-
그래프 G={V, E}가 있을때 V'⊆V이고, E'⊆E인 그래프 G'={V', E'}를 G의 부분그래프라고 한다
-
-
동형 그래프(isomorphic graph)
그래프 G = {V, E}와 G' = {V', E'} 에 대하여, 다음 조건을 만족하는 함수가 1:1관계의 함수이면 두 그래프 G와 G'는 동현 그래프라고 한다 함수 f: v→ v' (v∈V, v'∈V') (x,y) ∈ E ↔ (f(x), f(y)) ∈ E' 그리고 이 관계가 성립하는 함수 f를 동형(isomorphic)이라고 한다
-
완전 그래프(complete graph)
그래프 G={V, E}가 모든 정점 사이에 연결선이 존재하면 G는 완전 그래프라고 한다
-
이분 그래프(bipartite graph)
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프
-
정규 그래프 (regular graph)
그래프 G={V, E}의 모든 정점의 차수가 같으면, G를 정규 그래프라고 한다.
차수가 4인 정규그래프
-
평면 그래프(planar graph)
그래프 G=(V, E)의 연결선들이 서로 교차하지 않고 평면상에 그릴수 있는 그래프G를 평면그래프라고 한다
-
비평면 그래프
평면그래프와 반대로 교차하지 않고는 그릴수 없는 그래프
-
면(face)
연결선에 따라 구분된 영역을 면이라고 한다
-
방향그래프 (directed graph)
그래프 G={V,E}에서 연결선의 두 정점이 순서쌍일때 G를 방향 그래프라고 한다
인접하고 있는 정점들을 서로 다른 색을 갖도록 하면서 그래프의 모든 정점에 색을 당
-
색상수
그래프 채색에 필요한 최소한의 색의 수
x(G)로 표시한다 (ex. 4개 필요한 경우 x(G)=4)
-
완전 그래프에서의 색상수
x(k5) =5 (정점이 5개인 완전그래프)
x(kn)=n
-
이분 그래프에서의 색상수
x(k(3,3)) =2
-
Simple Coloring Algorithm - 모든 정점들의 순서를 정한뒤, 그래프 채색의 조건을 만족하는 색상중에서 가장 낮은 번호의 색장을 선택하여 정점에 배정한다 - 문제점: 그래프에 색상을 정하는 순서에 따라 답이 달라짐
-
Greedy Algorithm
- 결정을 할 때마다 최종 결과에 관계없이 그 순간에서 최선의 선택을 한다.
- 하지만 최종의 결과 또한 최적이라는 보장이 없음
이산수학 그래프4: 최소신장 트리(minimum spanning tree)
- 그래프 G = {V, E} 에서 V의 모든 정점을 포함하면서 **순환(cycle)이 존재하지 않는 부분 그래프(subgraph)**를 신장 트리라고 한다
-
최소 신장 트리 ( Minimum Spanning Tree,MST)
- 가중 그래프에서 가중치의 합을 최소로 하는 신장 트리
- 알고리즘 종류: Prim, Kruskal
-
프림 알고리즘
- MST알고리즘 중 하나로 선택한 정점들에서 갈 수 있는 에지 중에서 가장 낮은 가중치를 가진 에지를 선택하여 아직 선택하지 못한 정점을 포함 하도록 하여 MST를 구하는 알고리즘
- 그리디 알고리즘이지만 최종적으로 최적의 해를 찾아줌
- 시간 복잡도
- O(V*logE)
-
크루스칼 알고리즘
- MST알고리즘 중 하나로 에지들을 오름차순으로 정렬하여 가장 작은 가중치부터 고르는 알고리즘
- 단, 사이클이 생기지 않게 하기 위하여 Union-Find알고리즘을 이용함
- 프림과 동일하게 그리디알고리즘이지만 최종적으로 최적의 해를 찾아줌
- 시간 복잡도
- O(E*logE)
- One → One : MST알고리즘
- One → all : 다익스트라, 벨만포드
- all → all : 플루이드워샬
-
한 정점에서 다른 모든 정점으로의 최단경로를 찾는 알고리즘
-
방향그래프, 비방향그래프 모두 적용 가능
-
가중치값이 음수가 아니어야함
-
방법
- (출발 정점의 가중치를 0, 갈수 없는 곳의 가중치를 무한대로 둠)
- 출발 정점을 우선순위 큐에 넣음
- 큐에서 정점 하나를 꺼내 해당 정점에서 갈 수 있는 정점들을 확인하고 가중치를 업데이트하여 우선순위 큐에 넣음 (큐에서 꺼낸 정점이 이미 도달한 정점의 경우 넘김)
- 큐가 빌때까지 2번 반복
- 한 정점에서 다른 모든 정점으로의 최단경로를 찾는 알고리즘
- 방향그래프, 비방향그래프 모두 적용 가능
- 가중치값이 음수일 때도 적용 가능
- 사이클이 존재하면 안됨
- 방법
- 출발점을 가중치 0, 나머지를 가중치 무한대로 둠 (D[1]=0, D[i]= 무한대 for all i ∈ {2,3,..,n})
- for all i ∈ {2,3,...n} D[i] = min (D[k] + d(ki)) for i 와 직접 연결선이 있는 k
- 2번을 D[i]의 변화가 더 이상 발생하지 않을때까지 반복한다