[JAVA] Graph 개념 설명

용어 정리

• Graph: 개념간 연결관계
• 무향간선: 정점들을 연결, 간선 방향 X
• 유향간선: 정점들을 연결, 간선 방향 O
• 인접: 간선 e=(a,b)존재, 정점 a,b는 인접한다
• 부속: 간선 e=(a,b)존재, 간선 e는 a,b에 부속한다
• 차수: Degree, 정점에 부속된 간선의 수 (in-degree: 들어오는 수, out-degree: 나가는 수)
• loop-back: 정점 a에 대해 간선 e=(a,a) (중복 허용 X)
• ⭐️경로(Path): 정점, 간선이 교대로 구성 / 단순 경로: 간선, 정점 중복 X

그래프 정리

• 무향 그래프(무향간선)
• 유향 그래프(유향간선)
• 가중치 그래프(가중치 or 비용을 가짐)
• 정규 그래프(모든 정점이 동일한 차수)
• 완전 그래프(정규그래프에 속함)
  • 간선 e(a,b)
  • N개의 정점인 무향 그래프의 전체 간선 개수 = $\frac{1}{2}\times N(N-1)$
  • N개의 정점인 유향 그래프의 전체 간선 개수 = $N(N-1)$
• 연결 그래프(경로 존재)
• 트리 그래프(순환X인 연결 그래프 / 임의의 2개의 정점에 대해 경로가 1개만 존재)