Overview
Graph Theory는 쾨니히스베르크의 다리 문제가 불가능한 문제임을 증명하는 것으로 시작되어 현재 다양한 알고리즘과 인공지능 모델로 발전하고 있다.
Graph
Graph는 여러 개의 Vertex(또는 Node)와 이를 연결하는 Edge로 구성된 자료구조이다.
- Vertex(정점): 하나의 개체(관측치)를 나타내는 점을 의미한다. ex) $u,v$
- Edge(간선): 두 정점을 연결하는 선을 의미한다. ex) $uv$
- 하나의 edge와 연결된 두 vertices를 endpoints라고 한다. ex) $uv$의 endpoints는 $u$와 $v$
- 그림
Compound
Graph $G$는 다음으로 구성된다.
- 정점의 집합: $V(G)$ ; $u, v \in V(G)$
- 간선의 집합: $E(G)$ ; $uv \in E(G)$
- 간선과 정점 사이의 관계
Loop
Loop는 edge의 endpoints가 동일한 것이다.
- 하나의 vertex에서 출발한 edge가 다시 돌아오는 경우를 말한다.
Multiple edges
Multiple edges는 두 edges가 동일한 endpoints를 갖는 것이다.
- 두 vertices 사이에 두 개의 edges가 존재하는 경우를 말한다.
