Graph : 개념 정리

1. Graph

  :  A data Structure that represents the relationships between connected objects.

 

 

 

2. Terminology

Vertex = Node

Edge = link

 

3. Graph Type

Undirected Graph	Directed Graph
ONLY undirected edge	ONLY directed edge
Both way	One way
(A, B)	<A, B>
(A, B) == (B, A)	<A, B> != <B, A>

 

▶ Weighted Graph

  : A graph with the weight assigned to edges

 

▶ Sub Graph

  : A graph consisting of a subset of the vertex set V(G) & the edge set E(G)

 

 

 

4. Degree of Graph

▶ Adjacent vertex 

: 하나의 vertex랑만 연결되어있는 vertex

 

▶ Degree of Graph

: 각 vertex와 연결된 edge의 수

 

Degree of Undirected Graph	Degree of Directed Graph
∑ degree(v) = 2 * |E|	∑ in-degree(v) = ∑ out-degree(v) = |E|
( E : 총 edge의 수 )	in-degree : incomming edges 수 out-degree : outcomming edges 수
∵ edge 하나당 2개의 vertex가 이 edge를 자신의 것으로 세기 때문

 

 

 

5. Path of Graph

▶ Path 

: a set of vertices that connect two vertices (두 vertex를 연결하는 길)

 

Path	① simple path : 겹치기 불가능
	② non-simple path : 겹치기 가능
	③ cycle : 출발=도착
not-Path	불가능한 path

 

path :  0, 1, 2, 3

not path :  0, 1, 3, 2  (이런 경로 불가능)

simple path : 1, 0, 2, 3

non-simple path : 1, 0, 2, 0

cycle : 0, 1, 2, 0

 

 

 

 

6. Connectivity of Graph

▶ Connected Graph

: undirected graph 중 모든 vertex가 결국 연결된 그래프

non-connected Graph

 

 

▶ Tree

: Connected graph 중 cycle이 없는 그래프

 

 

▶ Complete Graph

: 모든 vertex가 직접 연결된 그래프

 # Number of edges ( n : vertex 개수 ) 

Undirected complete graph	Directed complete graph
n(n-1) / 2	n(n-1)