[Graph] Graph Basics

Graph 

그래프는 Vertex(정점)들의 집합 V(G)와 두 vertex를 이어주는 edge(간선)들의 집합 E(G)로 구성되어있는 구조

(G = V(G),E(G))로 표기한다.

 

방향성

• 그래프의 edge가 방향성이 있는지 없는지에 따라 Directed Graph, Undirected Graph로 나뉜다.
• Directed Graph : E(G)의 각 원소들은 ordered pair == 방향성이 있음.
• e=(a,b) != (b,a) :
  • directed pair 는 방향성을 갖고 있기 때문에 vertex 순서도 중요하다.
• Undirected Graph : E(G)의 각 원소들은 unordered pair == 방향성이 없음. 

 

인접하다

 

• (v,u) 가 E(G)에 속해있을 때 adjacent(인접하다)라고 한다.
• undirected graph에서 u와 v 가 adjacent 하면 v, u도 adjacent하다.

 

Degree of v : deg(v) : G에서 v 와 인접한 vertex의 수.

Directed graph의 경우 in-degree, out-degree를 따로 정의 할 수 있다.

Edge(v,u)가 있는 경우 u는 v의 neighbor이라고 한다.