[Graph] 그래프, Graph

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 그래프 (Graph)

• 정점(Vertex)과 간선(Edge)의 쌍, G = (V, E)
• 하나의 간선은 두 개의 정점 사이를 연결하는 정점의 쌍
  • Undirected edge : 정점의 쌍에 순서가 없는 경우, 즉 (u, v) == (v, u)
  • Directed edge : 정점의 쌍에 순서가 있는 경우, 즉 (u, v) != (v, u)
• 정점은 집합이며, 간선은 집합이 아닌 공동체(Collection)
  •  즉 같은 정보를 표현하는 두 개 이상의 간선이 그래프에 존재할 수 있음
• 종류
  • Undirected graph : 모든 간선이 무방향 간선인 그래프
  • Directed graph : 모든 간선이 방향 간선인 그래프
  • Weighted graph : 간선에 가중치가 부여된 그래프

 

- 용어

예시 그래프

• 양 끝점 : 정점 U, V는 간선 a의 양 끝점(Endpoints or end vertices)
• 인접 간선 : 간선 a, b, d는 정점 V의 인접 간선(Incident edge)
• 인접 정점 : U는 V의 인접 정점(Incident vertex)
• 정점의 차수(Degree) : 인접 간선의 개수
  • 방향 그래프에서는 Incoming degree와 Outgoing degree를 구분
• 병렬(중복) 간선 : h, i는 병렬 간선(Perallel edge) 혹은 중복 간선(Multiple edge)
• 루프 : j는 루프(Self-loop) 
• 경로 : 두 정점 사이를 연결하는 정점의 순서 있는 나열(Sequence of vertices)
  • 단순 경로 : 경로상의 모든 정점이 다른 경로
  • 사이클 : 경로상의 시작과 끝 정점이 같은 경로
• 연결 그래프 (Connected graph) : 모든 정점 간에 경로가 존재하는 그래프
• 연결 성분 (Connected component) : 그래프에서 정점들이 서로 연결되어 있는 부분
• 부분 그래프 (Subgraph) : 주어진 그래프의 일부분의 정점과 간선으로 이루어진 그래프
• 신장 부분 그래프 (Spanning subgraph) : 주어진 그래프의 모든 정점과 일부분의 간선으로 이루어진 그래프
• 트리 (Tree or free tree) : 연결 그래프이면서 사이클이 없는 무방향 그래프
• 숲 (Forest) 사이클이 없는 무방향 그래프, 숲의 각 연결 성분은 트리
• 신장 트리(Spanning tree)와 신장 숲(Spanning forest)
  • 연결 그래프의 신장 트리는 부분 그래프이면서 트리
  • 연결 그래프가 아니면 신장 트리가 유일하지 않음
  • 그래프의 신장 숲은 부분 그래프이면서 숲

 

- 그래프 자료구조

• 인접 리스트(Adjacent list) 구조
  • 각 정점마다 인접 간선을 리스트에 저장하는 구조
• 인접 행렬(Adjacent matrix) 구조
  • 정점의 개수 n에 대하여 n x n 행렬의 i, j 원소에 정점 i, j를 양 끝점으로 하는 간선의 정보를 저장하는 구조