Graphs(1)

Graph

Graph G = (V,E)라고 표기하고 vertices(node)의 집합 V와 edges의 집합 E로 구성되어 있다.

vertices의 수는 |V|, edges의 수는 |E|라고 표시한다.

 

Graph의 종류

 

Path

edge들로 연결된 vertice들의 배열을 말한다.

graph

예를 들어 위의 graph에서 0,4,1,3,2,4는 path이다.

 

path 중에서도 path에 있는 모든 vertice들이 서로 다르다면 그 path는 simple하다고 한다.

예를 들어 0,4,1,3,2는 simple path이다.

 

 

Cycle

길이가 3이상인 path가 한 vertice에서 나와 자기 자신에게 연결된 것을 cycle이라고 한다.

예를 들어 위의 graph에서 1,3,2,4,1,3,2,4,1은 cycle이다.

 

cycle중에서 첫 vertex와 마지막 vertex를 제외하고 path에 있는 모든 vertice들이 서로 다르다면 그 cycle은 simple하다고 한다.

ex) 1,3,2,4,1

 

 

Connected Components

undirected graph의 경우 어떠한 vertex에서 다른 vertex로 가는 path가 최소 1개 존재한다면 connected 되었다고 한다.

어떤 undirected graph에서 subgraph 중 가장 큰 connected subgraph를 connected components라고 한다.

 

 

 

Representation

undirected representation

Costs

Adjacency Matrix : O(|V|^2) space

Adjacency List : O(|V| + |E|) space

 

|E|의 maximum size는 O(|V|^2)이다.

따라서 |E| << |V|^2일때는 Adjacency List가 효율적이지만 비슷할 때는 Adjancey Matrix가 효율적이다.