그래프의 종류

• 무방향성 / 방향성 그래프
  • 각 간선 간에 방향성이 존재하는가의 여부
• 완전 그래프
  • 모든 정점 간에 간선이 존재하는 그래프
• 부분 그래프
  • 그래프 내의 부분집합
  • 모든 간선이나 정점이 포함되지 않은 그래프

그래프 용어

• 사이클
  • 처음과 마지막이 동일한 단순 경로
  • 그래프를 만들 때 이 사이클이 생기는 지 union-find로 검사할 수 있다.
• 연결
  • 정점 u와 v 사이에 경로가 존재하면, u와 v는 연결
    • 이 때 방향성 그래프는 강한 연결 (strongly connected) 라고 함
• 연결 요소
  • 연결된 부분 그래프 중 가장 큰 것
    • 이 떄 방향성 그래프는 강한 연결 요소 (strongly connected component) 라고 함