그래프에 대해서 정리를 하려고하는데
그래프 이론이 되는 위상 수학에 대해 잘 모르기도 하고
일단 생각 나는데로 정리하고자 한다.
1. 그래프 graph (자료 구조에서의 그래프)
- 노드 node(or 정점, 꼭지점 vertex)과 에지 edge로 구성된 자료 구조
- 노드 node / 정점 vertex : 하나의 지점
- 에지 edge / 간선 : 두 노드/정점 사이를 이어주는 경로
=> 그래프 G = (V, E)로 표기
2. 그래프 이론
* 그래프 이론에 대한 역사적인 배경은 이후에 설명하고 일단 그래프에 관한 전반적인 내용들을 설명한다.
2.1 Wikipedia에서 말하는 그래프 이론
- 정점(에지)과 간선(노드)로 이루어진 수학적 구조 그래프에 대한 연구 이론
- 그래프 관련 주요 용어 : 경로, 순환, 부분 그래프, 연결 그래프
- 그래프 종류 : 순환 그래프, 완전 그래프, 트리 등
- 그래프 이론의 연구 분야 : 대수적 그래프 이론, 위상 그래프 이론, 기하 그래프 이론, 확률 그래프 이론, 알고리즘 그래프 이론
* 알고리즘 그래프 이론 : 그래프를 이용해 알고리즘 문제를 해결하고, 계산 복잡도를 다루는 분야
알고리즘 그래프 이론 문제 예시 : 해밀턴 경로, 클릭, 그래프 색칠
2.2 AIStudy에서 설명하는 그래프의 예시
ref : www.aistudy.com/math/graph_johnsonbaugh.htm
- 아래의 그림은 와이오밍 주의 고속도로 시스템이며, 모든 도로를 가장 경제적으로 순찰하는 방법을 찾아야 한다. 하지만 순찰하는 방법에 대해서 생략하고, 우선 아래의 그림은 그래프로 표현, 모델링 할수 있는데 어떻게 나타내는지 한번 살펴보자 살펴보자.
- 위의 그림에서보면 각 도시들과 도시들을 이어주는 도로들을 볼 수 있다. 각각의 도시를 노드(정점)로 보고, 두 도시를 연결하는 도로를 에지(간선)이라고 하자. 그러면 위 그림의 그래프 G = (V, E)는 아래와 같이 그릴 수 있다. 각 노드의 이름은 이름의 앞 세글자로 하고, 에지들은 $e_{1}$, . . ., $e_{13}$과 같은 식으로 정리하였다.
- 아래의 그래프도 모양은 다르지만 위의 그래프와 동일한 그래프라고 볼 수 있다.
2.3 AIStudy에서 설명해주는 그래프 정리
- 우리는 그래프를 다음과 같이 표기한다. : G = (V, E)
- 하나의 간선 e는 간선 집합 E의 원소로 다음과 같이 표기한다 : e $\in$ E
- 하나의 간선 e는 두 노드 v, w를 연결하므로 e = (v, w) 혹은 e = (w, v)로 표기한다.
* 무방향 그래프 undirected graph의 경우 노드의 순서가 상관없으나, 유방향 그래프의 경우 노드 순서를 지켜야한다.
* 그래프 G가 유방향 그래프이고, e = (v, w) 라면, 노드 v에서 노드 w를 가리키는 간선이 된다.
2.4 와이오밍 주 고속도로의 간선과 정점 정리
- 아래의 와이오밍 주 고속도로 그래프 시스템은 무방향 그래프
- 노드에 대한 집합 V = {Gre, She, Wor, Buf, Gil, Sho, Cas, Dou, Lan, Mud}
- 에지에 대한 집합 E = {$e_{1}$, $e_{2}$, . . ., $e_{13}$}
- 간선 예시 1 : 간선 $e_{1}$ = (Gre, She) = (She, Gre)
- 간선 예시 2 : 간선 $e_{10}$ = (Cas, Dou) = (Dou, Cas)
2.5 방향 그래프와 무방향 그래프 비교
- 에지/간선이 화살표 직선인 경우 방향 그래프
- 에지/간선이 그냥 직선인 경우 무방향 그래프
2.6 그래프 이론에서의 경로 path와 사이클 cycle
- 경로 Path : 하나의 정점에서 다른 정점으로 가는 길.
* example : 정점 A에서 정점 D로 가는 경로 A -> C -> D
- 사이클 Cyle : 한 정점에서 자기 자신으로 돌아갈 수 있는 경로. 사이클이 없는 경우 트리가 된다.
* example : 정점 A의 사이클 : A -> C-> B -> A
2.7 그래프와 토폴로지 Topology
- 일반적인 토폴로지(위키백과) : 위상 수학을 가리킨다.
- 네트워크 토폴로지(위키백과) : 컴퓨터 네트워크 구성을 말한다.
- 그래프에서의 토폴로지(고어쿤님의 블로그) : 그래프가 이루는 전체적인 모양
ref : blog.gorekun.com/?p=1518
* 토폴로지의 예시
- 위 토폴로지들은 모두 기본적으로 네트워크 구조로 사용 되고 있다.
- 성형 토폴로지 star topology : 중앙 허브가 모든 장치와 연결하는 대표적인 네트워크 연결 형태
ref : topologynetwork.com/what-is-star-topology-definition-examples-advantages-disadvantages/
- Bus topology : 네트워크 이외에도 CPU와 메모리, 그외 입출력 장치 데이터, 명령 전송에 사용된다.
- tree topology : 컴퓨터 과학에서 탐색, 정렬 문제 등에 많이 사용하는 자료 구조
위상 수학에 대한 참고 영상
3.그래프의 예시
3.1. 네트워크 토폴로지
3.2. 트리 구조
- 사이클이 존재하지않는 그래프를 트리라고 부른다.
3.3. 신경망 neural network
- 계산 그래프로 만들어진 인공 신경망도 그래프
Quiz. 컴퓨터 과학에서 다루는 트리가 아니라 (조금 더 큰범위의)그래프 이론의 트리는 방향 그래프인가? 무방향 그래프일까?
-----------------------정답선 -------------------------------------
ref : en.wikipedia.org/wiki/Tree_%28graph_theory%29
정답 : 그래프 이론에서 말하는 일반적인 트리는 무방향/무향 그래프이다.
컴퓨터 과학에서 다루는 트리는 루트가 있는 루트 트리 rooted tree
4. 그래프를 어떻게 저장하는가?
- 아래의 그림은 방향 그래프 directed graph의 노드와 에지를 저장하는 방법을 보여주고 있다.
- 인접 리스트 adjacency list와 adjacency maxtrix를 이용하는 방법이 존재.
5. 그래프를 가지고 뭘 할수있는고?
- 그래프를 이용하여 다양한 경로 탐색 문제들을 풀수 있다
-> 경로 탐색 방법으로 퍼즐을 풀거나 목적지까지 가장 빠른 경로를 찾을 수 있다.
5.1 8 퍼즐 문제
- 아래와 같이 초기 상태와 목표 상태가 주어질때,
* 아래의 목표 상태는 잘못 그려짐. 1, 2, 3, 4, 5, 6, 7, 8 순서대로 퍼즐이 맞춰지는게 목표.
- 다양한 탐색 방법으로 (트리이기도 하지만) 비용을 비교해서 원하는 노드를 찾아나갈 수 있다.
* 아래의 그림은 astar 알고리즘으로 목표 상태까지 최단 경로를 찾은 결과.
- 다른 링크에서 구한거지만 위 방법으로 퍼즐을 찾은 결과
5.2 최단 경로를 찾아보자
5.2.1 다양한 그래프 탐색방법들
- 맹목적 탐색 : 목표 노드와 상관없이 무작위로 탐색해나가는 방법으로 계산비용이 크며 소모적임.
- 경험적 탐색 : 목표 노드와 관한 정보, 경험적 정보를 활용한 탐색
| 임의 경로 탐색 | 최적 경로 탐색 | |
| 맹목적 탐색 blind search | 깊이 우선 탐색 Depth First Search 너비 우선 탐색 Breadth First Search |
균일 비용 탐색 Uniform Cost Search |
| 경험적 탐색 heuristic search | 언덕 오르기 탐색 hill Climbing Search 최적 우선 탐색 |
다익스트라 알고리즘 Dijkstra algorithm A* 알고리즘 Astar Algorithm |
- 아래의 그림은 다익스트라 알고리즘으로 한 그래프의 노드 a에서 노드 b까지 최단 경로를 찾는 과정
5.2 휴리스틱 탐색 방법을 이용한 경로 계획
- 이러한 경로 탐색, 계획 방법들을 이용해서 로봇을 스스로 이동시키는데 사용된다.
ref : github.com/AtsushiSakai/PythonRobotics
- 아래는 다익스트라 알고리즘을 이용한 경로 계획 예시
- 아래는 Astar 알고리즘을 이용한 경로 계획 예시
- 아래는 로봇 시뮬레이션 환경에서 경로 탐색 알고리즘을 통한 자율 주행 예시
- 그 외에도 그래프 최적화가 자율 주행, SLAM 연구에서 필요한 2/3차원 점구름 지도를 작성하는데 사용되기도 한다. (KITTI dataset ORB SLAM 적용 영상)
ref : www.youtube.com/watch?v=sLjsnQrmtVM
'수학 > 알고리즘' 카테고리의 다른 글
| 퀵 정렬 quick sort (0) | 2021.04.07 |
|---|---|
| 그래프 정리 2 (0) | 2021.02.24 |
| [리트코드 문제 풀기] 연결 리스트 (0) | 2021.01.27 |
| [리트코드 문제 풀기] 배열 (0) | 2021.01.20 |
| 알고리즘설계기법 - 7. 근사해법 (0) | 2020.08.09 |