Graph 용어 정리

그래프의 정의

• 그래프 G = (Vertex,Edge)일 때, Vertex(G)는 vertex들의 집합이고 finite and nonempty이다.
• Edge(G)는 edge들의 집합이고 finite and possibly empty이다.
• 그래프는 방향성을 기준으로 undirected graph와 directed graph로 나눌 수 있다. undirected graph는 방향성이 없어서 (u,v)=(v,u)의 관계가 성립한다.(따라서 adjacency matrix로 표현할 때 무조건 symmetric한 matrix가 나오게 된다.)
• dirceted graph는 digraph라고도 하는데 방향성이 있는 그래프이다. 이 책에서는 <u,v>로 표현하고 u를 tail, v를 head로 본다.
  
  

Complete graph

• edge의 수가 최대인 그래프를 뜻한다. 즉, 서로 다른 두개의 vertex가 반드시 edge로 연결되어있는 그래프이다.
• complete graph는 방향성이 없는 undirected graph의 경우, n개의 vertex를 가질 때 n(n-1)/2 개의 edge를 가진다.
• 방향성이 있는 dirceted graph의 경우, n(n-1)개의 edge를 가진다. 또한, directed graph가 complete할 경우 strongly complete graph라고 한다.
  
  

path

• vertex u부터 v까지의 경로

simple path

• 처음과 마지막을 제외한 모든 vertex가 서로 다른 path를 simple path라고 한다.

cycle

• 처음과 마지막 vertex가 같은 simple path를 cycle이라 한다.

connected

• Vertex u와 v가 있을때, 이 둘의 path가 있으면 connected라고 한다. tree는 connected이면서 acyclic(비순환)이다.

connected component

• undirected graph에서 edge의 개수가 최대이고, connected인 subgraph를 connected component라고 한다.
• 이 그래프는 서로 다른 subgraph의 vertex를 연결하는 path가 존재하면 안된다. 즉, 독립적이어야 한다.

strongly connected

• Directed graph에서 vertex u와 v가 양방향으로 path가 존재할 때 strongly connected라고 한다.

strongly connected component

• directed graph에서 edge의 개수가 최대이고, strongly connected인 subgraph를 뜻한다.

Adjacency Matrix

• vertex의 개수가 n개일 때, n x n의 2차원 배열로 이루어진다. (i,j)가 인접할때, a[i][j] = 1 이다.
• undirected graph에서의 adjacency matrix는 symmetric이고 digraph에서는 그렇지 않다.
• undirected graph에서 vertex i의 degree는 row 성분들의 합이다.
• digraph에서는 row 성분들의 합은 out-degree이고 column 성분들의 합은 in-degree이다.
• 성분이 1인 원소들이 많지 않더라도 n^2만큼의 공간을 확보해 주어야 하기 때문에 공간 낭비가 크다는 단점이 있다. 이러한 단점 때문에 linked list를 많이 사용한다.

---

adjacency list부터는 내일 정리 해야겠다~