그래프의 용어와 표현

그래프란?

: 정점(Vertex)와 간선(Edge)을 모아둔 것

 

• 그래프 G = (V, E)

• V = V(G) = {v1, v2, v3, v4}

• E = E(G) = {(v1, v2), (v2, v3), (v1, v3), (v3, v4)} // 방향 그래프의 경우에 각각의 간선은 순서쌍으로 들어 있다.

• {(v1, v2), (v2, v1), (v2, v3), (v3, v2), (v1, v3), (v3, v1), (v3, v4), (v4, v3)} // 무 방향 그래프의 경우에 양쪽으로 순서쌍을 가진다.

관련 용어

• 무방향 그래프 

• 방향 그래프

• 완전 그래프

• 부분 그래프

• Clique

• 차수

• 경로

• DAG

• Tree graph

• 그래프의 표현

  • 인접 행렬

  • 인접 리스트

무방향 그래프

• (v1, v2) = (v2, v1)

방향 그래프

• (v1, v2) ≠ (v2, v1)

완전 그래프

• 모든 서로 다른 정점 쌍 사이에 간선이 존재하는 무방향 그래프

• n개의 간선을 갖는 완전 그래프를 수학적으로 Kn이라고 한다.

• 간선의 개수는 nC2 이다.

부분 그래프

• 원래 그래프에서 정점과 간선을 지우고 나머지 몇개의 정점과 간선을 남긴 그래프

• 그래프 H가 그래프 G의 부분 그래프이다는 것은 H의 정점과 간선이 G에 포함되는 관계여야 한다.

클릭 clique

• 그래프의 완전 그래프인 부분 그래프

정점의 차수(degree)

• 정점과 연결되어 있는 간선의 개수

  • in-degree 들어오는 간선

  • out-degree 나가는 간선 out-degree가 모두 1 인 것은 functional graph라고 한다.

경로

• 시작점과 끝 정점이 있고 간선으로 가는 길을 경로라고 한다.

• 단순 경로: 한 정점을 여러 번 지나지 않는 경로

• cycle: 시작점과 끝점이 같은 경로

DAG

• Cycle이 없는 방향 그래프

Tree graph

• DAG의 무방향그래프 버전

• 사이클이 없는 무방향 그래프 = 임의의 두 정점 사이에 경로가 정확히 하나만 존재하는 무방향 그래프 = 간선의 개수가 정점의 개수보다 하나 적은 연결 그래프

그래프의 표현

• 인접 행렬

  • 행의 모든 요소를 합하면 정점의 out degree가 됨

  • 열의 모든 요소를 합하면 정점의 in degree가 됨

  • 무방향 그래프의 경우 in-degree와 out-degree 둘 다 값을 넣어줘야 함

  • 메모리 사용량: O(V^2)

  • 구현이 편하며, 일부 알고리즘은 인접 행렬로 구현하는 것이 매우 편함

  • 한 정점에 연결된 간선을 모두 순회할 때, 항상 O(V)의 시간을 사용

  • 정점에 비해 간선이 몇 개 없는 희소 그래프에서 비효율적으로 작동

• 인접 리스트

  • 메모리 사용량: O(V + E)

  • 메모리 사용량이 적으며, 희소 그래프를 표현하는 데 유리

  • 한 정점에서 시작하는 간선을 모두 순회할 때, 연결된 정점의 개수만큼의 시간을 소요

  • 한 정점으로 들어오는 간선을 순회할 때에는 추가적인 처리가 필요