본문 바로가기

카테고리 없음

[자료구조] 그래프 기초

그래프

정점(Node, Vertex): 정점

간선(Edge): 정점에 연결된 선

차수(degree): 각 정점이 가지는 간선의 개수



*간선의 개수는 정점의 제곱보다 작거나 같다 

12,13,14

21,23,24

31,32,34

41,42,43


A를 정점의 수 라하고, E를 간선의 수 라 하면

E <= A^2

 

 

4개의 정점 중 2개를 선택하는 경우의 수 nC2 = n(n-1) / 2
 

 

 


*각 정점의 차수의 합은 간선의 개수 2배와 같다.