그래프

Oak_Cassia·2021년 11월 25일

Descrete Mathematics

목록 보기

6/9

그래프

G=(V,E)는 유한한 개수의 정점(vertex) 또는 노드들의 집합인 V와 연결선(edge)이라고 불리는 정점들의 쌍들의 집합인 E로 이루어진다.
방향 그래프(directed graph, digraph)
정점 v에서 w로 가는 아크는 v -> w 로 표시한다
v를 w의 선행자predecessor라 하며w를 v의 후속자successor라 한다.
방향이 없는 그래프 undirected graph
(head -> tail)

단순 그래프 simple graph
한 쌍의 정점 사이에 많아도 하나의 연결선으로 이뤄진 통상 다루는 그래프로서 자기 자신으로의 연결선이 없는 그래프 이다.

멀티 그래프 multigraph
단순 그래프의 확장으로서 한쌍의 꼭지점사이에 연결선의 개수 제한이 없는 그래프

부분 그래프 subgraph
두개의 그래프 G=(V,E) G'=(V',E') 에서 V'⊆V, E'⊆E 일 때 G'을 G의 부분 그래프라고 한다.

서브 그래프의 정점과 간선은 원래 그래프의 부분 집합

연결선 edge
그래프에서 순서화된 쌍 E, (u,v)∈E일 때 u와 v를 연결하는 연결선 e는 u와 v에 부속됐다(incident)하고 u와 v를 서로 인접했다(adjacent)라 한다.

v의 차수 degree
d(v)는 v에 인접하는 연결선들의 개수
각 정점의 차수들의 합은 연결선 개수의 2배
방향 그래프에서는 In-Dgree, out-Dgree를 구분한다

경로 path

꼭지점의 열 $v_1, v_2, ... , v_n$ 에서 ( $v_{k-1}, v_k \in E$ ), 1≤k≤n 인 경우를 말하며 경로의 길이는 n-1이다.
그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것 $V_i$ 에서 $V_j$ 까지 간선으로 연결된 정점을 순서대로 나열한 리스트를 경로라 한다.

path length
경로를 구성하는 간선 수

단순 경로 simple path
경로가 같은 연결선을 두 번 포함하지 않는 경로를 말한다.

elemetary path 어떤 정점들도 두번 만나지 않는 경로를 말한다

사이클 cycle, 순회 circuit

경로 $(v_1, v_2, ... , v_n)$ 에서 종점 $v_n$ 과 시점 $v_1$ 이 일치하는 경우

단순 사이클 simple cycle
같은 연결선을 반복하여 방문하지 않는 사이클

기본 사이클 elementary cycle
시작점을 제외한 어느 정점도 반복하여 방문하지 않는 사이클

연결 그래프 connected graph
그래프의 모든 정점들이 연결된 그래프

강한 연결 그래프 strongly connected graph
모든 두 정점 a와 b에 대해서 a->b 와 b->a 경로들이 존재하는 그래프. 방향 그래프에서 의미를 가진다.

연결요소 connectivity component
그래프에서 모든 정점들이 연결되어 있는 부분을 말하며 연결수(connectivity number)란 그래프 G에서 연결 요소의 개수를 말한다.

인접행렬(adjacency matrix): 그래프 G=(V,E) 에서 |V|=n일 때 G의 인접 행렬은 n*n 행렬 A로 나타낸다. 이때 A의 각 원소 $a_{ij}$ 는 정점간의 연결이 있을 때 1 없으면 0

인접리스트 adjacency list
각 정점에 포인터가 주어지고 그점으로부터 연결된 정점들을 차례로 연결 리스트로 표시한 것 같은 리스트 내에서는 순서에 관계 없다.

오일러 경로(eulerian path)
그래프에서 각 연결선을 한 번씩 통과하는 경로
연결그래프이며 홀수 차수의 개수가 0또는 2여야 한다.

오일러 순회(Eulerian circuit)
그래프에서 꼭지점은 여러 번 지날 수 있지만 각 연결선은 한 번씩만 통과하는 순회
모든 정점이 짝수의 차수를 가져야 한다.

한붓그리기(traversable)
시작점과 끝점을 제외한 정점은 짝수여야 한다.

해밀턴 경로 Hamiltonian path
그래프에서 모든 꼭지점을 한번씩 지나지만 시작점으로 돌아오지 않는 경로

해밀턴 순회 Hamilton circuit
모든 꼭지점을 한 번씩 지나는 순회

가중 그래프 weight graph
그래프 G의 각 연결선에 0보다 큰 수가 할당 되었을 때 이 값을 가중값이라 한다.

동형 그래프 isomorphic graph
$G_1=(V_1, E_1)$ 과 $G_2=(V_2, E_2)$ 가 주어졌을 때 전단사 함수 $f:V_1 → V_2$ 가 존재하여 $\{u, v\} \in E_1 ↔ \{f(u),f(v)\} \in E_2$ 이면 f를 동형이라 하고 $G_1, G_2$ 를 동형 그래프라 한다.

평면 그래프(planar graph)
평면상에서 어떤 연결선도 서로 교차할 수 없도록 그려진 하나의 그래프
평면 그래프의 정점 수를 v, 연결선 수를 e, 면의 수를 f라 할때
v-e+f=2 이때 f는 그래프 바깥의 평면도 포함한다.

완전 그래프 complete graph
G=(V,E)의 모든 정점들의 쌍 사이에 연결선이 존재.
Kn (n은 정점 수)

정규 그래프 regular graph
그래프의 모든 꼭지점의 차수가 k일 때 k차 정규 그래프라고 한다.

이분 그래프 bipartite graph
G가 두 부분집합 X,Y= V-X 로 나누어져 연결선이 X내의 정점과 Y내의 정점의 쌍으로 연결되면 G를 이분 그래프라고 한다.

완전 이분 그래프 complete bipartite graph
X내의 정점들과 Y내의 정점들 사이에 연결선이 모두 존재하는 그래프

방향 비사이클 그래프 DAG Directed Acyclic Graph
사이클이 없는 방향 그래프이다.
공통 인수를 가진 산술적 표현의 구조를 나타내는 데 유용하다.

coloring problem
G에 대해 인접한 영역이 서로 다른 색이 되도록 각 저점에 색을 칠하는 문제
chromatic number
G를 칠하는데 필요한 최소의 색의 수 x(G)
쌍대 그래프
두 그래프가 동형이 될 때

그래프 G에서 다음은 서로 동치
두가지 색으로 칠할 수 있다.
이분 그래프이다.
모든 순환은 짝수의 길이를 가진다.

four coloring problem
모든 평면글래프는 네 가지 색으로 색칠 가능하다.

최단경로 문제, 다익스트라, 순회 판매원(최근접 이웃 근삿값), DFS, BFS 자료구조랑 겹쳐서 나중에 어디에 넣을지 고민

DFS

depth first search.
스택을 사용한다.

시작 정점 v를 결정하여 방문한다.
정점 v에 인접하 정점 중에서
A. 방문하지 않은 정점 w가 있으면 v를 push하고 w방문. w를 v로 하여 2 반복
B. 방문하지 않은 정점이 없으면 스택을 pop하여 가장 마지막에 방문한 정점을 v로 설정하여 2 반복
스택이 공백이 될 때 까지 반복

BFS

breadth first search.
큐를 사용

시작 정점 v를 결정해 방문한다.
정점 v에 인접한 정점 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enqueue한다.
방문하지 않은 정점이 없다면 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 dequeue하여 받은 정점을 v로 설정하고 2를 반복한다. 큐가 공백이 될 때까지 2~3을 반복한다.

Spanning Tree

모든 정점이 n개인 무방향 그래프 G에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프.
간선을 최소로 하여 모든 정점을 방문한다.
그래프에서 순회를 하면 n-1개의 간선을 이동하면서 n개의 모든 정점을 방문하게 되므로 순회경로는 신장 트리가 된다.
Depth First Spanning Tree: 깊이 우선 탐색을 이용하여 생성된 신장 트리
Breadth First Spanning Tree: 너비 우선 탐색을 이용하여 생성된 신장 트리
Minimum cost spanning tree: 가중치 합이 최소인 신장 트리

Prim's algorithm

주어진 가중 그래프 G=(V,E)에서 V={1,2, ... , n}

노드의 집합 U를 1로 시작
u $\in$ U, v $\in$ V-U일 때
U와 'V-U'를 연결하는 가장 짧은 (u, v)를 찾아서 v를 u에 포함. 이때 (u, v)는 사이클을 형성하지 않아야 한다.
2의 과정을 U=V 까지 반복

Kruskal algorithm 1

그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.
가중치가 가장 높은 간선을 제거한다. 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 그 다음으로 가중치가 높은 간선을 제거한다.
그래프G에 간선이 n-1개만 남을 때 까지 2를 반복한다.
그래프 G의 간선이 n-1개일 때 Minimum cost spanning tree 가 된다.

Kruskal Algorithm2

모든 간선을 가중치에 따라 오름차순으로 정리한다.
그래프G에 가중치가 가장 낮은 간선을 삽입한다. 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음으로 가중치가 낮은 간선을 삽입한다.
그래프G에 간선이 n-1개 삽입될 때까지 2를 반복한다.
그래프G에 간선이 n-1개 삽입되면 최소 비용 신장 트리가 완성된다. MCST

Shortest Path

신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로.
최단 경로를 구하려는 가중치 그래프의 가중치는 ‘가중치 인접 행렬(Weight Adjacent Matrix)’에 저장한다. 2차원 배여. 두 정점 사이 간선이 없으면 $\infty$ , 대각선 값0

Dijkstra Shortest Path Algorithm

one to all shortest path 알고리즘 중 가장 많이 사용된다.

경로 길이를 저장할 배열 distance 준비: 시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 $\infty$ 로 초기화한다.
시작 정점의 distance를 0으로 초기화 하고 집합 S에 추가한다.
집합 S에 속하지 않은 정점들 중에서 distance가 최소인 정점 u를 찾아 집합 s에 추가한다. 새로운 정점 u가 추가되면, u에 인접하고 집합 s에 포함되지 않은 정점 w의 distance 값을 다음 식에 따라 수정한다. 집합 S에 모든 정점이 추가될 때까지 3을 반복한다.
distance[w]=min(distance[w],distance[u]+weight+[u][w])

Floyd Shortest Path Algorithm: all to all shortest path

A^k[v][w]는 0부터 k까지의 정점만을 이용한 정점 v에서 w까지의 최단 경로를 의미한다.
정점 0부터 정점 k-1까지의 정점을 고려한 최단 거리 $A^{k-1}$ 을 구한 상태에서 다음 정점 k를 고려할 때 $A^{k-1}[v][w]$ 와 $A^{k}[v][k]+ A^{k}[k][w]$ 중에서 작은 값에 따라 최단 경로가 수정된다.
$A^k[v][w]=min(A^{k-1}[v][w], A^{k}[v][k]+ A^{k}[k][w])$
$A^-1 -> A^0 -> A^1$ -> … 순으로 정점을 늘려 가면서 최단경로를 구하다가 최종적으로 $A^{n-1}$ 을 구하면 n 개의 모든 정점 사이의 최단 경로를 구하게 된다.
$A^{-1}$ 은 초기 상태로서 가중치 인접 행렬인 배열 weight 값이 되고, $A^{n-1}[v][w]$ 는 정점 0부터 정점 n-1까지의 모든 정점을 이용한 최단 경로가 된다.