[graph] 기본 개념 정리

1. 그래프 G = (V, E) 

V(vertex)	정점 : 연결할 객체를 나타내는 것
E(edge)	모서리 : 한쌍의 정점을 이은 것

graph란?

연결되어있는 원소간의 관계를 표현한 자료구조

즉, 정점과 간선의 집합

---

2. 그래프의 종류

종류	설명
무방향 그래프(undirected graph)	간선에 방향이 없는 그래프 임의의 모서리 (x, y)∈E 이면 (y, x)∈E 를 만족한다. 즉, (x, y)와 (y, x)는 같은 간선을 나타낸다.
방향 그래프(directed graph) = 다이그래프(digraph)	간선에 방향이 있는 그래프 = i → j = <i,j>로 표현 임의의 모서리 (x, y)∈E 이면 (y, x)∈E 를 만족하지 않는다.
완전 그래프(complete graph)	한 정점에서 다른 모든 정점과 연결되어 최대의 간선 수를 가진 그래프
부분 그래프(subgraph)	원래의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프
가중 그래프(weight graph)	간선에 가중치를 부여한 그래프
비가중 그래프(unweight graph)	모든 간선이나 정점의 가치가 똑같은 그래프
순환 그래프(cycle graph)	사이클이 존재하는 그래프
비순환 그래프(acyclic graph)	사이클이 존재하지 않는 그래프 ◆ Tree = 연결 비순환 무방향 그래프(connected acyclic undirected graph)     - 어떤 모서리를 끊어내도 두 개의 작은 트리가 만들어진다.(재귀적인 구조) ◆ DAG = 방향성 비순환 그래프(directed acyclic graph)     - 위상 정렬(topological sorting) : 우선순위를 고려해서 DAG의 정점을 정렬

완전 그래프 예시 - 각 정점이 다른 모든 정점과 연결

◆ 완전 그래프 - 간선의 수 ◆

무방향 그래프 = n(n-1)/2

무방향 그래프는 두 정점 사이에 간선이 1개만 존재할 수 있다.

그러나 방향 그래프는 두 정점 사이에 2개의 간선이 존재하므로 무방향 그래프의 2배이다.

방향 그래프 = n(n-1)

---

3. 그래프 용어 정리

• 두 정점 i와 j 사이에 연결된 간선(i,j)이 있으면 i와 j는 인접(adjacent)되어 있다.
  • 이때, 간선(i,j)은 두 정점 i와 j에 부속(incident)되어 있다.
    
    
• 정점(vertex)
  • 머리(head) : 화살표의 머리가 있는 정점
  • 꼬리(tail) : 화살표의 꼬리가 있는 정점
  • i → j 일 경우 i가 꼬리 정점, j가 머리 정점이다.
    
    
• 차수(degree) : 정점에 부속되어 있는 간선의 수 = 즉, 정점에 연결되어 있는 모서리의 수
  • 무방향 그래프  차수
    • 모든 정점의 차수 합 = 모서리의 개수 * 2
    • 즉, 차수가 홀수인 정점의 개수는 반드시 짝수이다. 
  • 방향 그래프의 정점의 차수 = 진입 차수 + 진출 차수
    • 진입 차수(in-degree) : 정점을 머리로 하는 간선의 수
    • 진출 차수(out-degree) : 정점을 꼬리로 하는 간선의 수
    • 진입 차수를 모두 더한 값 = 진출 차수를 모두 더한 값

예시 방향 그래프

정점 2의 진입 차수=2, 진출 차수 = 1, 차수 = 2+1 = 3

 

• 경로(path) : 간선을 따라갈 수 있는 길을 순서대로 나열한 것
  • 경로 길이(path length) : 경로를 구성하는 간선의 수
  • 단순 경로(simple path) : 모두 다른 정점으로 구성된 경로
    • 사이클(cycle) : 단순 경로 중 시작 정점과 끝 정점이 같은 경로
    • DAG(Directed Acycllic Graph) : 방향 그래프이면서 사이클이 없는 그래프
      
      
• 그래프에서 두 정점 i와 j 까지의 경로가 존재하면 정점 i와 j는 연결(connected)되어 있다.
  • 연결 그래프(connected graph) : 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프
                                                         즉, 떨어져 있는 정점이 없는 그래프
  • 단절 그래프(disconnected graph) : 연결되지 않는 정점이 있는 그래프