컴퓨터알고리즘#14

LeeMir, 12 May 2021

그래프

(정점 V, 간선 E) 쌍으로 저장하는 자료구조
경로 : 정점과 간선의 교대열
단순 경로 : 모든 정점과 간선이 유일한 경로
부그래프 : V의 부분집합과 E의 부분집합으로 구성된 그래프
신장 부그래프 : E의 부분집합과 V로 구성된 그래프
연결요소 : 그래프의 최대 연결 부그래프
밀집도
- 그래프 알고리즘의 선택은 종종 간선의 밀집도에 따라 좌우된다
싸이클
- 트리 : 연결그래프면서 싸이클이 존재하지 않는 그래프
- 숲 : 싸이클이 없는 무방향 그래프
  - 숲의 연결요소는 트리들임
신장
- 신장트리 : 신장 부그래프 가운데 트리인 것
- 신장트리는 그래프가 트리가 아닌 한, 유일하지 않음
- 신장숲 : 신장 부그래프 가운데 숲인 것