공부/자료구조 2018. 9. 26. 15:49

Graph

트리는 그래프의 특수한 케이스

그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용

용어

vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념

root node와 leaf node가 아닌 모든 노드

edge: 트리의 link와 동일개념

undirected edge ( = undirected graph)
directed edge ( = directed graph)
- 단방향, 양방향
- in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)
weighted edge ( = (directed or undirected) weighted graph)
- 서울 - 제주도 와 서울 - LA의 weight는 다름

정의1

graph G=(V,E)

V(G): empty가 없는 vertex들의 유한한 집합
v1, v2, ..., vi, vj, ... ∈ V(G)
E(G): empty가 가능한 유한한 edge들의 집합
(vi, vj) ∈ E(G) 이면 vi, vj ∈ V(G)
undirected graph
(vi,vj) = (vj,vi)
directed graph ordered
<vi,vj> ≠ <vj,vi>
집합의 표현 예시V(G1) = {0,1,2,3}; E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
V(G2) = {0,1,2,3,4,5,6}; E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}
V(G3) = {0,1,2}; E(G3) = {<0,1>,<1,0>,<1,2>}

예시

상세

degree (of a vertex): vertex에 인접한 edge의 수

in-degree (of a vertex v): 방향성 있는 edge가 vertex를 향하고 있는 edge의 수

out-degree (of a vertex v): 방향성 있는 edge가 vertex에서 나가고 있는 edge의 수

그래프 제한사항

vertex에 edge가 없거나 자기자신을 가리키는 edge는 없음

하나의 vertex에서 다른 vertex를 연결하는 edge가 중복인 경우는 없음 (<=> multigraph)

정의2

subgraph: 그래프의 한 부분
connected graph: 모든 vertex가 연결된 그래프
disconnected graph: 한개의 vertex라도 연결되어 있지 않는 그래프
adjacent nodes: 인접한 vertex간 연결되어 있는 node 관계
complete (connected) graph: 모든 vertex가 adjacent node로 표현이 가능한 그래프. 전부 연결되어 있으므로 connected graph임

예시

정의3

path: vertex X에서 vertex Y까지 가는 edge의 연결된 경로
- 아래 그림에서 A에서 D까지 가는 경로는 (A,B), (B,C), (C,D) 이므로 length=3임
cycle: 출발한 노드 다시 도착할 수 있는 구조
- 아래 그림에서 ABCDA는 cycle 구조
cyclic graph: cycle 구조가 존재하는 그래프
acyclic graph: cycle 구조가 존재하지 않는 구조 (=tree)