3-1. 그래프(graph)

Graph

그래프

• 그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조를 나타내는 수학적인 개념입니다.
• 그래프는 다양한 현실 세계의 문제를 모델링하고 분석하는 데 사용됩니다.

(무방향) 그래프 G = (V, E)

• V : 노드 혹은 정점(vertex)
• E : 노드쌍을 연결하는 Edge 혹은 Link
• Object들 간의 이진관계를 표현
• n = |V|, m = |E| (개수)

• 무방향이란 예를 들어 (1,2) 나 (2,1) 이 같은 개념

 

방향 그래프 (Directed Graph)

• 방향그래프(Directed Graph) G = (V, E)
• Edge (u, v) : u로부터 v로의 방향을 가짐

가중치 그래프

• Edge마다 가중치(weight)가 존재 (사용빈도 높음)

 

 

• 두 노드 사이에 에지 여러개 있을 수 있느냐
• 자기자신에게 가는 에지 있을 수 있는냐(셀프에지)
• 보통 그래프는 어떤 두 정점 연결하는 에지는 0 또는 1다.
• 셀프 에지도 없다고 가정 ( 하지만, 방향 그래프는 또 있다고 가정)

 

 

그래프의 표현

 

인접행렬 (adjacency matrix)

• 정점의 개수가 n개인 그래프를 nXn 의 행렬로 표현한 것
• 인접한건 1 / 인접하지 않으면 0
• 대각선을 기준으로 잡았을 때 대칭행렬
• 저장공간 : n^2
• 어떤 노드 v에 인접한 모든 노드 찾기 : O(n) 시간 
• => 행 전체를 읽어서 0인지 1인지 봐야 인접한지 알 수 있기 때문 
• 어떤 에지 (u,v) 가 존재하는지 검사 :  O(1) 시간 

 

인접리스트(adjacency list)

• 정점 집합을 표현하는 하나의 배열과
• 각 정점마다 인접한 정점들의 연결 리스트
• 노드 개수 : 2m
• => 에지가 하나당 2개가 있기 때문에 (연결하니까)
• 저장공간 : O(n+m)
• 무방향 그래프 : 최악의 경우 모든 노드가 에지가 있을때 => m = O(n^2) 될 수 있음
• 어떤 에지 (u,v) 가 존재하는지 검사 :  O(degree(u)) 시간 
• 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) 시간 (최악의 경우 : n-1)   

 

방향 그래프의 경우

• 인접행렬은 비대칭
• 인접 리스트는 m개의 노드를 가짐

 

 

가중치 그래프의 경우

• 엣지의 존재를 나타내는 값으로 1대신 엣지의 가중치를 저장
• 엣지가 없을 때 혹은 대각선그때마다 상황에 따라 정의 가능
  • 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의마하는 바에 따라서
  • 예) 가중치가 거리 혹은 비용을 의미하는 경우라면 엣지가 없으면 oo(무한대), 대각선은 0
  • 예) 만약 가중치가 용량을 의미한다면 엣지가 없을때 0, 대각선은 oo(무한대)

경로와 연결성

• 연결되어 있다라는 것은 노드와 노드를 연결하는 경로가 존재할 때를 말함
• 무방향 그래프 G = (V, E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때 v와 u는 서로 연결되어 있다고 말함
• 모든 노드 쌍들이 서로 연결된 그래프를 연결된(connected) 그래프라고 한다.
• 연결요소(connected component)